自适应精英遗传算法的快递车路径规划

袁梦飞，阚 秀，曹 乐，王夏霖，吴健珍，罗 晓

自适应精英遗传算法的快递车路径规划

袁梦飞，阚 秀，曹 乐，王夏霖，吴健珍，罗 晓

（上海工程技术大学 电子电气工程学院，上海 201620）

针对快递车物流配送效率低、行驶路线不规范的问题，提出了自适应精英遗传算法实现对快递车的路径规划。通过搭建车载定位系统，实时对车辆位置进行监督以确保行驶在规定路线上。在实际快递位置分布的基础上建立了路径规划模型，设计了基于经纬度坐标的适应度函数，以地表距离作为种群评价标准更加贴合实际运输需求；引入自适应交叉算子和自适应变异算子，根据个体基因的适应度值自适应地调节交叉和变异概率，并将精英个体进行遗传保留，更好地平衡了算法的局部搜索能力和全局优化性能。通过与其他4种智能算法的对比实验，来验证改进算法的有效性及可行性，实验结果表明改进算法的收敛性最快且解的精度明显优于其他4种算法。

快递车；自适应交叉算子；自适应变异算子；精英遗传策略；路径规划

0 引言

近年来随着互联网电商行业的蓬勃兴起，快递配送公司如雨后春笋般纷纷成立，快递车的路径规划受到了越来越多专家学者和企业的关注[1-4]。快递配送路线问题是路径规划的一个重要应用领域。目前主要通过智能启发式算法求解大规模的复杂路径规划问题[5-6]，该类算法可以较快地找到逼近最优解的满意解，但是在快递配送领域还有很多改进的空间。

现有的智能启发式算法主要包括：遗传算法、模拟退火算法和蚁群算法等。文献[7]利用网络约简技术对模拟退火算法进行了改进，并成功使用该算法为电气与照明公司做出了运输规划。文献[8]通过权重策略和变异操作改进蚁群算法，解决了多仓库的车辆路径规划。文献[9]提出了帕累托最优的多目标车辆路径问题，将蚁群算法与三元素优化（3-optimization，3-opt）算子相结合，通过所罗门（Solomon）数据集验证了算法的有效性。文献[10-12]都在对遗传算法做出改进的基础上进行路径规划。其中，文献[10]针对奖品领取车辆的路线问题，将遗传算法与局部搜索策略相结合，提高了算法的优越性；文献[11]设计了改进的路由复制交叉算子和基于卫星选择的变异算子，并将该算法用于物流服务中，减少了预期成本；文献[12]针对制造商的订单运输问题，将最优生产序列的思想嵌入到遗传算法中，提供了高质量的解决方案。然而他们都没有注意到交叉和变异概率对遗传算法性能的影响，尽管文献[11]对交叉和变异算子进行了重新设计，却不能实现算子的动态调节，难以根据当前解的质量自适应调整，极易陷入局部最优。

本文从实际的快递配送问题出发，提出了自适应精英遗传算法。该算法将实际经纬度作为模型输入，以地表距离作为适应度函数对种群质量进行评价；并设计了自适应交叉算子和自适应变异算子，可以根据当前个体基因的质量自适应地调整交叉和变异概率，实时调整种群进化方向；最后将上一代精英个体的适应度值设置成下一代的阈值进行遗传保留，从而更加快速有效地找到高精度的解。为了将算法应用到实际快递车的配送中，本文搭建了车载定位系统，将定位模块安装在快递车仪表盘内进行位置的读取和上传。企业可以根据算法提供的车辆和路径信息进行相应的安排和规划，将定位系统上传的司机行驶轨迹与规划路径进行有效比对，进一步规范司机的驾驶路线，提高企业运营效率。

1 快递车定位系统及路径规划模型

1.1 车载定位系统搭建

为了获得真实的车辆行驶轨迹信息，用于与规划的路线进行对比分析，本文选用如图1所示的多模微型定位导航模块。所选模块为合宙电子推出的一款高性能、小体积、低功耗定位模块，其内部支持全球定位系统（global positioning system, GPS）、北斗卫星导航系统（BeiDou navigation satellite system, BDS）、格洛纳斯卫星导航系统（global navigation satellite system, GLONASS）、伽利略卫星导航系统（Galileo satellite navigation system, Galileo）等多种定位。定位系统安装在图2所示的仪表盘内，对快递车的经纬度信息进行读取。为实现车辆行驶轨迹的稳定上传，本文采用SIM7600CE模块作为数据传输模块，该模块为一款适用于室外稳定信息传输的4G通信模块，通过SIM7600CE可实现采集系统与上层服务器的通信，实现定位信息的上传。

