基于改进遗传算法的物流路径优化方法

（湖南科技大学 知识处理与网络化制造实验室，湖南 湘潭 411201）

1 引言

车辆路径优化是物流配载的中心环节，其本质是旅行商问题（TSP-Travelling salesman problem）[1]：给定一系列城市和每对城市之间的距离，求解访问每一座城市一次并回到起始城市的最短回路。TSP问题，是一种经典的从组合问题的可行解集中求出最优解的问题且是一种容易描述却难以处理的NP难题[2]。随着城镇数目n的增加，其路径可能存在数目成指数型模式增长，利用现有条件很难求出满足条件的最优解[3]。

目前，针对物流配送中心环节路径问题求解主要采用优化方法，构造法是率先被提出用来求解物流配送路径问题的，构造法求解速度高效，但是求得的解与最优解偏差太远[4]，因此构造法主要用于求得初始路径，Clarke、Wright等提出以最小代价把不在当前路径上的点添加进来[5-7]，形成一条相对不错的初始路径，最后再采用改进的算法对初始路径进行处理，尽可能提高解的质量。刘荷花等[8]针对传统遗传算法求解TSP问题时解的质量不高的问题,提出了一种能够判定遗传算法截止代数的改进遗传算法,提高了算法的收敛性，但容易陷入局部最优。因此，本文提出一种改进的遗传算法对物流配送车辆路径进行优化，提高解的质量。

2 遗传算法优化物流配送路径

遗传算法是一种经典的启发式算法，也是一种全局搜索算法[9-11]。其主要的思想是根据自然界的生存法则“优胜劣汰”，自然界生物的发展都是从简单到复杂、从低等到高等、从不适应自然界到不断适应自然界的慢慢进化的过程[12]。在这个过程中对环境适应能力强的得以生存，并将其优良基因遗传到下一代，不同个体之间的交配产生的后代是父代的一个基因组合，在这个过程中可能伴随着基因的突变和变异，产生出更好的后代。将遗传算法应用于求解物流配送中心环节车辆路径优化问题，其详细步骤描述如下：

步骤1：计算距离矩阵D=dij(n×n)；

步骤2：随机产生N个染色体TN={T1，T2，...,Tn}；

步骤3：调用评价函数计算染色体集合TN中的各染色体适应度的值；

步骤4：对集合TN首先执行选择运算，再执行交叉运算，最后执行变异运算；

步骤5：判断循环次数是否满足指定代数，若满足，继续第6步，输出最优解；否则，跳转到第3步；

步骤6：对遗传算法迭代生成的最后解调用解码函数进行解码操作，即可得到每辆车的派车路线和访问顺序。

遗传算法优化物流配载路径算法流程如图1所示。

3 改进遗传算法优化物流配送路径

遗传算法是传统经典算法，具有全局搜索能力、很好的收敛性和鲁棒性，但其搜索全局解的能力比较弱，容易陷入局部最优，为了避免陷入局部最优，所以针对遗传算法做出一些改变。

图1 遗传算法优化物流配载路径算法流程图

3.1 在求解过程中用较高质量的解代替较低质量的解

（1）采用动态交叉策略来解决遗传算法中较早收敛的问题，在求解路径的过程中，交换两个待送货客户的顺序，将距离最小的组合顺序保存下来，其交叉变异公式如下：

式（1）中pc2表示种群中配送路径最小的个体的交叉率，f为要交叉的每组中配送路径最小的个体，fmax为种群中配送路径最大的值，favg为种群配送路径平均值。

（2）采用动态变异策略可以解决算法中较早收敛的问题，变异策略同交叉策略相同，在求解路径的过程中，交换两个待派送客户之间的途径顺序，将路径最小的组合顺序保存下来，其变异公式如下：

式（2）中pn2表示种群中配送路径最小的个体的变异率，f为要交叉的每组中配送路径最小的个体，fmax为种群配送路径最大的值，favg为种群配送路径平均值。

3.2 利用爬山算法对得到的解进行优化改进

爬山算法是一种局部择优的查找算法，该算法每次从当前的解开始，然后与其邻域内的解进行比较，选择最优的解作为当前解。动态交叉策略和动态变异策略主要是在求解的过程中选择较优解，爬山算法主要是对生成的路线作进一步的优化改进，交换线路中两个待派车客户的访问顺序，如果交换两个待派车客户顺序后路径变短，就交换这两个待派车客户的派送顺序，反之，则按照原来线路的客户访问顺序不变。其流程示意图如图2所示。

图2 爬山算法改进线路的流程

3.3 改进后的遗传算法步骤

步骤1：随机产生初始种群，用自然数串进行编码，染色体中每个基因位代表待派送区域内的每个待派车的客户，每个个体对应待派送区域内全部待派车客户的一个全排列，用所配送车辆行驶的总距离作为适应度值；

步骤2：对种群中的个体进行译码，按照染色体上基因顺序计算每条染色体上车辆行驶的总路径；

步骤3：进行选择操作，用轮盘赌注方法选择父代最优个体遗传至子代；

步骤4：根据动态交叉策略和动态变异策略对个体分别执行交叉操作和变异操作，在求解路径的过程中求出较优解；

