基于捕食搜索策略混合遗传算法的车辆路径问题研究

林 涛，武孟贤，轩倩倩，徐庆国，江 冲

(1 河北工业大学 控制科学与工程学院,天津 300130;2 河北工业大学 计算机科学与软件学院,天津 300401)

基于捕食搜索策略混合遗传算法的车辆路径问题研究

林 涛1,2，武孟贤1,*，轩倩倩1，徐庆国1，江 冲1

(1 河北工业大学 控制科学与工程学院,天津 300130;2 河北工业大学 计算机科学与软件学院,天津 300401)

在分析研究车辆路径问题的基础上，将其转换为经典TSP优化问题进行求解并建立数学模型,针对遗传算法在求解车辆路径问题时搜索效率低，容易陷入局部最优的缺点，提出了一种改进的遗传算法.改进算法引用自适应邻域法进行种群初始化；基于捕食搜索策略动态自适应调整遗传参数，在加快寻优速度的同时防止陷入局部最优；交叉前后的种群分别实施精英个体保留策略，交叉变异之后引进进化逆转操作，继承父代较优和较多的信息.实验结果表明：改进遗传算法搜索效率高、计算结果较为稳定；求解车辆路径最优问题较其它算法具有较好的性能.

车辆路径问题；遗传算法；自适应邻域法；捕食搜索算法

作为物流运输配送系统的核心问题，车辆路径问题(VRP)主要研究车辆从配送中心到各客户点配送最后返回配送中心的满足约束条件的最优车辆使用方案以及最优车辆路线方案[1].该问题是一个典型的NP-hard(NP难)问题，自提出以来一直受到众多专家和学者的关注，在理论研究和现实应用上均取得了丰硕的研究成果.神经网络、模拟退火、遗传算法、蚁群算法、粒子群算法等智能算法都已实现了对该NP难题的求解[2].

近年来，随着我国电子商务行业的高速发展，使得物流配送业务大量增加，企业的配送车辆数目迅猛增多.不合理的配送路线不仅增加了企业的配送成本,同时还影响了城市的交通和环境[3].求解最优路径时许多算法的搜索效率和解的质量不高，所以许多学者为了使算法同时兼顾时间和效率的要求，继续对启发式智能算法进行了优化改进[4].文献[5]将贪婪算法引入到遗传算法来初始化种群，采用基于贪婪算法的启发式交叉算子来求解旅行商问题；文献[6]将侦察特性引用到蚁群优化算法来提高算法的有效性和适用性.文献[7]基于K-means算法提出了一种新的初始种群策略来改善遗传算法求解组合优化问题.

为了更好地实现对VRP问题的求解，本文将其转换为经典TSP优化问题进行求解并建立数学模型.由于遗传算法是求解TSP优化问题的强大搜索方法，本文基于该数学模型对遗传算法进行改进来提高算法的寻优性能.

1 VRP问题描述及模型

一般的车辆路径问题可以描述为：配送中心和客户点用i,j表示；车辆用k表示，最多拥有m辆；配送中心编号为0，客户点集合N0=1,2,3,…,n}；其中客户需求量为gi(i=1,2,3,…,n)，车辆的载重量为qk(k=1,2,3,…,m)，配送车辆最后都返回配送中心；求满足需求的最小成本的车辆路径R=(c0,c1,c2,…,cn).

为了得到合理的车辆使用和路线方案，本文对所需要的车辆数目进行预估，按照下面的公式(1)来确定车辆数m：

(1)

其中,⎣」表示括号内数字的向下取整；qmin表示最小载重量车辆的载重量；0<α<1，它是卸车复杂程度和约束多少估计的参数.可以根据实际情况调整α的大小.

对VRP问题建立数学模型如下.

定义决策变量：

目标函数：

(2)

约束条件:

(3)

(4)

(5)

(6)

(7)

(8)

