基于混合蚁群算法的车辆路径问题研究

梁承姬，崔佳诚，丁 一

(上海海事大学 物流研究中心，上海 201306)

基于混合蚁群算法的车辆路径问题研究

梁承姬，崔佳诚，丁 一

(上海海事大学 物流研究中心，上海 201306)

为了求解车辆路径问题，设计了一种结合节约算法和邻域搜索算法的混合蚁群算法，该算法改善了标准蚁群算法搜索时间长、容易陷入局部最优解的问题。首次引入节约算法以提高初始解的质量，使得蚁群算法在较优的路径中进行搜索，从而更有效地收敛到最优解；运用最大最小蚂蚁系统控制路径的信息素，避免算法陷入局部最优解；采用邻域搜索算法优化某阶段最优解的子路径。应用该混合蚁群算法对VRPLIB数据库实例进行了运算，取得了较为满意的结果。

交通运输工程；车辆路径问题；混合蚁群算法；最大最小蚂蚁系统；节约算法；邻域搜索算法

0 引 言

车辆路径问题(vehicle routing problem, VRP)是物流配送优化的基础问题，同时也是提高物流经济效益、事先物流科学化所必不可少的[1]。该问题自问世以来，很快就引起了运筹学、计算机等各学科专家学者的极大关注，成为运筹学以及组合优化领域的前沿和热点问题。车辆路径问题是组合优化领域著名的NP难题(nondeterministic polynomial problem)，求解非常复杂。半个世纪以来，许多学者从车辆路径问题的实际出发，根据不同的目标函数和约束条件，建立了不同的数学模型，也提出了许多不同的算法。盛丽俊等[2]运用遗传算法对VRPTW问题进行求解；吴思等[3]运用PSO算法解决了货物带权重的VRP问题；王志刚等[4]运用人工蜂群算法求解了车辆路径问题；叶开文[5]运用增加反转算子的蚁群算法求解了车辆路径问题；蔡婉君等[6]运用多维信息素和基于扫描法的局部优化方法来提高蚁群算法的性能，求解了车辆路径问题；王仁民等[7]利用变邻域搜索算法对车辆路径问题进行了求解。总的来看，求解车辆路径问题的算法主要有两大类：精确算法和启发式算法[8]。精确算法是根据具体的模型和约束，用运筹学的方法得到精确的结论，精确算法得到的往往是最佳解。启发式算法是凭借着经验和直觉，通过不断的优化，朝着最优解不断靠近或搜索最优解的一种算法。图1是求解车辆路径问题的算法的关系示意。

图1 VRP求解算法Fig.1 Solving algorithm of VRP

蚁群算法(ant colony optimization，ACO) 最先是由意大利学者M.DORIGO提出的一种启发式算法[9]。蚁群算法在提出之初便是用来解决旅行商问题的，蚂蚁沿最优路径觅食和旅行商沿着最优路径推销商品之间有着极强的相似性。而车辆路径问题作为旅行商问题的拓展，自然是最适合用蚁群算法来求解的。故笔者将以蚁群算法为基础对VRP问题进行研究。蚁群算法是一种具有正反馈性的算法。初始时刻各边的信息素是相同的，但只要有一只蚂蚁给予微小的信息素增量，那么各边的信息素浓度就会产生差别，不同的解之间也有了优劣之分，从而较好的路径上会有越来越多的信息素留下，吸引更多的蚂蚁。这个正反馈的过程使得初始解不断朝着最优的方向进化。

然而，标准的蚁群算法在求解中存在搜索容易陷入局部最优解、收敛到全局最优解要花费较长的时间且解的结果容易在局部最优解和全局最优解之间波动的缺点，故笔者将对标准蚁群算法进行改进。首先，通过节约算法，给出问题的初始解，使得信息素仅留在较好的路径上，从而蚁群算法可以更快更有效地收敛到最优解；其次，采用了提高算法性能的最大最小蚂蚁系统；最后，通过邻域搜索算法，对最优解的子路径进行调整。提出的算法能兼顾局部最优和全局最优，具有较强的鲁棒性。

1 VRP数学模型

VRP问题可以描述为有L个客户点，每个客户点的送货量和坐标是已知的，配送中心有K辆车完成这L个客户点的配送任务，完成任务后车辆需要返回配送中心，每辆车有一定的载重上限[10]。要求车辆在完成配送任务的前提下尽可能地节约运输成本，且有以下的约束条件：