步骤5：用局部爬山法对种群中的单个个体配送路径进行改进；

步骤6：通过环境选择生成下一代新种群；

步骤7：如果达到预先设定的进化代数或停止条件，算法结束并输出路径；否则，跳转到第2步。

具体操作流程如图3所示。

图3 改进遗传算法优化物流配载路径算法流程

4 实验分析

本算法是根据步步高云通物流配送公司的实际需求提出，为了验证改进遗传算法的正确性和有效性，随机从步步高云通物流2017年11月份订单数据中选择3 000条订单进行测试，每一个订单是一个待派车门店。实验采用JAVA编程语言，对传统遗传算法和改进后的遗传算法进行编码实现，分别求解物流配送路径。通过对两种算法求得最优物流配送路径的行驶里程和耗费时间进行对比分析。

利用遗传算法进行物流配送路径优化求解，需要预先设定种群规模N的大小，种群规模N影响算法的执行效率；交叉概率Pc的大小影响着求解较优路径时交换途径带派车客户的操作的频率，同样变异概率Pm影响着交换途径待派车客户顺序操作的频率。根据步步高订单数据得知，一个区域一天的待派客户量在500左右，同时考虑到种群多样性和收敛时间，种群规模N设定为10 000，兼顾考虑算法执行的效率和保持种群的多样性，变异概率Pm设置为0.05，交叉概率Pc设置为0.6，终止条件最优个体持续的代数M=150。设定比较指标里程节约百分比、标准差、路径较优百分比。程，L2：改进遗传算法平均里程）。标准差里程的平均值，N：总实验次数，i:第i次实验）。路径较优百分比=N1/(N1+N2)（N1：传统遗传算法出现的路径较优次数，N2：改进遗传算法出现的路径较优次数）。

表1 实验结果对比分析

从表1可知，在N次实验中，通过路径较优百分比可以看出，改进遗传算法明显优于传统遗传算法，特别是在里程稳定性方面，改进遗传算法求得的路径里程几乎没有任何的波动；里程节约方面，传统遗传算法比改进的遗传算法平均节约10.15%，也就是说每100km大约节约10.15km。

5 结束语

物流配送的中心环节-路径优化问题是现阶段国内外专家、学者正在研究的热点问题，各种优化算法层出不穷。本文先对传统遗传算法求解物流配送中心环节路径优化问题进行了介绍，由于传统遗传算法在求解物流配送路径优化方面存在过早收敛和解不稳定的特征，针对性的采用动态交叉策略和动态变异策略避免了在求解路径时出现过早收敛的问题，然后采用爬山算法对交叉和变异操作之后得到的较优解进一步的优化改进，提高了解的质量。最后，运用步步高云通物流公司的真实订单数据进行模拟仿真实验，进一步证实了本文提出的改进遗传算法在求解物流配送路径方面的可行性和优越性。

[1]李娟,张婷,李元香.基于改进演化算法的最短路径问题研究[J].计算机应用与软件,2015,32(9):244-245.

[2]刘晗兵.基于GIS决策功能的物流配送TSP优化模型研究[J].电子设计工程,2017,25(18):46-49.

[3]Qing-rong Wang,Chang-feng Zhu,Ying Li,Zheng-kun Zhang.Research on robust optimization of emergency logistics network considering the time dependencecharacteristic[J].IOP Conference Series:Earth and Environmental Science,2017,69(1).

[4]申艳光,张玲玉,刘永红.基于混合遗传算法的物流路径优化方法研究[J].计算机技术与发展,2018,(3).

[5]Thi Thoa Mac,Cosmin Copot,Duc Trung Tran,Robin De Keyser.A hierarchical global path planning approach for mobile robots based on multi-objective particle swarm optimization[J].Applied Soft Computing,2017,59.

[6]Y Volkan Pehlivanoglu.A new vibrational genetic algorithm enhanced with a Voronoi diagram for path planning of autonomous UAV[J].Aerospace Science and Technology,2011,16(1).

[7]Xiao-Bing Hu,Ming-Kong Zhang,Qi Zhang,Jian-Qin Liao.Co-Evolutionary path optimization by Ripple-Spreading algorithm[J].Transportation Research(Part B),2017,(2).

[8]刘荷花,崔超,陈晶.一种改进的遗传算法求解旅行商问题[J].北京理工大学学报,2013,33(4):390-393.

[9]唐冲.基于模拟退火算法的应急物流车辆调度[J].物流技术,2017,36(1):114-116.

[10]蒋然.改进遗传算法在TSP问题中的应用[J].软件导刊,2016,15(12):127-129.

[11]金巳婷,吕闪,吴阳明,等.基于改进遗传算法的物流配送路径优化方法研究[J].计算机与数字工程,2017,45:629-631.

[12]AdemTuncer,Mehmet Yildirim.Dynamic path planning of mobile robots with improved genetic algorithm[J].Computers and Electrical Engineering,2012,38(6).

[13]刘兆仁,徐冠宇,尹航.基于遗传算法的公共自行车调度优化[J].物流技术,2017,36(2):78-81.