求解车辆路径问题的改进扰动机制的ILS算法

doi:10.11896/j.issn.1002-137X.2016.01.057

计算机科学 ›› 2016, Vol. 43 ›› Issue (1): 264-269.doi: 10.11896/j.issn.1002-137X.2016.01.057

求解车辆路径问题的改进扰动机制的ILS算法

侯彦娥,孔云峰,党兰学

河南大学黄河中下游数字地理技术教育部重点实验室开封475004;河南大学计算机与信息工程学院开封475004,河南大学黄河中下游数字地理技术教育部重点实验室开封475004,河南大学计算机与信息工程学院开封475004

出版日期:2018-12-01 发布日期:2018-12-01
基金资助:
本文受国家自然科学基金项目(41401461),河南省教育厅自然科学重点项目(15A520009)资助

Iterated Local Search Algorithm with Improved Perturbation Mechanism for Vehicle Routing Problem

HOU Yan-e, KONG Yun-feng and DANG Lan-xue

Online:2018-12-01 Published:2018-12-01

摘要/Abstract

摘要： 针对车辆路径问题,提出一种改进的迭代局部搜索(ILS)算法。该算法基于破坏再重建(Ruin and Recreate)的思想,设计了一种新的扰动机制。扰动过程包含破坏和重建两个阶段,即先使用一种兼顾随机性和相关性的破坏方法对解进行破坏,并引入扰动因子控制解的破坏强度,然后再随机选择基本贪婪插入和改进贪婪插入算法完成解的修复。利用国际标准测试案例对常规扰动机制和改进后的扰动机制进行了测试,并与量子进化算法、蜂群算法进行了比较,实验结果表明改进后的ILS算法更加有效。

关键词: 车辆路径问题,迭代局部搜索,破坏再重建,元启发

Abstract: This paper proposed an iterated local search (ILS) algorithm with a new perturbation mechanism for vehicle routing problem.The perturbation mechanism is based on ruin and recreating principle,which includes destroying and repair procedures.The best local neighborhood solution is firstly destroyed by a method which takes randomness and correlation into account.In the destroying process,a perturbation factor is also introduced into the perturbation mechanism to control the strength of destroying.And then the destroyed solution is repaired by randomly selecting basic greedy insertion and regret greedy insertion algorithms.The experiments on the benchmark instances prove that the developed algorithm is more effective when compared with quantum evolutionary algorithm and artificial bee colony.

Key words: Vehicle routing problem,Iterated local search,Ruin and recreate,Metaheuristic

侯彦娥,孔云峰,党兰学. 求解车辆路径问题的改进扰动机制的ILS算法[J]. 计算机科学, 2016, 43(1): 264-269. https://doi.org/10.11896/j.issn.1002-137X.2016.01.057

HOU Yan-e, KONG Yun-feng and DANG Lan-xue. Iterated Local Search Algorithm with Improved Perturbation Mechanism for Vehicle Routing Problem[J]. Computer Science, 2016, 43(1): 264-269. https://doi.org/10.11896/j.issn.1002-137X.2016.01.057

参考文献

[1] Toth P,Vigo D.The vehicle routing problem [M]∥ The vehicle routing problem :Society for Industrial and Applied Mathematic Philadelphia.2002:245-247
[2] Gendreau M,Potvin J Y.The Vehicle Routing Problem:Latest Advances and New Challenges [M].New York:Springer,2008:143-169
[3] Laporte G.Fifty years of vehicle routing [J].Transportation Science,2009,43(4):408-416
[4] Vidal T,Crainic T G,Gendreau M,et al.Heuristics for multi-attribute vehicle routing problems:A survey [J].European Journal of Operational Research,2013,231(1):1-21
[5] Gendreau M,Potvin J Y.Handbook of Metaheuristics(2nd Edition)[M].New York:Springer,2010:368-370
[6] Chen Ping,Huang Hou-kuan,Dong Xing-ye.A Multi-OperatorBased Iterated Local Search Algorithm for the Capacitated Vehicle Routing Problem [J].Journal of Beijing Jiaotong University(Natural Science),2009,33(2):1-5(in Chinese)陈萍,黄厚宽,董兴业.基于多邻域的车辆路径优化迭代局部搜索算法[J].北京交通大学学报(自然科学版),2009,3(2):1-5
[7] Penna P H V,Subramanian A,Ochi L S.An Iterated LocalSearch heuristic for the Heterogeneous Fleet Vehicle Routing Problem [J].Journal of Heuristics,2013,19(2):201-232
[8] Subramanian A,Penna P H V,Uchoa E,et al.A hybrid algorithm for the Heterogeneous Fleet Vehicle Routing Problem [J].European Journal of Operational Research,2012(221):285-295
[9] Subramanian A,Drummond L M A,Bentes C,et al.A parallel heuristic for the Vehicle Routing Problem with Simultaneous Pickup and Delivery[J].Computers & Operations Research,2010,7(11): 1899-1911
[10] Michallet J,Prins C,Amodeo L,et al.Multi-start iterated local search for the periodic vehicle routing problem with time windows and time spread constraints on services[J].Computers & Operations Research,2014,41(1):196-207
[11] Schrimpf G,Scheider J,Stamm-Wilbrandt H,et al.Recordbreaking optimization results using the ruin and recreate principle[J].Journal of Computational Physics,2000,159(2):139-171
[12] Shaw P.Using constraint programming and local search me-thods to solve vehicle routing problems[C]∥Principles and Practice of Constraint Programming－CP98.Springer,1998:417-431
[13] Pisinger D,Ropke S.A general heuristic for vehicle routingproblems [J].Computers & Operations Research,2007,34(8):2403-2435
[14] Clarke G,Wright J.Scheduling of vehicles from a central depot to a number of delivery points [J].Operations Research,1964,12(4):568-581
[15] Gror C,Golden B,Wasil E.A library of local search heuristics for the vehicle routing problem [J].Mathematical Programming Computation,2010,2(2):79-101
[16] Hou Yan-e,Dang Lan-xue,Kong Yun-feng,et al.Design and Ap-plication of Metaheuristic Framework for School Bus Routing Problem[J].Journal of Chinese Computer Systems,2014,35(7):1625-1631(in Chinese)侯彦娥,党兰学,孔云峰,等.校车路径问题元启发算法框架设计及应用[J].小型微型计算机系统,2014,5(7):1625-1631
[17] Zhao Yan-wei,Peng Dian-jun,Zhang Jing-ling,et al.Quantum volutionary algorithm for capacitated vehicle routing problem[J].System Engineering Theory and Practice,2009,9(2):159-166(in Chinese)赵燕伟,彭典军,张景玲,等.有能力约束车辆路径问题的量子进化算法[J].系统工程理论与实践,2009,9(2):159-166
[18] Wang Zhi-gang,Xia Hui-ming.An artificial bee colony algorithm for the vehicle routing problem[J].Computer Engineering and Science,2014,6(6):1088-1095(in Chinese)王志刚,夏慧明.求解车辆路径问题的人工蜂群算法[J].计算机工程与科学,2014,6(6):1088-1095

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed

求解车辆路径问题的改进扰动机制的ILS算法

Iterated Local Search Algorithm with Improved Perturbation Mechanism for Vehicle Routing Problem

PDF (PC)

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 0

Metrics

本文评价

推荐阅读 0