摘    要：针对传统的遗传算法存在收敛速度慢，局部搜索能力差，易早熟的缺点，采用混合遗传算法进行优化求解开放式车辆路线问题。即采用二重结构编码，可以使问题变得更简洁，提高遗传法的搜索效率．用个体数量控制选择策略，以保证群体的多样性，周改进的顺序交叉算子避免优良基因片断在顺序交叉时被破坏，保证算法能够收敛到全局****。最后，结合具体实例，通过买验计算证明了该改进算法的艮好性能。

关键词：开放式车辆路线问题；二重结构编码；个体数量控制；顺序交叉；混合遗传算法

中图分类号：tp 29    文献标识码：a

    开放式车辆路线问题(，ovrp)是经典车辆路线问题(vrp)的拓展问题。

    ovrp问题研究方法主要包括精确算法、启发式算法和智能优化方法；在求解大规模、

复杂问题时，智能优化算法应用更广泛，其中，遗传算法具有简单通用、鲁棒性好、隐并行性和求解组合优化问题的良好特性。肖天国通过应用交叉、变异概率的自适应机制和交叉算子等技术，构造了一个求解带软时间窗的开放式车辆路径问题的遗传算法。邓猛针对开放的车辆路线安排问题，建立以车流为基础的数学模型，利用罚函数法来化简约束条件，并设计了基于自然数编码的遗传算法．

    但由于ovrp的特殊性，借助于标准遗传算法存在收敛速度慢，局部搜索能力差，易早熟的缺点。因此，针对这些缺点，本文设计了一种混合遗传算法进行优化求解。最后，通过算例，对模型和算法的性能进行了验证。

    ovrp和vrp最显著的区别在于，车辆在服务完最后一个顾客点后，不要求其回到出发车场，若需要回到车场，则必须沿原路返回，如图l所示。

   

约束条件

式中，m为配送中心拥有车辆数；wk为车辆载重量；n为客户需求点数；ri为需求点需货量；lk为每辆车日****运行距离；dij为配送中心到各需求点距离及需求点之间距离。

    约束条件式(2)表示每辆车辆所运送量不超出其载重量；约束条件式(3)表示每个需求点由一辆车送货；约束条件式(4)表示若客户点j由车辆k送货，则车辆必从某点。到达点j；约束条件式(5)表示若客户点i由车辆k送货，则车辆k送完该点货后必到达另一个点j；约束条件式(6)表示每条线路距离不大于车辆****运行距离为lk。

    针对传统遗传算法不足，本文设计了一种混合遗传算法，即采用二重结构编码，提高遗传法的搜索效率；采用个体数量控制选择策略以保证群体的多样性；采用改进的顺序交叉算子避免优良基因片断在顺序变叉时被破坏，保证算法能够收敛到全局****。

    1)遗传编码个体染色体表示的二重结构由变量码和附加码两行组成。上行s(i)为变量x(j)的附加码s(i)=j，下行为变量xsi，对应于附加码s(i)的值。

    解码算法的步骤如下：

    step 1 s=o，sum =o。

    step 2 若xs（i）=o，则ps（i） =0，执行step 4，否则，执行step 3。

    step 3 如果ei≤sum+as(i)≤li则ps(i)=l，sum= sum+as(i)，否则，ps(i) =0。

    step 4 i=i+1，如果i≤n，返回step 3，否则终止。

2)初始解的形成设表示编码的…维数组为p[n]，先令p[n]={0，l，2，…，n-l}，再利用伪随机数发生器，产生2个随机整数j1，j2其中，j1，j2属于[1，n,2]。交换数组中p[j1]和p[j2]2个元素，形成一个随机的初始解。重复该过程，直至达到所需的群体规模为止。

    3)适应度函数采用轮盘赌选择法，要求适应度函数为非负，通过下面的变化将目标函转化为适应度函数。