1)每段路径上所有客户点的送货量总和不允许超过车辆的最大载重；

2)每段配送路径的总路程长度不允许超过车辆配送的最大行驶距离；

3)每个客户点必须有车辆经过，且只能由一辆车完成其需求。

其目标是使得某个实现设定的目标函数(如距离、成本、时间等)为最小。

图2是一个基本的物流配送示意。假设有1个配送中心、7个客户点、4条行驶路径；其中行驶路径1负责右上方3个客户点的配送，行驶路径2和3分别负责左上方和左下方的客户点，行驶路径4负责右下方2个客户点的配送；这4条行驶路径可以由一辆车分4次进行，也可以由4辆车同时进行；必须满足车辆由配送中心出发、访问完所有的客户点，且最后返回配送中心。

图2 物流配送示意Fig.2 Logistics distribution diagram

符号的定义：L为客户点总数；q(i)为客户点i的货物需求量，单位为t，其中i=1,2,…，n；d(i,j)为客户点i到客户点j的距离，特别地当i，j=0 时，表示配送中心，如d(0,3)表示从配送中心到3号客户点的距离，i,j=0，1，2,…，n；K为总车辆的数目；Qk为车辆k的最大载重，其中k=1，2,…，K；nk为车辆k完成配送的客户总数，当nk=0 时，表示该车没有参与配送；Rk为车辆k配送的客户点的集合，当nk=0 时，Rk为空集；当nk≠0 时，Rk={rk1,rk2,rk3,…}⊆{1,2,…,L}，其中rki表示该客户点在车辆k的行驶路径中的顺序为i，k=1，2 ,…，K。

约束条件：

1)每条线路上的客户点货物重量之和不超过汽车载重量：

(1)

2)每个客户点的货物都要得到送达，只能由一辆汽车来完成：

Rk1∩Rk2=,k1≠k2

(2)

3)行驶路径要求访问所有客户点：

(3)

0≤nk≤L

优化目标函数：

将采用所有车辆的总行驶路径最短为优化目标，最短的路径意味着汽油的节省，车辆的损耗降低，司机疲劳程度的降低，对物流配送来说有着直接的经济意义：

(4)

至此，车辆路径问题的数学模型已经建立完毕，之后的编程以及算法设计都将围绕这一数学模型展开。当式(4)的值S越小时，表明行驶路径越优。

2 基于节约算法和邻域搜索算法的混合蚁群算法

2.1 算法说明

通过节约算法得到问题的较优解，作为蚁群算法初始解的比较对象，当蚁群算法得到的解优于节约算法得到的解时，蚂蚁才会在路径上留下信息素，保证了信息素仅会留在较优的路径上，从而能让蚁群算法更有效地收敛到最优解。而每当有更优解出现时，对该条路径进行邻域搜索，使得所有的客户点以“最优的方式”排列。

2.1.1 节约算法

节约算法运用在车辆路径问题中的基本思路是首先把各个客户点单独与配送中心相连，构成n条“0→i→0”(i=1，2，…，n)初始路线(用双线表示)，第i条线路的物流成本为[11]

Zi=C0i+Ci0

(5)

之后把客户点i和客户点j连接在一起，形成路线“0→i→j→0”(i，j=1，2，…，n)，计算出这两点连接后费用的“节约值”：

s(i,j)=Ci0+C0j-Cij

(6)

s(i，j)越大，说明将客户点i和客户点j连接在一起时节约的总费用越多，因此应优先连接s(i，j)值大的点i和j。根据这一原则，CLARKE和WRIGHT在1964年提出C-K节约算法。图3为典型的节约方案。约定把只有一个客户的线路(如“0→i→0”)称为初始化线路，把包含两个或两个以上客户的线路(如“0→…→i→…→0”)称为已构成线路。

图3 典型的节约方案Fig.3 Typical C-W plan

通过节约算法，得到VRP问题的较优解，并将其作为蚁群算法的初始解，这样可以提高蚁群算法的收敛速度，并保证信息素仅留在较优的路径上，避免算法的停滞。

2.1.2 最大最小蚂蚁系统

最大最小蚂蚁系统(max-min ant system)是德国学者Stützle等提出的一种改进蚁群优化系统。

最大最小蚂蚁系统在蚂蚁系统的基础上有4项主要的改进[12]。