上述模型中，cij可以是从客户点i到j的距离、费用、时间等；K表示所有车辆的集合，N0表示所有客户的集合.式(3)约束使用车辆数小于车辆总数；式(4)约束车辆行驶路线都是环线；式(5)约束每条服务路线上的需求总量小于车辆载重；式(6)约束所有客户点都能被配送；式(7)和式(8)约束一个客户点仅被一辆车配送.

2 改进的遗传算法

遗传算法是一种求解组合优化问题的强大搜索方法，它是根据适应度值按照“优胜劣汰”的自然规则来逐代全局遍历的寻优方法[8].标准遗传算法包括种群初始化，计算种群中个体适应度，选择操作，交叉操作，变异操作，终止条件判断等基本操作.标准遗传算法的搜索效率和优化精度不高，且容易陷入局部最优，所以遗传算法需要不断改进来满足时间和效率的同时，使得寻优结果更接近最优.

2.1 基于自适应邻域法生成初始种群

初始种群常常影响遗传算法解的质量和算法的效率；复杂组合优化问题使用随机方法生成的初始种群，搜索空间大、时间长，且容易出现早熟收敛.为了克服这些问题，本文引用一种初始化种群策略来改善遗传算法，采用自适应邻域法生成遗传算法的初始种群.自适应邻域法是从一个点出发，随机选取比其最近点稍远的邻域范围内的点作为下一点并作为当前点，继续搜索添加未加入的点，直至遍历完所有的点，由此得到初步优化的个体.实验结果得出，自适应邻域算法生成的初始种群即不失随机性，又提高了初始种群的质量，可以改善算法的收敛速度.

2.2 基于捕食搜索策略的自适应参数

标准遗传算法采用固定的交叉概率Pc和变异概率Pm，限制了算法的搜索性能.许多专家学者研究自适应的遗传概率Pc和Pm，可以在种群进化过程中自动调整遗传概率的大小.交叉算子和变异算子分别决定算法的全局和局部搜索能力，因此Pc和Pm的选择关系到遗传算法的搜索效率和群体多样性.

为了合理的选择Pc和Pm，本文引入平衡全局搜索能力和局部寻优能力的捕食搜索策略[9]，运用捕食搜索策略改进遗传算法，形成自适应的遗传算法.根据种群进化代数和适应度值的变化，动态自适应调整Pc和Pm的值.进化过程类似于动物的捕食过程，先进行全局搜索，即选择较大Pc的和较小的Pm，一旦发现较好的解，则改为集中的局部搜寻，即选择较小Pc的和较大的Pm，希望得到更好的解来提高群体的多样性.如果最优解得不到改善，则放弃局部搜索继续进行全局搜索.Pc1和Pm1随着进化代数动态改变：

其中：i代表进化代数；总进化代数为M.

实际应用中，结合进化代数、适应度值的变化来动态调整参数Pc和Pm.全局最优的适应度值为gbest，局部最优(当代最优)的适应度值为fbest，根据两者的比值g=fbest/gbest来调整遗传参数，其中Pc2和Pm2为实际问题设定的遗传参数，k的取值根据实际情况选定，k的取值越小局部搜索的次数越多.

2.3 精英策略

采用精英策略和轮盘赌选择法来进行选择操作，选择适应度值最高的个体复制到交叉配对的父代群体中.当父代执行完交叉变异算子之后，使用精英策略，用父代中的精英个体替换子代中适应度最低的个体，使得父代的好的个体不至于随着进化操作而丢失.

2.4 进化逆转操作

交叉算子在进化过程中可以保持种群的多样性，但是它不利于子代继承父代较多的信息，特别是进化后期交叉操作对父代较优基因的破坏较大，使得父代的一些优良基因难以被继承.本文对发生交叉、变异操作之后的个体使用进化逆转操作，可以继承父代较多的信息，使得搜索最优解的能力变强.“进化”指逆转操作后可以提高适应度值的个体才接受逆转.

逆转操作如下：随机的选择染色体中的两个位置a和b，对选中位置之间基因实施逆转，如a=3,b=7