图1 定位模块

图2 定位模块安装示意图

1.2 快递配送路径规划模型的建立

根据北京市朝阳区某快递业务的实际配送情况，本文主要研究只有一个配送中心且以多辆快递车进行配送的路径规划问题。在车辆不超载的情况下，对快递车的使用数量和路线进行优化计算，以实现总行驶路径最短。

图3（a）为该快递公司的实际位置分布，其中方块表示配送中心，圆圈表示快递客户点。基于实际的地理位置信息，以经度为横坐标、纬度为纵坐标进行路径规划空间建模，模型地图如图3（b）所示。

图3 快递业务分布

2 自适应精英遗传算法

遗传算法根据“物竞天择，适者生存”的生物进化思想，按照生物遗传理论将优化问题编码为染色体基因的形式，通过种群遗传的选择、基因的交叉和变异等操作，产生问题的最优解[13]。然而在进化过程中，交叉概率和变异概率是固定不变的值，若概率值过大，会导致算法无法收敛；概率值过小，则容易陷入局部极优值。算法缺少精英保留机制，适应度值高的优秀个体也可能在进化过程中丢失优良基因。

本文采用自适应交叉算子、自适应变异算子与精英保留策略对遗传算法进行优化。为了更好地平衡算法的局部搜索能力和全局优化性能，在进化初期需要将交叉和变异概率设定大一些，扩大搜索空间。到了进化后期时，再降低交叉和变异概率，从而加快算法的收敛速度。因此，在进化过程中，通过交叉概率和变异概率的动态调整，可以使种群的进化方向自适应变化并将每一代的优秀个体作为精英直接遗传给子代，提高了算法的寻优能力与计算精度。

2.1 种群初始化

图4 基因编码解码示例

2.2 适应度函数

遗传算法通过适应度值来对个体基因的优劣进行评估，本文将最短路径值作为适应度函数。

显然，适应度函数值越小，表示基因越优秀，

规划的路径长度也越短。

2.3 选择算子

针对基因选择过程，本文采用轮盘赌策略[14]进行选择操作。轮盘赌策略是根据个体的适应度值确定在轮盘上所占的比例。适应度值越高，则代表该个体基因越优秀，在轮盘中所占的比例也越大。这种选择策略确保了优秀个体有较大的概率被选中，符合“优胜劣汰”的自然规律。

2.4 交叉算子

2.4.1 自适应交叉概率函数

为了实现种群在进化过程中根据当前个体基因的适应度值自适应调整交叉概率，本文定义自适应交叉概率函数为

在种群的遗传进化过程中，交叉概率的大小在很大程度上决定了种群的搜索空间和基因的多样性。自适应交叉概率函数将交叉概率与当代遗传中种群适应度值的平均值和最大值相联系，可以在遗传进化的过程中更好地把握种群进化方向。在进化初期，不同个体之间的基因质量参差不齐，通过自适应交叉概率函数根据当前个体的质量对交叉概率进行调节，若当前个体的适应度函数值较差，则增大基因的交叉概率，有利于增强基因的多样性，扩大种群的寻优范围；若当前个体的适应度函数值较好，则保持基础的交叉概率不变，有利于增强局部搜索能力，更快地寻求最优解。随着进化过程的持续进行，到进化后期，种群的基因不断地优化更新，总体保持着较高的质量，个体之间的适应度值相差较小，自适应交叉概率函数以较小的交叉概率对基因的交叉进行自适应调节，可以在加快算法收敛速度的同时提高精度。

2.4.2 顺序交叉策略

针对基因交叉过程，本文选用顺序交叉策略。顺序交叉策略的具体示例如图5所示，随机选择一组长度相同的基因片段对父代的基因进行交叉操作，将交叉后的基因作为子代基因进入后续进化过程。

图5 交叉算子示例

2.5 自适应变异算子

2.5.1 自适应变异概率函数

在传统的遗传算法中，相较于交叉概率而言，变异概率值设置的较小。因此，变异概率的微小变化都会对种群基因和算法的求解性能产生极大的影响。为了实现变异概率的自适应调节，本文定义了自适应交叉概率函数为

自适应变异概率函数可以根据个体当前的适应度函数值自适应调整变异的概率。当前基因的适应度值越差则变异概率越大，在进化寻优的过程中逐步降低变异概率，使得种群逐渐收敛至最优解，提高了算法的搜索效率。

2.5.2 动态变异策略

针对基因变异过程，本文采用动态变异策略。动态变异策略的具体示例如图6所示，随机选择两个或以上的基因位进行相互间的动态置换，将置换后的基因作为变异基因遗传给子代进入后续进化过程。

