物流取送件路线优化模式及算法

导语：物流取送件路线优化模式及算法一文来源于网友上传，不代表本站观点，若需要原创文章可咨询客服老师，欢迎参考。

1引言

如今物流配送在经济增长中的地位日益显著，而车辆调度又是物流配送中的主心骨之一，选取恰当的车辆路径方案，可以提高服务质量，增加客户满意度，也能节约成本，带来更大的效益。所以对车辆取送货问题(即VRPB)这种复杂普遍的车辆问题的研究优化是当下前沿热点之一。正是对车辆问题研究的广泛性，从中可以得出遗传算法对解决NP难题更有优越性，所以本文研究VRPB优化问题也同样选择遗传算法，不过为了更加方便有效地进行运算，本文对遗传算法进行了一定的改进。

2同时送取货(VRPB)的数学模型

2.1问题描述

VRPB问题可以描述为，车队车辆从初始点出发，完成节点的取货送货任务，并回到初始点的过程。为了将现实的取送货问题抽象为数学模型，建立如下假设:①只有一个初始点，每辆车都从初始点出发，完成任务后又回到初始点;②车辆载重能力为已知，车辆的取送货量不能超过车辆的能力;③节点位置已知，即各节点之间以及节点与初始点之间的距离;④每个节点的取送货量已知;⑤每个客户只能由一辆车服务一次;⑥在客户处同时完成送货和取货任务。

2.2参变量定义

V，所有节点的集合，V={i}，i=0为初始点，i=1，…，n为客户需求点;I，所有客户需求点集合，其中V=I∪{0};M，所有车辆的集合，M={k}，k=1，…，m;Qk，车辆k的能力;M，车辆的最长行驶距离;C，各节点间的距离矩阵，C=(cij)，i∈V，j∈V;其中cii=∞，i∈I，c00=0;pi，客户i的取货量，i∈I;di，客户i的送货量，i∈I;sij，车辆从节点i到达j的距离;xij，车辆是否从节点i直接到达节点j，当xij=1时表示车辆服务于节点i与j之间;否则xij=0。yijk:从节点i直接到达节点j时车辆k上的送货量;zijk:从节点i直接到达节点j时车辆k上的取货量;uik:节点i是否由车辆k服务，当uik=1时表示车辆k服务于节点i，否则uik=0;

2.3数学模型

Minf=∑ni=0∑nj=0∑mk=0cijxijk(1)∑ni=0x0ik=2，k∈M;(2)公式(1)为目标函数，是求最优解，使总运输成本最小，即距离最短;公式(2)表示每辆车都是从配送中心出发最后回到配送中心;公式(3)是保证进入每个节点的车辆又从该节点驶出，并且保证每个节点只被一辆车服务一次;公式(4)～(7)表明车辆任何时间所载货物不能超过其最大能力;公式(8)表示每辆车不能超过它的最大行驶距离;公式(9)为各个决策变量取值约束。

2.4改进遗传算法求解

2．4．1编码及初始值生成

本文选用整数编码。将其中一条可行路线编成长度为n+k+1的染色体(i11，i12，i13，…，i1s，0，i21，i22，i23，…，i2t，0，…，0，ik1，ik2，…，ikw)，其中0表示配送中心，ikj表示第k辆车路径上的第j个顾客的顾客号。下面对这个染色体结构进行解析:第一辆车从配送中心0出发，经过客户i11，i12，i13，…，i1s后，回到配送中心0，形成子路径1;第二辆车从配送中心0出发，经过以前未服务过的客户i21，i22，…，i2t回配送中心0，形成子路径2;如此反复，直到所有客户的要求全部被满足。为简化编码，可将染色体中的第一个“0”省略。例如，染色体3－2－5－0－9－7－6－0－4－1－8表示如下行车路线:子路径1:配送中心0→客户3→客户2→客户5→配送中心0;子路径2:配送中心0→客户9→客户7→客户6→配送中心0;子路径3:配送中心0→客户4→客户1→客户8→配送中心0;从这种染色体的结构可以看出，它具有子路径内部有序而子路径之间无序的特点。

2．4．2选择

我们运用适应度来对染色体进行选择。对于染色体S的适值函数h(S)则可基于目标函数式(1)进行构建。由式(10)表示:h(S)=1/f(10)为方便说明下面会取一些简单的数值进行阐述，具体如下:每个节点用其i值表示，车与车之间用起始点i=0隔开，即如果需要5辆车，为n=12个客户服务，那么编码形式如下:(012401130560780129100)。2．4．3交叉运用改进的OX交叉法，将被交叉的子串复制以后移到对方的首位。这不仅能够在相同双亲的情况下，产生新染色体，避免早熟，做到和放在原位置一样的作用，同时又能够将对原染色体的破坏降到最低，尽可能保留原路径的最优性，具体如下:图1交叉示意图运用于实例，如下:染色体V1:(012401130560780129100)染色体V2:(031001248012011670950)由上述图示的变换我们可得到交叉后的子染色体P1:(124812113567910)，进行完交叉，又要再次对其进行解码，得P1:(0124801211035607910)。2．4．4变异运用可行性变异操作，使每次变异的结果都能得出有效解，从而提高算法的效率。例如给定各节点取送货需求量如下表，其中Q1=Q2=Q3=10染色体P1经过第一步变异操作后得到P11:(125601211034807910)。可行性变异操作需要分成两阶段进行:首先检验每辆车所取送的货物是否超出车辆运输能力，如果超出则进行车辆间节点调换;然后检验编码是否满足公式(4)～(7)的约束。如果不满足，则调节车辆内部节点顺序。具体操作如下:第一阶段:车辆间可行性调整。依次检验每一个节点，如不满足约束，则将该节点调整到下一个0节点之后，由下一辆车服务。经过第一阶段，该染色体最后的编码ρ12:(0124081201135067910)。第二阶段:车辆内部可行性调整操作。满足总送货辆和总取货辆的限制，并不代表染色体可行。还需要调整节点顺序，实现真正可行。以第一辆车为例，按上述方法将不满足约束的节点调整到最后服务。产生新染色体:(0124081201135067910)。

3实例计算与试验分析

运用MATLAB7.0进行实例验证，设有快递公司配送中心0，及它所负责区域的100个客户，客户点坐标如下表，运输的车辆载重量一致，均为100。在计算中，设定相关参数:M=300，交叉概率，变异概率分别为:Pc=0．85，Pm=0．02。为证明实验的有效性，我们进行4次运行，最后运行得结果如下表。通过上表，可得四次试验的平均成最优目标值为1968.4，车辆数为17，平均跌代数为280。其中第3次得到的最优解最佳，目标函数值为1960.1。

4结束语

根据实际情况，综合各方面因素对取送货车辆运输路线进行优化。在选用最为适用的遗传算法时，根据具体情况，对算法进行创新改进，使它对整个求解过程更具有效性和方便性，最终用实例求出的最优解证明模型和算法的可行性。但模型和算法都有一定的复杂繁琐性，还有待进一步简化改进。