5 2 |3 8 9 6 7 |4 1

逆转后为：

5 2 |7 6 9 8 3 |4 1

2.5 改进遗传算法求解VRP问题

基于上述改进分析，本文设计的改进遗传算法求解VRP问题步骤如下.

Step 1：确定编码方式，基于自适应邻域算法生成初始种群.求解VRP问题通常采用客户点序列编码方式生成染色体，并设置算法运行的参数.

Step 2：计算种群中个体的适应度值.较大的适应度值代表较优的路径，适应函数一般选用Fitness(i)=D/f(Ri).常数D保证适应度值不会太小.

Step 4：终止条件.判断进化代数是否达到最大代数，达到则停止迭代，得到的最优个体被认为是最优路径；否则进化代数加1，转Step 2循环操作.

Step 5：最优个体(染色体)分割得到最优车辆使用方案和最优路线方案.

3 实验分析

根据上述改进遗传算法求解车辆路径问题的步骤，设计算法的基本流程如图1所示.

图1 改进遗传算法流程图Fig.1 Improved genetic algorithm flow chart

3.1 实验结果分析

为了验证改进算法的性能，采用Matlab对其进行仿真实验.根据某物流公司实际业务情况其拥有一个配送中心，配送车辆的载重量相同，随机抽取该公司的一次配送订单数据，该订单共拥有13个客户点，为方便计算将各客户点实际地理位置按照一定比例缩小到xy坐标系下.配送中心与客户点的位置坐标如表1所示，客户点0即配送中心.本实例中使用相同载重量车辆，车辆载重量为10t；改进算法参数设置为：初始种群大小为100，最大迭代次数为200， K=1.5Pc max=0.95Pc min=0.4Pm max=0.1Pm min=0.01.

表1 配送中心与客户点坐标

预估使用4辆配送车辆，通过使用本文方法运行10次，得到14个坐标点TSP问题的最优解为：12→6→11→5→4→3→2→13→1→0→9→8→10→7→12，总距离：29.3405.根据车辆载重解码可以得到4条最优配送路线：

路径1：0→9→8→10→11→4→0

路径2：0→7→12→6→0

路径3：0→5→3→13→0

路径4：0→2→1→0

实验计算结果如表2所示.

表2 实验结果

从表2中实验结果可以看出，本文方法计算效率高，结果较为稳定，能够较好的解决其它算法搜索效率低的问题.

3.2 改进算法性能分析

采用标准遗传算法(GA)、自适应遗传算法(AGA)、蚁群算法(ACA)、混合粒子群算法(HPSO)对本文示例进行仿真，迭代200次得到的结果如表3所示.

表3 各种算法计算结果

各算法程序仿真的优化过程与改进遗传算法的仿真过程比较如图2～5所示.

图2 标准遗传算法与本文改进算法的迭代曲线Fig.2 The iterative curve of standard GA and improved GA

图3 自适应遗传算法与本文改进算法的迭代曲线Fig.3 The iterative curve of adaptive GA and improved GA

图4 蚁群算法与本文改进算法的迭代曲线Fig.4 The iterative curve of ACA and improved GA

图5 混合粒子群与本文改进算法的迭代曲线Fig.5 The iterative curve of HPSO and improved GA

由表3可见，本文所改进算法求解配送VRP问题时在最优距离、迭代次数、时间上优于其它算法.遗传算法、蚁群算法、混合粒子群算法虽然可以在短时间内找到较优路线，但是容易陷入局部最优.通过图2～5比较还发现，本文的改进遗传算法能够加快进化初期的寻优速度，减少迭代次数，可以在更短的时间内找到最优解，而且计算结果较为稳定.

由于本实验所用数据为某公司产生的实际数据，而且是随机抽取的结果，所以对该类实际问题具有一定的普遍应用性.

4 结语