1)每次迭代中，只有最优的蚂蚁才释放出信息素。

2)把信息素的大小限制在一个区间[τmax,τmin]内，这样可以防止某些路径上的信息素增长速度过快从而导致算法可能出现停止的现象，即所有的蚂蚁都在对同一条路径进行搜索，尽管这些路径是较好的路径，却不一定是全局最优的路径。

3)信息素的初始值将设定为其取值范围的上限，并且和一个相对小的信息素蒸发速率相结合，这样可以让算法在最初的搜索步骤中探索更多可能的路径。

4)当系统达到停滞状态或者长时间没有找到更优解的时候，所有信息素的值将被初始化。

2.1.3 邻域搜索算法

蚁群算法在构造最优解时，仅仅得到了最优路径中包含哪些客户点，即“最优解的成分”，然而却不一定是“最优解的排列方式”[13]。最优解的排列方式往往是唯一的，所以蚁群算法直接得到最优解的可能性很低。例如在图4中，各个顶点即是最优路径的成分(客户点)，连线就是不同的排列方式(车辆行驶的路径)。其中图4(a)是算法得到的近似最优解，它包含了最优解需要遍历的客户点，却没有得到最优的行驶路径，图4(b)则是最优解。图4访问了相同的4个客户点，然而，图4(a)的行驶距离却明显大于图4(b)的行驶距离。

图4 邻域搜索算法优化过程Fig.4 Optimization process of local search algorithm

使用的邻域搜索就是将图4(a)的解调整为图4(b)的解的一种方法，确保解的最优性。通过在局部遍历该路径上所有点的排列方式，得到其中最短的一条路径，作为算法的最终结果。

2.2 算法步骤

1)定义参数并设置参数的变量值。首先导入客户点和配送中心的坐标，得到客户的数量，客户点之间的距离和货物需求量。其次设置参数α,β,ρ，在蚁群算法中，参数α,β,ρ对算法的性能有着一定的影响。α表明了每条路径的相对重要性，α的值越大表明蚂蚁选择之前选择过的点的可能性就越高，但α过大会导致搜索陷入局部最优解，从而停滞；β表明能见度的相对重要性，β越大表明选择该路径就越依靠启发信息；ρ表明路径的持久性，可将1-ρ理解为迹衰减度。通常0≤α≤5，1≤β≤5，0.1≤ρ≤0.99，笔者将取α=1，β=2，ρ=0.95。蚂蚁数量一般取为派送点数量的2/3，如总共有15个点的话，那么设置蚂蚁数量为10。

2)设置信息素参数。在最大最小蚂蚁系统中，信息素有最大值τmax和最小值τmin的限制，它们有着τmin=τmax×τrate的关系，其中最大最小信息素的比值为

(7)

式中：p为蚂蚁一次搜索找到最优解的概率，假设p=0.05；Cn为配送中心和客户点的总数量。

信息素最大最小值在初始的时候设置成多大无所谓，因为第一次搜索完会生成一个最优解，然后用这个解重新产生最大最小值。不妨设τmax=1，则τmin=τmax×τrate。信息素更新规则为只有全局最优的蚂蚁才释放信息素：

(8)

式中：Lb为最优蚂蚁行驶过的路径的长度，所以增加的信息素为距离的倒数；ρ为信息素的挥发。

同时更新信息素最大值和信息素最小值：

(9)

τmin=τmax×τrate

(10)

3)通过节约算法得到问题较优解，作为蚁群算法初始值Lb，并得到初始的最优路径长Lb。

4)fori=1 tok，第n只蚂蚁开始进行搜索。

5)根据概率公式：

式中：ηij(t)=1/dij。

求得第k只蚂蚁的转移概率p(i,j)，找到蚂蚁k下一个要走的点j。

6)计算i和j连接后线路上的总货运量Q，若Q≤VW(车辆最大容量)，则转到步骤5)，蚂蚁继续选择下一个要去的客户点；否则蚂蚁回到配送中心，表示这辆车已经完成配送任务，不能再承担更多重量的货物运输，之后再从配送中心重新出发，转到步骤5)，寻找下一个要去的客户点。

7)当蚂蚁访问完所有的客户点后，记录其走过的路径到path表中，并计算走过的路径长度L，与当前最优路径Lb比较，若L