图6 动态变异算子示例

2.6 精英保留策略

精英保留策略避免了对优秀基因进行重复计算且在更大程度上保护了优秀基因，提高了算法的运行效率。

2.7 算法框架

本算法设计了自适应交叉算子与变异算子，根据当前个体的适应度函数值生成自适应交叉和变异概率，对选中的基因进行顺序交叉和动态变异。基于遗传进化的特征，采用了精英个体的遗传保留策略。算法具有较强的全局搜索能力，收敛性也较高。

算法的设计框架如下所示，其中为当前迭代次数，ter为最大迭代次数。

Algorithm:自适应精英遗传算法 Input: Latitude and longitude matrix Initialize:, while do Population selection: Roulette strategy;Calculate population f according to (5); Population crossover: Calculate pcaccording to (8);Order crossover; Population variation: Calculate pmaccording to (9);Dynamic variation;Elite genetic preservation according to (10); Update population genes; end while Output: Theshortest path.

3 实验分析与讨论

3.1 实验结果

表1 配送中心和客户点经纬度信息

表2 车辆和路径安排

为了更好地了解算法的求解性能，本文根据图7的配送方案绘制了如图8所示的迭代收敛曲线，进一步衡量算法的有效性。从迭代收敛曲线可以看出，自适应精英遗传算法在前60次迭代过程中优化曲线下降趋势陡峭，收敛速度较快；随着迭代次数的增加，优化曲线趋于平坦，在第166次迭代后进入稳定状态，收敛至最优解318.6。

图7 具体配送路线

图8 自适应精英遗传算法迭代曲线

3.2 与其他算法对比实验

为了检验自适应精英遗传算法的有效性，在同样的实验环境下分别与遗传算法、模拟退火算法、蚁群算法、人工鱼群算法4种算法进行对比实验，通过测试结果验证所提算法的性能。4种算法的配送方案适应度值对比如表3所示，车辆路径如图9所示。

表3 算法适应度值对比

通过对比发现，在遗传算法、模拟退火算法、蚁群算法、人工鱼群算法4种算法中，蚁群算法的求解性能相比其他3种算法而言效果略好，但是仍然与自适应精英遗传算法存在一定的差距。从车辆和路径的具体安排可以看出，遗传算法、模拟退火算法、人工鱼群算法都采用了7辆车进行配送，而本文提出的自适应精英遗传算法和蚁群算法均采用6辆车进行配送。在快递车的配送过程中，增加车辆的使用数量会增加车辆从配送中心出发和返回配送中心的这两段路径，因而在很大程度上增加行驶距离。为了减少快递车的行驶距离，算法在寻优过程中会根据本文设置的最大车辆使用数量，逐步合并路径从而减少车辆的使用数量。因此，在保证车辆不超载的一般情况下，使用车辆的数量越少，算法的寻优效果越好，所得到的行驶路径也更短。

图9 4种算法车辆和路径安排

自适应精英遗传算法与其他4种算法的迭代收敛对比如图10所示。图10中结果表明，蚁群算法在4种对比算法中收敛速度最快，与本文提出算法的收敛速度相当。然而在收敛至相同解的情况下，本文提出的算法收敛曲线更加陡峭，收敛速度也更快。

图10 自适应精英遗传算法与其他算法迭代收敛曲线

综合以上分析，本文所提出的自适应精英遗传算法具有较好的收敛性，寻优效果和求解性能都较出色。

4 结束语

为了有效提高配送效率，进一步规范快递车在物流配送中的行驶路线，本文提出了自适应精英遗传算法。通过在快递车上搭建车载定位系统，实时获得车辆的行驶轨迹信息以确保车辆行驶在规定的路线范围内。为了减少快递车的行驶路径，根据实际快递配送业务建立了路径规划模型，将客户点的经纬度坐标转换为地表距离作为适应度函数，从而实现对种群质量的有效评估，并设计了自适应交叉算子和自适应变异算子对遗传算法中的交叉和变异概率进行自适应调节。在种群进化的过程中，本文改进的算法交叉和变异概率可以根据个体的适应度函数值进行动态调节，从而有效控制算法的收敛速度和运行效率，并将上一代精英个体的适应度值作为阈值对下一代进行遗传保留。通过与其他4种智能算法的实验对比，证明了本文改进的算法能够使用较少的车辆完成配送任务，减少了行驶路径，且收敛速度较快、求解精度也更高。

[1] 江海, 陈峰. 面向快递同城运输的车辆路径问题研究[J]. 工业工程, 2019, 22(4): 58-63.

