基于改进遗传算法的同城快递配送模型

宋 娟，崔 艳

（1.宁夏大学 物理电气信息学院，宁夏 银川 750021；2.河南广播电视大学 理工学院，河南 郑州 450008）

0 引言

电子商务与连锁商业的兴起推动了物流业的发展[1]，近年来同城快递配送问题已经成为现代物流系统中微观层次的热点问题[2]。

目前，基于同城快递配送方案的研究多集中在算法优化上，遗传算法在求解组合优化问题[3-4]上所表现出的良好特性，被广泛地应用于快递配送领域。本文针对传统遗传算法的收敛慢、全局搜索能力差等不足，提出了一种改进的遗传算法。该算法采用了2-OPT(2-optimization)与翻转变异相结合的变异方法，并结合了模拟退火机制[5]，经实验验证，在解决同城快递配送问题方面有较高的效率。

1 快递配送问题的建模

1.1 快递配送问题的描述

同城快递配送问题可描述如下：某快递公司要从一个配送中心向若干个配货点配送快递，配送中心拥有若干辆配送车辆，每辆车的承重量相同并已知，选取的车辆数和每辆车的路线是未知的。配送车辆从该中心出发，在车辆负载范围内进行配送，并在任务完成后返回配送中心，如图1所示是4条车辆行驶路线的配送图。本文采用车队行驶的总距离衡量快递配送的代价。总距离越小，表明配送方案越优。

图1 车辆行驶路线的配送图

1.2 快递配送问题的数学模型

以最短配送距离为目标，针对同城快递问题，建立数学模型。模型中，配送中心编号为0，快递提货点编号为 1，2，…，n，配送中心和客户点均用 i(i=0，1，2，…，n)来表示，cij表示从客户i到客户j的运输成本（这里指距离），xijk表示车辆 k从 i到 j，yik表示需求点 i由 k服务，如式(1)、(2)所示。 约束条件如式(3)～式(10)所示。

目标函数(3)表示车队总的最短配送距离；约束(4)为车辆装载能力约束，即每条配送线路k的送货量不能超过车的最大载重量；约束(5)保证每个客户都被服务；约束(6)保证车辆都从配送中心出发并返回到配送中心；约束(7)、(8)保证如果客户点i、j在车辆k的行驶线路上，那么客户点 i、j将由车辆 k服务；约束(9)、(10)定义了 xijk和yik的范围。

2 改进的遗传算法求解同城快递问题

2.1 改进遗传算法的设计

本文中提出的改进遗传算法将模拟退火机制与传统的选择算子相结合，有效避免“早熟收敛”，本文采用改进的遗传算法求解快递配送的具体流程如图2所示。

图2 改进遗传算法设计流程

2.2 染色体编码方案

本文采用的是基于配货点编号的自然数编码，采用“先排序，后聚类”的方法，染色体的编码为包含全部配货点编号的一个不重复排列，路径的分割要求满足每辆车配送的所有配货点的总货物需求量不超过该车载重。即在一个染色体中，按照从左到右的顺序，将达到车辆载重的配货点序列确定为一条车辆路线。这种编码方式占用存储量较小，而且产生的配送方案会覆盖所有配货点，因而编码效率较高。

2.3 适应度函数

适应度是用来区分群体中个体好坏的标准[6]，本文中以车队行驶总距离为成本衡量标准，适应度函数如式(11)所示，其中F(x)表示染色体对应的路径距离。

2.4 初始群体生成

[7]表明，虽然初始群体的解分布不影响最优解，但是如果初始群体的解是均匀分布的，会减少算法陷入局部最优的可能性，因而本文中在保证多样性的前提下随机生成初始群体。

2.5 选择算子

本文采用的是适应度比例法（又称轮盘赌法）与模拟退火算法相结合的方法。适应度比例法的优点是简单易操作，基于适应度比例选择算子。经典的适应度比例算子易实现，但是选择误差比较大，容易导致最优配送方案流失，未进入下一代，从而导致结果收敛于局部最优解。本文采用轮盘赌法与模拟退火机制相结合的方法，引入模拟退火机制的配送选择操作。

2.6 交叉算子

由于采用配货点全排列方式进行编码，即配送方案会覆盖全部配货点，并不会对同一配货点重复配送，若直接选用部分匹配交叉算法，交叉结果代表的配送路线可能会遗漏部分配货点，使得交叉结果的存活率过低。因此，本文采用改进的部分匹配交叉法，对交叉后的结果进行调整优化，使得交叉结果代表的快递配送方案均可完成对所有配货点的快递配送任务。具体操作过程如下：(1)根据选择概率选择进行交叉的父代配送方案A、B；(2)通过随机函数生成交叉片段首末下标a、b；

(3)将A、B染色体下标a与b之间的片段进行交叉，得到A1、B1，同时使用两个标记数组flag1、flag2记录每个配货点编号交换后对应的配货点编号，未发生交换则置为 0；