8)k=k+1，若还有蚂蚁没进行搜索，则转到步骤4)；当全部蚂蚁遍访完所有客户点后转到步骤9)。

9)按照式(7)～式(10)更新各边的信息素。

10)判断是否超过设定迭代次数而没有产生更优解，否的话直接转到步骤11)，是的话初始化信息素并转到步骤11)。

11)I(迭代次数)=I+1，当完成预定迭代次数的搜索后，跳出并打印最优路径；否则转到步骤4)开始下一次迭代。

3 计算实例与结果分析

3.1 计算实例1

为了便于分析和比较，选用文献[14]的第一个VRP实例进行试算。其中，车容量为8 t，问题规模为21(20个客户点加上一个配送中心)，其基础数据如表1，配送中心位于坐标点(52,4)，设置蚁群算法参数α=1，β=2，ρ=0.95。表2为本文算法和其他各算法的比较。

表1 客户及配送中心数据

表2 各算法比较

由表2可见，本文算法得到的最优解为828.897，优于文献[14]中列出的最优解846.785，多次运算的平均值也明显优于文献中的平均解，最优路径经过验证是可行的。且由图5可见，算法收敛速度很快。

图5 算法收敛图Fig.5 Algorithm convergence diagram

3.2 计算实例2

为了进一步验证算法的有效性，采用了国际公认的VRP算例库VRPLIB中的经典算例，经大量运行测试，得到了较好的结果。限于篇幅，仅给出E-n22-k4，E-n30-k3，E-n51-k5，3个算例的结果，见表3。设置蚁群算法参数α=1，β=2，ρ=0.95。对VRPLIB中算例进行计算时，大部分算例达到了最优解，少部分甚至改进了最优解，也有一部分解比已知最优解稍差一些。表3给出了有代表性的3个算例。其中E-n22-k4达到了已知最优解，且得到了和已知最优路径相同的路径；E-n30-k3得到了更优于已知最优解的结果，但略有不足的是车辆数从3辆增加到了4辆，但行驶距离比已知最优解更短；E-n51-k5得到的解比已知最优解稍差一些，但偏差仅为1.5%，在可接受范围之内。由此可见，笔者提出的算法是一种有效的混合算法。

表3 VRPLIB中问题的计算结果

Table 3 Calculation results of the problems in VRPLIB

4 结 语

笔者提出一种混合蚁群算法，该算法将蚁群算法和节约算法相结合，控制初始阶段信息素仅留在较优路径上，增强了蚁群算法的寻优能力，引入最大最小蚂蚁系统的局部改进机制，防止了算法陷入局部最优解。仿真实验及其对比结果表明，本算法能有效得到问题的最优解，具有较强的寻优能力。不过笔者仅考虑了基础的VRP问题，对于一些复杂的VRP问题(如带时间窗的VRPTW问题)，本文算法能否得到满意的结果，有待进一步研究。

[1] 马良,朱刚,宁爱兵.蚁群优化算法[M].北京:科学出版社,2008:9-18,85. MA Liang,ZHU gang,NING Aibing.AntColonyOptimization[M]. Beijing: Science Press,2008:9-18,85.

[2] 盛丽俊,周溪召.带有时间窗的车辆路径问题优化[J].上海海事大学学报,2007,28(4):64-67. SHENG Lijun,ZHOU Xizhao. Vehicle routing problem optimization with time windows[J].JournalofShanghaiMaritimeUniversity,2007,28(4):64-67.

[3] 吴思,丁以中.计重收费政策下的货物权重车辆路径[J].上海海事大学学报,2010,31(3):22-26. WU Si,DING Yizhong. Weighted vehicle routing problem under toll-by-weight policy[J].JournalofShanghaiMaritimeUniversity,2010,31(3):22-26.

[4] 王志刚,夏慧明.求解车辆路径问题的人工蜂群算法[J].计算机工程与科学,2014,36(6):1088-1094. WANG Zhigang,XIA Huiming. An artificial bee colony algorithm for the vehicle routing problem[J].ComputerEngineering&Science,2014,36(6):1088-1094.

[5] 叶开文.基于群体智能的车辆路径问题研究[D].西安:西安电子科技大学,2014. YE Kaiwen.ResearchontheVehicleRoutingProblemBasedonSwarmIntelligenceOptimization[D]. Xi’an: Xi’an Electronic and Science University,2014.