[2] 禹鑫燚, 郭永奎, 欧林林, 等. 基于线性时序逻辑的移动端快递派送路径规划[J]. 高技术通讯, 2017, 27(6): 544-553.

[3] 宋汶轩. 城市快递配送车辆路径规划研究[D]. 北京: 北京邮电大学, 2019.

[4] 郑丹阳, 毛剑琳, 郭宁, 等. 多车场动态路径问题的自适应量子蚁群算法[J]. 传感器与微系统, 2017, 36(10): 133-136.

[5] ZHANG S, GAJPAL Y, APPADOO S S. A meta-heuristic for capacitated green vehicle routing problem[J]. Annals of Operations Research, 2018, 269(1/2): 753-771.

[6] 杨旭, 王锐, 张涛. 面向无人机集群路径规划的智能优化算法综述[J]. 控制理论与应用, 2020, 37(11): 2291-2302.

[7] KHODABANDEH E, BAI L H, HERAGU S S, et al. Modelling and solution of a large-scale vehicle routing problem at GE appliances & lighting[J]. International Journal of Production Research, 2017, 55(4): 1100-1116.

[8] YU B, YANG Z Z, XIE J X. A parallel improved ant colony optimization for multi-depot vehicle routing problem[J]. Journal of the Operational Research Society, 2011, 62(1): 183-188.

[9] ZHANG H Z, ZHANG Q W, MA L A, et al. A hybrid ant colony optimization algorithm for a multi-objective vehicle routing problem with flexible time windows[J]. Information Sciences, 2019, 490: 166-190.

[10] LONG J Y, SUN Z Z, PARDALOS P M, et al. A hybrid multi-objective genetic local search algorithm for the prize-collecting vehicle routing problem[J]. Information Sciences, 2019, 478: 40-61.

[11] WANG K Z, LAN S L, ZHAO Y X. A genetic-algorithm-based approach to the two-echelon capacitated vehicle routing problem with stochastic demands in logistics service[J]. Journal of the Operational Research Society, 2017, 68(11): 1409-1421.

[12] ZOU X X, LIU L, LI K P, et al. A coordinated algorithm for integrated production scheduling and vehicle routing problem[J]. International Journal of Production Research, 2018, 56(15): 5005-5024.

[13] 吕倩, 孙宪坤, 熊玉洁. 改进遗传算法的无人机路径规划[J]. 导航定位学报, 2020, 8(5): 42-48.

[14] 马洁莹. 基于轮盘赌策略的混沌萤火虫算法研究[D]. 西安: 西安电子科技大学, 2018.

Path planning of express vehicle based on adaptive elite genetic algorithm

YUAN Mengfei, KAN Xiu, CAO Le, WANG Xialin, WU Jianzhen, LUO Xiao

（School of Electronic and Electrical Engineering, Shanghai University of Engineering Science, Shanghai 201620, China）

Aiming at the problem of low logistics distribution efficiency of express vehicles and irregular driving routes, an adaptive elite genetic algorithm was proposed to realize the path planning of express vehicles. By building a vehicle-mounted positioning system, the vehicle position was monitored in real time to ensure that it was driving on a prescribed route. A path planning model was established on the basis of the actual express location distribution, and a fitness function based on latitude and longitude coordinates was designed, and the ground distance was used as the population evaluation criterion to better fit the actual transportation needs; adaptive crossover operator and adaptive mutation operator were introduced according to the fitness value of individual genes, adaptively adjusted the crossover and mutation probability, and retained the elite individuals genetically, which better balanced the local search ability and global optimization performance of the algorithm. Through comparative experiments with other four intelligent algorithms, the effectiveness and feasibility of the improved algorithm were verified. The experimental results showed that the improved algorithm had the fastest convergence and the accuracy of the solution was significantly better than the other four algorithms.

express vehicle; adaptive crossover operator; adaptive mutation operator; elite genetic strategy; path planning

P228

A

2095-4999(2021)06-0104-08

袁梦飞，阚秀，曹乐，等. 自适应精英遗传算法的快递车路径规划[J]. 导航定位学报,2021,9(6): 104-111.（YUAN Mengfei, KAN Xiu, CAO Le, et al. Path planning of express vehicle based on adaptive elite genetic algorithm[J].Journal of Navigation and Positioning, 2021, 9(6): 104-111.)

10.16547/j.cnki.10-1096.20210616.

2021-02-04

国家自然科学基金项目(61703270)。

袁梦飞(1995—)，女，江苏扬州人，硕士研究生，研究方向为数据处理、路径规划。

阚秀(1983—)，女，上海人，博士，副教授，研究方向为数据处理、网络化系统研究。