[1]刘万峰,李霞.车辆路径问题的快速多邻域迭代局部搜索算法[J].深圳大学学报理工版,2015,32(No.2(111-220)):196-204.[doi:10.3724/SP.J.1249.2015.02000]
 Liu Wanfeng,and Li Xia,A fast multi-neighborhood iterated local search algorithm for vehicle routing problem[J].Journal of Shenzhen University Science and Engineering,2015,32(No.2(111-220)):196-204.[doi:10.3724/SP.J.1249.2015.02000]
点击复制

车辆路径问题的快速多邻域迭代局部搜索算法()
分享到:

《深圳大学学报理工版》[ISSN:1000-2618/CN:44-1401/N]

卷:
第32卷
期数:
2015年No.2(111-220)
页码:
196-204
栏目:
电子与信息科学
出版日期:
2015-03-20

文章信息/Info

Title:
A fast multi-neighborhood iterated local search algorithm for vehicle routing problem
文章编号:
201502012
作者:
刘万峰12李霞12
1)深圳大学信息工程学院,深圳 518060
2)深圳市现代通信与信息处理重点实验室,深圳 518060
Author(s):
Liu Wanfeng1 2 and Li Xia1 2
1) College of Information Engineering, Shenzhen University, Shenzhen 518060, P.R.China
2) Shenzhen Key Lab of Communication and Information Processing, Shenzhen 518060, P.R.China
关键词:
人工智能启发式算法车辆路径问题多邻域迭代局部搜索可变长编码
Keywords:
artificial intelligence heuristic algorithms vehicle routing problem multi-neighborhood iterated local search variable length coding
分类号:
TP 391
DOI:
10.3724/SP.J.1249.2015.02000
文献标志码:
A
摘要:
对于容量约束的车辆路径问题 (capacitated vehicle routing problem,CVRP)以及容量和最大行驶距离约束的车辆问题(capacitated and distance constrained vehicle routing problem,CDVRP) ,邻域解的评估包含了适应值计算及合法性评估.设计一种可变长编码的可行解表示,提出用于CVRP/CDVRP问题的邻域解合法性快速评估策略.该策略针对交换、插入、2-opt和2-opt*四种常用的局部搜索算子,通过引入前载重、后载重、前向距离和后向距离的概念,实现了邻域解合法性的快速评估.将改进后的局部搜索算子与迭代局部搜索(iterated local search, ILS)算法相结合,提出用于车辆路径问题的快速多邻域迭代局部搜索(fast multi-neighborhood ILS,FMNILS)算法.该快速评估策略将评估一个邻域解的时间复杂度由O(N)降至O(1),算法仿真结果表明,FMNILS算法运算能力的提高大致与配送路线所服务的客户数成正比;对客户数介于200~500的容量/最大距离约束VRP问题,该算法能在短时间内获得较满意解,平均求解精度1.2%以内,平均耗时约96 s,仅为对比算法的6%或更少.
Abstract:
For capacitated vehicle routing problems without/with maximum traveling distance constraint (CVRP/CDVRP), the evaluation of neighborhood solutions involves fitness calculation and feasibility assessment. This paper proposes a fast feasibility assessment strategy in which variable length coding is used to represent feasible solutions of vehicle routing problem. We introduce the concepts of pre-load, post-load, pre-distance and post-distance to obtain fast feasibility assessments for neighborhood solutions achieved by four widely used local search operations (insert, exchange, 2-opt, and 2-opt*). By combining the improved local search operations and iterated local search (ILS), we propose a fast multi-neighborhood iterated local search (FMNILS) for CVRP. The feasibility assessment strategy can reduce computational complexity of the neighborhood solution assessment from O(N) to O(1). Experimental results show that the improvement in speed is approximately linearly proportional to the average customer number in a route. For CVRP/CDVRP problems with 200—500 customers, the algorithm can give satisfactory solutions with an average deviation of less than 1.2%. The average running time is 96 seconds, which is 6% of the time required for the counterpart algorithms, or even less.

参考文献/References:

