基于混合遗传算法的快递车辆路径优化问题研究

敖成敏

摘 要：车辆路径问题是物流配送过程中的关键环节，车辆路径优化问题是一个典型的有约束的组合优化问题，属于强NP问题。本文在建立车辆路径模型的基础上，运用分区算法，把大量的数据区域划分成几个不同的较小的数据区域，利用局部搜索算法和遗传算法结合的新的混合遗传算法来确定具体的快递车辆的配送路径。仿真实验证明，该混合遗传算法在寻找最优解上具有可行性，而且在运算效率方面有相应的提升。

关键词：混合遗传算法;配送分区;局部搜索算法;快递物流配送

中图分类号：U491 文献标识码：A

0 引言

Dantzig和Ramser[1]二十世纪六十年代在首次提出物流配送路径优化问题后，很快便成为组合优化领域和运筹学的研究热点以及前沿问题。Loannou G，Prastacos G[2]等人在建立带时间窗的问题模型时，采用可得到更好解的启发式算法求解车辆路径问题。沈维蕾等[3]在建立数学模型的基础上，建立混合快递服务的配送模式。目前，国内外有许多研究车辆路径规划问题的智能优化算法，其中局部搜索算法简单灵活，但容易陷入局部最优解。赵威，曾国辉等[4]以改进的局部搜索算法为基础，融合蚁群算法中信息素因子和人工势场算法中势场因子，建立了启发函数模型以提高寻优的目的性，并对搜索到的路径用迭代法进行优化。故本文采用局部搜索算法和遗传算法相融合的混合遗传算法，从而解决传统遗传算法求解拥有大量数据的车辆路径问题时会出现搜索效率低、收敛速度慢、早熟收敛等现象。

1 快递车辆路径模型

本文将优化目标设定为快递车辆的行驶路径最短。设为客户总数;为客户的需求量;为客户与客户之间的距离。当时，指位于配送中心，指客户2与客户3之间的距离;为车辆总数;为车辆的最大装载量;为车辆的最大行驶距离;为车辆配送的客户总数;当时，表示车辆不是配送车辆;为车辆参与配送客户的集合;当时，;当时，，其中表示该客户在车辆的配送路线中所处的位置为。

该模型中，目标函数（1）（2）叙述的车辆配送路径优化目标是将配送车辆的行驶总路径最短;约束条件（3）表示每个客户点只能被遍历一次;约束条件（4）叙述的是每条配送路径的总需求量不超过配送车辆的最大装载量;约束条件（5）表示的是每一条配送路径的总遍历长度不超过该车辆一次最大行驶距离;约束条件（6）（7）（8）规定了运输配送路径包含所有的客户点。

2 算法的求解

混合遗传算法的主要思想是：将每个算法的优势有效的结合起来，从而高效率的求解车辆路径优化问题，为物流配送中心提供具有参考价值的车辆调度方案。在面对大量又不尽相同的客户数据时，首先采用分区算法对客户数据初次区域分区;然后利用最近邻算法得出各分区域内的配送车辆的行驶路径的初始解;再运用遗传算法和局部搜索算法融合形成的混合遗传算法对初始解进行优化计算，从而求解出每辆快递服务车辆的服务序列。

2.1 混合遗传操作

混合遗传操作包括局部搜索操作和遗传操作两个环节。

局部搜索操作的目的是进一步优化算法的求解能力。在算法过程中，任意选取个体基因串中两个位置，交换该位置对应的基因，生成新的个体，若新的个体对应的最优值优于之前的个体，则以新个体取代旧个体，否则保留旧个体。

遗传操作分为选择、交叉、变异三个操作环节。其中，选择操作有多种选择方法，本文选取加权随机（轮盘赌）配对，对染色体进行选择;交叉操作，交叉运算本文采用的是等长度的染色体编码，且是小数编码，采用单点交叉策略;变异操作中为保持局部随机搜索能力和保持群体的多样性，避免出现未成熟就收敛的情况，本文对染色体第一段编码采用单点变异。

3 算例分析

3.1 算法有效性

图3.1给出了最优解随遗传算法迭代次数的变化图。由图3.1可知，当迭代次数达到500代左右，达到最优解收敛状态。

3.2 算法敏感性

为分析混合遗传算法中种群最优个体交叉变异概率的变化对最优解的影响，本文设定局部搜索次数为50;最优个体交叉概率为0.5、0.6、0.7、0.8、0.9以及最优个体变异概率为0.1、0.2、0.3、0.4、0.5两两组合对三类测试数据集进行25组实验，每组实验运行算法10次取平均值。通过对三类数据集的分析，发现整体上，最优解受最优个体变异概率的影响不显著，随最优个体交叉概率的增加而减小。并且，当最优个体交叉概率趋近0.6，变异概率趋近0.3时，算法会取得最优解。

4 结论

通过对物流路径优化问题进行深入的研究发现，本文将遗传算法与局部搜索算法相混合，得到了一种求解车辆路径问题的高效算法——混合遗传算法。最后引用实例对比分析求解结果，说明了混合遗传算法拥有寻找最优解的能力，并且在运算效率方面都能表现出一定的提高。

参考文献：

[1]Dantzig G B，Ramser J H.The Truck Dispatching Problem[J].Management Science，1959，6（01）：80-91

[2]Loannou G，Prastacos G.A greedy look-ahead heuristic for the vehicle routing problem with time windows[J].Journal of the Operational Research Society，2001，52（05）：523-537.

[3]周蓉，沈維蕾，刘明周，等.带时间窗装卸一体化车辆路径问题的混合离散粒子群优化算法[J].中国机械工程，2016，27（04）：494-502.

[4]赵威，曾国辉，黄勃，等.基于改进局部搜索算法的三维空间路径规划研究[J].电子科技，2019（06）：58-63.