基于混合遗传算法的大规模VRP问题算法研究

冉崇善　张妍

摘要：物流配送的车辆路径问题（VRP）是近年来物流领域中的研究热点，该问题属于NP难题，较难得到最优解和满意解。在建立了车辆路径问题数学模型的基础上，该问题被分解为两个阶段进行研究，分别为利用基于基地启发式分区算法进行区域划分和利用改进的遗传算法来确定具体的一条配送线路的先后次序。通过此改进的混合遗传算法最终得到优化配送路径。仿真计算结果表明，在大规模车辆路径问题中改进后的算法相比于传统的遗传算法最优解的质量得到一定提高。

关键词： 物流配送；大规模；车辆路径；分区算法； 遗传算法

中图分类号：TP301 文献标识码：A 文章编号：1009-3044（2016）18-0182-03

Research on Large Scale VRP Problem Based on Hybrid Genetic Algorithm

RAN Chong-shan，ZHANG Yan

（Shaanxi University of Science & Technology， Xian 710021， China）

Abstract：The vehicle routing problem （VRP） is a research hotspot in the logistics field in recent years. The problem is a NP problem， and it is difficult to obtain the optimal solution and the satisfactory solution. On the basis of the mathematical model of vehicle routing problem， the problem is decomposed into two stages were studied， namely the use of the base heuristic partitioning algorithm for region partition and the improved genetic algorithm to determine the sequence of specific a distribution line. Through this improved hybrid genetic algorithm to optimize the distribution path. The simulation results show that the improved algorithm can improve the quality of the optimal solution compared to the traditional genetic algorithm in the large-scale vehicle routing problem.

Key words：logistics distribution； large-scale； Vehicle routing； Partitioning algorithm； logistics distribution

1 引言

随着物流产业的迅猛发展、物流配送点大规模的增加，车辆路径问题的解决方案成为了目前研究的一个重点。解决车辆路径问题的算法很多，比较常用的有旅行商法、动态规划法、分区配送算法[1]、蚁群算法、粒子群算法、遗传算法等。新改进的混合遗传算法是在传统遗传算法的基础上采用精华模型和比例选择相结合的选择策略，构造了一种用于求解大规模车辆路径问题的混合遗传算法。在于文献[1]提出的改进遗传算法进行对比后，可知此改进遗传算法具有较强的全局搜索能力和较快的收敛速度。

2 物流配送车辆路径优化问题的数学模型

物流配送车辆路径优化问题的数学模型可以描述为：从配送中心用多辆汽车向多个需求点送货，每个需求点的位置和需求量一定，每辆汽车的载重量一定，要求合理安排汽车行驶路线，使总运距最短，并满足以下条件：

1）每条配送路径上各需求点的需求量之和不超过汽车载重量；

2）每条配送路径的长度不超过汽车一次配送的最大行驶距离；

3）每个需求点的需求必须满足，且只能由一辆汽车送货。

设配送中心拥有K台容量为q的车辆，i个客户的需求量为g，且gi≤q，i=1，2，…，i，将配送中心编号为0，配送中心和客户用i（i=0，1，...，i）表示，且有

Bramel和Simchi-Levi提出了基于基地启发式分区算法[2]，本文借助其算法思想，将它分解成一个分派问题（Pl）和一个单车线路优化问题（P2）。

P1：

且满足如下约束条件：

Pl中，zk表示车辆k所能服务的客户集合，满即足yki=1的客户集合，f（zk）表示在zk中满足约束条件的客户最优旅行线路的长度，由p2确定。

且满足如下约束条件：

前两个等式描述了两个变量之间的关系，对于客户i，只有两个客户与i相连；第三个等式消除了子回环，表示没有任何子回路解产生。

3 算法原理及改进

3.1算法原理

针对大规模车辆问题，本文首先用基于基地启发式分区算法进行区域划分，求解P1模型，然后运用最近邻算法计算各区域内的配送车辆的行驶路径的初始解，最后运用混合遗传算法对初始解进行优化，求解P2模型。

在实际的配送中，一般优先考虑离配送中心最远的点。我们利用地理信息系统和电子地图，可以确定在配送区域内任意两个网点之间的最短距离，且可以确定任一网点的左右两个关键节点，具体的求解思路是：

