刘 培 （河北工业大学，天津 300400）

电子商务的飞速发展推动了我国快递业的高速发展，据国家邮政局发布的《2017年中国快递发展指数报告》显示，2017年我国所有电商及物流企业完成的包裹总量达到400.6亿件，同比增长28.1%，2011～2016年，中国快递行业业务总量保持着高速增长的趋势[1]。包裹量的剧增，给末端配送带来了挑战[2]。

1 末端配送路径优化建模

考虑到末端配送车辆存在车载量和行驶里程的约束，建立多约束车辆路径模型（VRPMC），建立模型前做出如下假设：

（1）快递员驾驶相同的车辆，且有相同载货量的限制。

（2）所有车辆满电下的行驶里程一样，忽略车辆充电时间。

（3）每个需求点的配送任务必须由一辆车一次性完成。

数学模型如下：

上述模型中，m为车辆数，Q为车载量，Dist为最大行驶里程，dij两点间的距离，xijk为0-1变量，若车辆k从点i到点j，则为1，否则为0，yik：0-1变量，若车辆k服务顾客i，则为1，否则为0。

式（1）表示模型的目标是总行驶路程最短；式（2）表示车辆的载货量约束：式（3） 表示满足最大行驶里程约束；式（4）表示每位顾客点的运输仅由一辆车来完成。

2 改进蚁群算法

针对蚁群算法容易早熟、停滞的情况[3]，引入遗传算法操作算子进行改进。用这个改进的混合蚁群算法来解决多约束车辆路径问题。

（1）复制：将复制应用到蚁群算法中，完成一代的搜索之后，把目前父代中最优秀的个体复制下来，保存到子代中，这样优秀父代个体的信息素仍然可以积累在子代中。

（2）编码：编码是交叉、变异的基础，所以先对车辆和需求点进行编码。

（3）交叉：蚁群算法中引入交叉，能够扩大搜索范围，防止算法陷入局部最优。蚁群算法每次迭代完，对产生的最优解和次优解进行编码交叉操作。

（4）变异：变异可增加种群多样性，也可提升算法效率。应用到蚁群算法中是指在交叉结束后，对种群中最好的个体采取变异操作。

改进后的算法步骤如下：

Step1：算法相关参数初始化；

Step2：为客户点及配送网点进行编码；

Step3：随机选取一辆车从配送网点出发，并建立限重、限距存储器；

Step4：根据概率及约束条件选择下一步的地点；选出一轮迭代中距离最短和第二短的路径，进行交叉、变异、复制，并择优赋给下一轮迭代；

Step5：更新信息素；

Step6：重复step3、step4、step5，进行多次迭代。

3 实例分析

本文以CN企业上海市的配送任务为例。客户点的数据信息如表1。

表1 客户点经纬度及需求量

用第2节建立的模型及算法进行求解，得出的最优解为87.991km，共需3辆车，最优配送方案为：车辆1：0→6→2→8→10→3→0；车辆 3：0→5→0；车辆 3：0→9→4→7→1→0。

4 结论与展望

本文设计了GA+ACO的混合算法来求解多约束车辆路径模型。使用matlab软件运行算法，对模型进行求解，得出了最优的车辆配送方案。未来希望将实际的交通状况考虑进去，如交通拥情况。