[1] Laporte G,Toth P,Vigo D.Vehicle routing:historical perspective and recent contributions[J].EURO Journal on Transportation and Logistics,2013,2(1/2):1-4.
[2] Baldacci R,Mingozzi A,Roberti R.Recent exact algorithms for solving the vehicle routing problem under capacity and time window constraints[J].European Journal of Operational Research,2012,218(1):1-6.

[3] Chen Ping,Huang Houkuan,Dong Xieye.Iterated variable neighborhood descent algorithm for the capacitated vehicle routing problem[J].Expert Systems with Applications, 2010,37(2):1620-1627.
[4] Subramanian A,Uchoa E,Satoru Ochi L.A hybrid algorithm for a class of vehicle routing problems[J].Computers & Operations Research,2013,40(10):2519-2531.
[5] Subramanian A.Heuristic, exact and hybrid approaches for vehicle routing problems[D].Niterói(Brazil):Universidade Federal Fluminense,2012.
[6] Li Feiyue,Golden B,Wasil E.Very large-scale vehicle routing: new test problems, algorithms, and results[J].Computers & Operations Research,2005,32(5):1165-1179.
[7] Luo Jianping,Li Xia, Chen Minrong. Improved shuffled frog leaping algorithm for solving CVRP[J].Journal of Electronics & Information Technology,2011,33(2):429-434.(in Chinese)
骆剑平,李霞,陈泯融.基于改进混合蛙跳算法的CVRP求解[J]. 电子与信息学报,2011,33(2):429-434.
[8] Wink S,Back T,Emmerich M.A meta-genetic algorithm for solving the capacitated vehicle routing problem[C]// IEEE Congress on Evolutionary Computation(CEC). Brisbane(Australia): IEEE Press,2012:1-8.
[9] Zachariadis E E,Kiranoudis C T.A strategy for reducing the computational complexity of local search-based methods for the vehicle routing problem[J].Computers & Operations Research, 2010, 37(12):2089-2105.
[10] ChrisGror C,Golden B,Wasil E.A parallel algorithm for the vehicle routing problem[J].INFORMS Journal on Computing,2011,23(2):315-330.
[11] Jin J,Crainic T G,Lkketangen A.A parallel multi-neighborhood cooperative tabu search for capacitated vehicle routing problems[J].European Journal of Operational Research,2012,222(3):441-451.
[12] Ishibuchi H,Yoshida T,Murata T.Balance between genetic search and local search in memetic algorithms for multiobjective permutation flowshop scheduling[J].IEEE Transactions on Evolutionary Computation,2003,7(2):204-223.
[13] Baum E B.Towards practical ‘neural’ computation for combinatorial optimization problems [C]//AIPConference Proceedings 151 on Neural Networks for Computing.Snowbird Utah(USA):AIP Publishing LLC,1986:53-58.
[14] Nguyen H D,Yoshihara I,Yamamori K,et al.Implementation of an effective hybrid GA for large-scale traveling salesman problems[J].IEEE Transactions on Systems,Man,and Cybernetics,Part B:Cybernetics,2007,37(1):92-99.
[15] Christofides N,Eilon S.An algorithm for the vehicle-dispatching problem[J].Operational Research Society,1969,20(3):309-318.
[16] Crainic T G,Laporte G.Fleet management and logistics[M].Berlin:Springer,1998.

相似文献/References:

[1]潘长城,徐晨,李国.解全局优化问题的差分进化策略[J].深圳大学学报理工版,2008,25(2):211.
 PAN Chang-cheng,XU Chen,and LI Guo.Differential evolutionary strategies for global optimization[J].Journal of Shenzhen University Science and Engineering,2008,25(No.2(111-220)):211.
[2]胡明伟,唐浩.时相关旅行时间车辆路径高效启发式算法[J].深圳大学学报理工版,2009,26(3):315.
 HU Ming-wei and TANG Hao.Efficient heuristics for vehicle routing problems with time-dependent travel times[J].Journal of Shenzhen University Science and Engineering,2009,26(No.2(111-220)):315.
[3]骆剑平,李霞.求解TSP的改进混合蛙跳算法[J].深圳大学学报理工版,2010,27(2):173.
 LUO Jian-ping and LI Xia.Improved shuffled frog leaping algorithm for solving TSP[J].Journal of Shenzhen University Science and Engineering,2010,27(No.2(111-220)):173.