（1） 用改进的基地启发式算法每次都优先考虑离配送中心和己确定的基地集合最远的点[3]。基地，综合考虑客户的需求及车辆容量，从基地开始运用广度优先遍历算法，依次寻找最近的关键节点，由关键节点形成关键群；

（2） 关键群为中心扩展并形成配送线路，当达到预定的工作量时停止扩展；

（3） 未在线路上的网点进行聚类，直到所有的网点都在线路上。

基地启发式分区算法流程图如图1所示。

一个区域内单车线路优化算法的基本思路为：①利用最近邻算法确定初始可行解，并生成一个初始路径集合；②运用遗传算法优化初始可行解，再对由遗传算法确定的个体实施多次邻域操作。

3.2算法改进

3.2.1选择算子改进

本文采用精华模型和比例选择相结合的选择策略[4-5]，该策略保证最优个体生存到下一代，适应度较大的个体以较大概率进入下一代。其基本思路是对每代种群中的k个染色体按适应值函数值进行排序，其中适应值函数值最大的染色体复制并直接进入下一代，其余的k-1个染色体由轮盘赌选择法或比例选择法确定。

3.2.2交叉算子改进

本文设计了一种新的前置交叉算子。现用9个顶点为例来说明其原理，图2所示。设p1={1 2 3 | 4 5 6 | 7 | 8 9}，p2={4 5 2 | 1 8 7 6 | 9 3}，其中“|”表示交叉点。子个体确定的方法为取p2中的两个交叉点中间的点放在子代C1的开始处，得C1={1 8 7 6 X X X X X}，对C中未确定位置的X，在p1中找到暂时没有在C1中出现的离6最近的点3，将3放在6的后面，从左到右将p1中未出现的点移到C1中，最后C1为{1 8 7 6 3 4 5 9 2}。交叉点位置为：C1=2、C2=7。

给定两个相同的染色体，经过新的交叉算子仍可以产生不同于父体的新个体，如p1=p2={4 5 2 | 1 8 7 6 | 9 3}，则经过新的前置交叉算子后两个子代为{1 8 7 6 3 4 5 2 9}，不同于其父代染色体。这说明由于前置交叉算子的引入，即使个体都相同，仍能够进行迭代进化，跳出局部最优解，从而继续寻找问题的最优解，克服了早熟收敛的缺点。

4实验结果

为了验证混合算法的有效性，通过选用TSPLIB中的Oliver30和att48作为仿真算例，以验证本文提出的算法性能，并与基本遗传算法求解Oliver30和att48TSP进行比较。

基本遗传算法采用文献[6]中的程序和参数，GA的参数为：染色体N=30，Pc=0.2，Pm=0.5，迭代次数为100。对算法预测20次，，结果如表1、表2所示。

从表1及表 2可以看出，采用本文提出的混合算法求解Oliver30和att48，其最优解的质量均有明显的提高。

5 结论

考虑第三方物流企业拥有完成配送服务的所有车辆的情形，即在车场封闭条件下研究大规模的车辆路径问题，从理论上进行深入的研究，构造求解此问题的混合遗传算法，分两阶段对问题进行了求解，第一阶段先采用基于基地启发式分区算法，将零售网点进行区域划分，第二阶段利用优化算法，主要是最近邻算法，遗传算法，和邻域搜索算法，来确定具体的一条配送线路的先后次序，并通过选用TSPLIB中的Oliver30和att48作为仿真算例，以验证本文提出的算法性能。实验结果表明，本文提出的混合遗传算法在求解大规模车辆路径问题中求解效果相对较好。

参考文献：

[1] 郎茂祥，胡思继.用混合遗传算法求解物流配送路径优化问题的研究[J].中国管理科学，2012，10（5）：52-56.

[2] Bramel J，Simehi-Levi D.A location based heuristicb for general routing Problems.Operation Research，1995，（43）： 649-660.

[3] 陶波，朱玉琴.改进的动态规划法在车辆最短路径问题中的应用[J].重庆工学院学报，2011，23（1）：24-27.

[4] 李妍峰，李军，高自友.大规模邻域搜索算法求解时变车辆调度问题[J].管理科学学报，2012，15（1）：22-32.

[5] 代桂平，王 勇，侯亚荣.基于遗传算法的TSP问题求解算法及其系统[J].微计算机信息，2010，26（1）：15-19.

[6] 罗上远，徐天亮，陈代芬.零售业库存分布模型及分区配送算法研究[J].物流技术，2000（5）：22-25.