(4)对 A1、B1的未交叉基因段进行遍历，若对应的flag1、flag2有交换记录，则将对应的配货点编号置换，直到对应flag1、flag2无交换记录；

(5)得到最终交叉后代 An、Bn，进入下一代。

2.7 变异算子

传统遗传算法的变异算子可能会导致出现配送路径大量交叉的现象，一旦发生交叉现象，一定会增大解路径的长度，因而消除临近交叉显得尤为重要。本文采用了翻转变异和2-OPT相结合的变异方法，使得变异向更优的方向趋近。2-OPT具体方法为：对于选中的长度为n的个体（起始下标为0），使用随机函数确定一个下标 i(i+3＜n)，若临近配货点的配送路径满足式(12)，则将基因串中下标为i+1和下标为i+2上的配货点编号交换。 其中 d(i，j)表示配货点 i与 j之间的距离，2-OPT原理如图3所示。经过优化后，可以最大限度地消除配送方案中临近配货点的路径交叉现象，从而提高算法求解性能。

图3 2-OPT原理示意图

3 仿真实验

3.1 算例说明

本节中采用一组国际标准测试数据 E-n51-k5[8]进行实际测算，并与其他方法的性能进行比较。假设同城快递配送公司目前拥有1个配送中心和50个客户点，配送中心编号为0，客户点编号为 1～50，车辆的容量为160单位，配送中心坐标为(30,40)，各客户的坐标及客户快递需求量如表1所示。

采用本文提出的改进的遗传算法进行运输方案求解，利用MATLAB构建算法实现。为了兼顾算法性能和效率，取种群规模N=100，最大进化代数 2 000，交叉率 Pc=0.8，变异率 Pm=0.05。

表1 同城快递公司客户点位置坐标

3.2 实验结果与分析

采用改进遗传算法得到如表2的运输计划，最优解序列为配货点编号的的全排列，根据配货点货物需求量和车辆载重可知，需要5辆车进行快递配送，配送距离的总和(即最小成本)是 548。

表2 本文遗传算法得到的运输计划

接着对此快递配送问题进行了100次仿真实验，以验证算法的稳定性。每10次的平均结果如图4所示。可收敛到的最优解为 548，最差解为562，平均解的值为555.5，最优结果与最差结果之间相差不超过6%，结果相对稳定，这样本文的算法稳定性得到了验证。

图4 仿真每10次的平均结果

对于大规模的快递配送问题，不合理的解可能会导致配送方案代价很大，如图5所示为初始解的配送路径图。图中横轴、纵轴分别代表了位置坐标轴，中心交点代表配送中心，其余点代表配货点。传统遗传算法虽然可得到较优解，但极易陷入局部最优解，并出现大量的配送路径交叉现象，如图6所示。本文提出的改进遗传算法使用模拟退火机制避免局部最优，同时使用了2-OPT与翻转变异相结合的变异方法消除了临近配货点之间配送路线的交叉现象，极大降低了快递配送的代价，如图7所示。

图5 初始解的配送路径图

图6 传统遗传算法的配送路径图

图7 本文改进遗传算法的配送路径图

4 结论

针对同城快递配送问题，本文提出了一种改进的遗传算法对快递运输路线规划进行优化。将遗传算法与模拟退火机制相结合，并引入了2-OPT方法消除交叉路径。经过仿真实验可知，本算法可以跳出局部最优得到全局最优解，并且最大程度上减少了交叉路径的出现，同时具有很高的稳定性。因而本文所提出的改进遗传算法对于求解同城快递问题有很强的有效性和可行性。

在后续的研究中，本文的同城快递模型将考虑时间等其他次要因素，使得模型更加丰满、更接近现实，因而多目标的同城快递配送优化是今后的工作重心。

参考文献

[1]周慧，罗小琼.物流电子商务[M].北京：清华大学出版社，2006.

[2]曹淑艳，李振欣.跨境电子商务第三方物流模式研究[J].电子商务，2013(3)：23-25.

[3]HOLLAND J H.Adaptation in natural and artificial systems：an introductory analysis with applications to biology，control and artificial intelligence[M].MIT press，1992.

[4]刘鲭洁，陈桂明，刘小方，等.基于遗传算法的SVM参数组合优化[J].计算机应用与软件，2012，29(4)：94-96.

[5]段谟意.基于免疫克隆模拟退火算法的网络生存性研究[J].计算机工程与设计，2013，33(12)：4436-4439.

[6]张永，朱林杰.基于遗传禁忌搜索的分类器选择集成方法[J].Computer Engineering，2011，37(8)：183-185.

[7]何娟，涂中英，牛玉刚.一种遗传蚁群算法的机器人路径规划方法[J].计算机仿真，2010(3)：170-174.

[8]BALDACCI R，MINGOZZI A，ROBERTI R，et al.An exact algorithm for the two-echelon capacitated vehicle routing problem[J].Operations Research，2013，61(2)：298-314.