[4]胡明伟,唐浩.动态车辆路径问题的多目标优化模型与算法[J].深圳大学学报理工版,2010,27(2):230.
 HU Ming-wei and TANG Hao.Multi-objective optimization model of dynamic vehicle routing problem[J].Journal of Shenzhen University Science and Engineering,2010,27(No.2(111-220)):230.
[5]蔡良伟,李霞.基于混合蛙跳算法的作业车间调度优化[J].深圳大学学报理工版,2010,27(4):391.
 CAI Liang-wei and LI Xia.Optimization of job shop scheduling based on shuffled frog leaping algorithm[J].Journal of Shenzhen University Science and Engineering,2010,27(No.2(111-220)):391.
[6]张重毅,刘彦斌,于繁华,等.CDA市场环境模型进化研究[J].深圳大学学报理工版,2010,27(4):413.
 ZHANG Zhong-yi,LIU Yan-bin,YU Fan-hua,et al.Research on the evolution model of CDA market environment[J].Journal of Shenzhen University Science and Engineering,2010,27(No.2(111-220)):413.
[7]姜建国,周佳薇,郑迎春,等.一种双菌群细菌觅食优化算法[J].深圳大学学报理工版,2014,31(No.1(001-110)):43.[doi:10.3724/SP.J.1249.2014.01043]
 Jiang Jianguo,Zhou Jiawei,Zheng Yingchun,et al.A double flora bacteria foraging optimization algorithm[J].Journal of Shenzhen University Science and Engineering,2014,31(No.2(111-220)):43.[doi:10.3724/SP.J.1249.2014.01043]
[8]蔡良伟,刘思麒,李霞,等.基于蚁群优化的正则表达式分组算法[J].深圳大学学报理工版,2014,31(No.3(221-330)):279.[doi:10.3724/SP.J.1249.2014.03279]
 Cai Liangwei,Liu Siqi,Li Xia,et al.Regular expression grouping algorithm based on ant colony optimization[J].Journal of Shenzhen University Science and Engineering,2014,31(No.2(111-220)):279.[doi:10.3724/SP.J.1249.2014.03279]
[9]宁剑平,王冰,李洪儒,等.递减步长果蝇优化算法及应用[J].深圳大学学报理工版,2014,31(No.4(331-440)):367.[doi:10.3724/SP.J.1249.2014.04367]
 Ning Jianping,Wang Bing,Li Hongru,et al.Research on and application of diminishing step fruit fly optimization algorithm[J].Journal of Shenzhen University Science and Engineering,2014,31(No.2(111-220)):367.[doi:10.3724/SP.J.1249.2014.04367]
[10]蔡良伟,程璐,李军,等.基于遗传算法的正则表达式规则分组优化[J].深圳大学学报理工版,2015,32(No.3(221-330)):281.[doi:10.3724/SP.J.1249.2015.03281]
 Cai Liangwei,Cheng Lu,Li Jun,et al.Regular expression grouping optimization based on genetic algorithm[J].Journal of Shenzhen University Science and Engineering,2015,32(No.2(111-220)):281.[doi:10.3724/SP.J.1249.2015.03281]

备注/Memo

备注/Memo:
基金项目:国家自然科学基金资助项目( 61171124),深圳市基础研究计划资助项目(JC201105170613A)
作者简介:刘万峰(1974—),男(汉族),广东省兴宁市人,深圳大学博士研究生.E-mail:liuwf@163.com
引文:刘万峰,李霞.车辆路径问题的快速多邻域迭代局部搜索算法[J]. 深圳大学学报理工版,2015,32(2):196-204.
Received:2014-06-11;Revised:2015-02-06;Accepted:2015-02-28
Foundation:National Natural Science Foundation of China (61171124); Shenzhen Key Project for Foundation Research (JC201105170613A)
Corresponding author:Professor Li Xia. E-mail: lixia@szu.edu.cn
Citation:Liu Wanfeng,Li Xia.A fast multi-neighborhood iterated local search algorithm for vehicle routing problem[J]. Journal of Shenzhen University Science and Engineering, 2015, 32(2): 196-204.(in Chinese)
更新日期/Last Update: 2015-03-12