[6] 蔡婉君,王晨宇,于滨,等.改进蚁群算法优化周期性车辆路径问题[J].运筹与管理,2014,23(5):70-77. CAI Wanjun,WANG Chenyu,YU Bin,et al.Improved ant colony algorithm for period vehicle routing problem[J].OperationsResearchandManagementScience,2014,23(5):70-77.

[7] 王仁民,闭应洲,刘阿宁,等.改进变邻域搜索算法求解动态车辆路径问题[J].计算机工程与应用,2014,50(2):237-241. WANG Renmin,BI Yingzhou,LIU A′ning,et al. Improved variable neighbourhood search algorithm for DVRP[J].ComputerEngineeringandApplications,2014,50(2):237-241.

[8] 蒋波.基于遗传算法的带时间窗车辆路径优化问题研究[D].北京:北京交通大学,2010. JIANG Bo.StudyofVehicleRoutingProblemwithTimeWindowsBasedonGeneticAlgorithm[D].Beijing: Beijing Jiaotong University,2010.

[9] DORIGO M,MANIEZZO V,COLORNI A. The ant system: optimization by a colony of cooperating Agents[J].IEEETransonSystems,Man,andCybernetics-PartB,1996,26(1):29-42.

[10] 于芹.基于蚁群算法的物流车辆路径优化问题的研究[D].上海:上海交通大学,2007. YU Qin.VehicleRoutingOptimizationProblemsinLogisticsBasedonAntColonyAlgorithm[D].Shanghai: Shanghai Jiaotong University,2007.

[11] 缪兴锋,秦明森.物流运筹学方法[M].广州:华南理工大学出版社,2007:101-102. MIU Xingfeng,QIN Mingsen.LogisticsOperationalResearchMethods[M].Guangzhou: South China University of Technology Press,2007:101-102.

[12] 段海滨.蚁群算法原理及其应用[M].北京:科学出版社,2005:33-38. DUAN Haibin.ThePrincipleofAntColonyAlgorithmandItsApplication[M].Beijing: Science Press,2005:33-38.

[13] 李娅,王东.基于混沌扰动和邻域交换的蚁群算法求解车辆路径问题[J].计算机应用,2013,32(2):444-447. LI Ya,WANG Dong. Ant colony optimization algorithm based on chaotic disturbance and neighborhood exchange for vehicle routing problem[J].JournalofComputerApplications,2012,32(2):444-447.

[14] 程勇.物流车辆路径问题的混合快速蚂蚁算法[J].工业工程与管理,2007(4):15-19. CHENG Yong. Hybrid fast ant algorithm for vehicle routing problem [J].IndustrialEngineeringandManagement,2007(4):15-19.

Vehicle Routing Problem Based on Hybrid Ant Colony Algorithm

LIANG Chengji, CUI Jiacheng, DING Yi

(Logistics Research Center, Shanghai Maritime University, Shanghai 201306, P.R.China)

In order to solve the vehicle routing problem (VRP), a new ant colony algorithm based on C-W saving algorithm and local search algorithm was proposed. The hybrid algorithm solved the problem of the standard ant colony algorithm to search for a long time and easy to fall into the local optimal solution. Firstly, C-W saving algorithm was introduced to improve the quality of the initial solution, which made the ant algorithm search in a better way, so it could converge to the optimal solution more effectively. And then, the pheromone of path was controlled by using max-min ant system (MMAS), which avoided the local optimal solution of the algorithm. Finally, the sub-path of optimal solution for a certain stage was optimized by using local search algorithm. The proposed hybrid ant colony algorithm was used to calculate the examples in VRPLIB database, and achieved the satisfactory results.

traffic and transportation engineering; vehicle routing problem; hybrid ant colony algorithm; max-min ant system; C-W saving algorithm; local search algorithm

10.3969/j.issn.1674-0696.2016.03.20

2014-10-28；

2015-05-04

国家自然科学基金项目(71471110,71301101)

梁承姬(1970—)，女(朝鲜族)，吉林龙井人，教授，博士，主要从事集装箱港口物流方面的研究。E-mail:liangcj@shmtu.edu.cn。

崔佳诚(1991—)，男，上海人，硕士研究生，主要从事车辆路径及港口集卡调度方面的研究。E-mail:tracymcgrady 06675@126.com。

U116.2

A

1674-0696(2016)03-094-06