Computer Science ›› 2016, Vol. 43 ›› Issue (1): 264-269.doi: 10.11896/j.issn.1002-137X.2016.01.057

Previous Articles     Next Articles

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: 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

[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

No related articles found!
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!