车辆路径问题是一个难以求出其精确解的经典NP难题，本文设计了一种改进的遗传算法来对其进行求解.利用自适应邻域法的局部寻优能力来改善算法的初始种群，加快寻优速度；基于捕食搜索策略对遗传概率进行动态自适应调整，平衡算法的全局搜索能力和局部搜索能力.为了保持种群的多样性，交叉前后分别实施轮盘赌策略选择和精英策略保留，交叉变异操作之后实施进化逆转操作.实验结果表明，新算法的对问题的寻优质量和效率均优于其它几种智能优化算法.后续对VRP问题的研究将会考虑更多的约束条件，同时加大种群规模来验证算法的有效性.

[1] Kim G, Ong Y S, Heng C K, et al. City vehicle routing problem : a review[J]. IEEE Transactions on Intelligent Transportation Systems, 2015(16):1-13.

[2] 罗 勇,陈治亚.基于改进遗传算法的物流配送路径优化[J].系统工程,2012(08):118-122.

[3] 邵丽丽.蚁群优化自适应遗传算法物流车辆调度实现[J].计算机测量与控制,2012(05):1423-1425+1441.

[4] 张小琴.联合贝叶斯推理与遗传算法的主题信息搜索策略[J].中南民族大学学报(自然科学版), 2014(02):89-92.

[5] 于莹莹,陈 燕,李桃迎. 改进的遗传算法求解旅行商问题[J]. 控制与决策,2014(08):1483-1488.

[6] Gan R, Guo Q, Chang H, et al. Improved ant colony optimization algorithm for the traveling salesman problems[J]. Journal of Systems Engineering and Electronics, 2010, 21(2): 329-333..

[7] Deng Y, Liu Y, Zhou D. An Improved Genetic Algorithm with Initial Population Strategy for Symmetric TSP[J]. Mathematical Problems in Engineering, 2015(03):1-6.

[8] Contrerasbolton C, Parada V. Automatic Combination of Operators in a Genetic Algorithm to Solve the Traveling Salesman Problem.[J]. Plos One, 2015, 10(9).

[9] 王萍萍,陈进东,潘 丰.采用捕食搜索策略的遗传算法改进[J].东南大学学报(自然科学版),2010(S1):223-227.

Hybrid Genetic Algorithm Based on Predatory Search Strategy for Vehicle Routing Problem

Lin Tao1,2, Wu Mengxian1, Xuan Qianqian1, Xu Qingguo1, Jiang Chong1

(1 Institute of Control Science and Engineering, Hebei University of Technology, Tianjin 300130,China;2 Institute of Computer Science and Software, Hebei University of Technology, Tianjin 300401,China)

On the basis of the analysis of the vehicle routing problem, it is transformed into the classical TSP optimization problem to solve and build a mathematical model. Standard genetic algorithm in solving the vehicle routing problem (VRP) is not efficient since it is easy to fall local optimum. To improve the efficiency of genetic algorithm, this paper presents an improved genetic algorithm. The proposed algorithm introduces the adaptive neighborhood method into population initialization. In order to improve the optimization speed and prevent the local optimum, the improved algorithm dynamic adaptive adjustment of genetic parameters based on predatory search strategy. Elite individual retention strategy is introduced to genetic operation and evolutionary reversal operation is used after crossover and mutation operation to propagate the better and more gene structure. The experimental results show that the improved genetic algorithm has high search efficiency and stable calculation results, and it has better performance than other algorithms in case of solving the vehicle routing problem.

vehicle routing problem; genetic algorithm; adaptive neighborhood method ; predatory search algorithm

2016-06-10 *通讯作者 武孟贤，研究方向：计算机网络控制、人工智能，E-mail:724996875@qq.com

林 涛(1970-)，男，教授，博士,研究方向：计算机网络控制理论、网络管理与安全、嵌入式系统及网络控制,E-mail: lintao@scse.hebut.edu.cn

天津市科技支撑项目( 14ZCDZGX00818)

TP399

A

1672-4321(2016)04-0106-05