Computer Science ›› 2018, Vol. 45 ›› Issue (4): 76-82.doi: 10.11896/j.issn.1002-137X.2018.04.011

Previous Articles     Next Articles

Hybrid Evolutionary Algorithm for Solving Mixed Capacitated General Routing Problem

SUN Qi, JIN Yan, HE Kun and XU Ling-xuan   

  • Online:2018-04-15 Published:2018-05-11

Abstract: This paper studied an NP-hard mixed capacitated general routing problem(MCGRP),which is derived from the classical vehicle routing problem(VRP) by adding the capacitated constraints and the demands on the arcs.Given a vehicle team with unlimited number,the vehicles serve the customers from the depot and need to return to the depot after completing service.The constraints are that the total load of each vehicle cannot exceed its capacity and each demand can only be served by one vehicle once.This paper aimed to provide a plan of the service route for each vehicle,so that the total travel expenses of all vehicles are minimized when the constraints are satisfied.The MCGRP has a relatively high theoretical value as well as application value.An efficient hybrid evolutionary algorithm was proposed for MCGRP.It applies a variable neighborhood tabu search with five neighborhood operators to improve the quality of solutions,and designs a route-based crossover operator to inherit the high-quality solutions so that the search efficiency can be improved.Experimental results on 23 well-known benchmark instances show that the proposed algorithm is effective for solving the MCGRP.

Key words: Metaheuristic,Vehicle routing problem,Tabu search,Hybrid evolutionary algorithm

[1] GOLDEN B,RAGHAVAN S,WASIL E.The Vehicle Routing Problem:Latest Advances and New Challenges [M].Springer US,2008.
[2] CORBERN A,PRINS C.Recent results on arc routing problems:An annotated bibliography[J].Networks,2010,56(1):50-69.
[3] PRINS C,BOUCHENOUA S.A memetic algorithm solving the vrp,the carp and general routing problems with nodes,edges and arcs[M]∥Recent Advances in Memetic Algorithms.Springer Berlin Heidelberg,2005,166:65-85.
[4] PANDI R,MURALIDHARAN B.A capacitated general routing problem on mixed networks [J].Computers & Operations Research,1995,22:465-478.
[5] DELL’AMICO M,HASLE G,CARLOS J,et al.An AdaptiveIterated Local Search for the Mixed Capacitated General Routing Problem [J].Transportation Science,2014,50(4):1223-1238.
[6] KOKUBUGATA H,MORIYAMA A,KAWASHIMA H.Apractical solution using simulated annealing for general routing problems with nodes,edges,and arcs[M]∥Engineering Stochastic Local Search Algorithms :Designing,Implementing and Analyzing Effective Heuristics.Springer Berlin Heidelberg,2007.
[7] BRANDIO J,EGLESE R.A deterministic tabu search algorithm for the capacitated arc routing problem [J].Computers & Ope-rations Research,2008,35(4):1112-1126.
[8] PRINS C,BOUCHENOUA S.A memetic algorithm solving the vrp,the carp and general routing problems with nodes,edges and arcs[M]∥Recent Advances in Memetic Algorithms.Springer Berlin Heidelberg,2005.
[9] BOSCO A,LAGANA D,MUSMANNO R,et al.Modeling andsolving the mixed capacitated general routing problem [J].Optimization Letters,2013,7(7):1451-1469.
[10] POTVIN J Y,BENGIO S.The vehicle routing problem withtime windows part II:genetic search [J].INFORMS Journal on Computing,1996,8(2):165-172.
[11] CHEN Y,HAO J K,GLOVER F.A hybrid metaheuristic approach for the capacitated arc routing problem[J].European Journal of Operational Research,2016,253(1):25-39.
[12] BACH L,HASLE G,WHLK S.A lower bound for the node,edge,and arc routing problem [J].Computers & Operations Research,2013,40(4):943-952.

No related articles found!
Full text



[1] . [J]. Computer Science, 2018, 1(1): 1 .
[2] LEI Li-hui and WANG Jing. Parallelization of LTL Model Checking Based on Possibility Measure[J]. Computer Science, 2018, 45(4): 71 -75, 88 .
[3] XIA Qing-xun and ZHUANG Yi. Remote Attestation Mechanism Based on Locality Principle[J]. Computer Science, 2018, 45(4): 148 -151, 162 .
[4] LI Bai-shen, LI Ling-zhi, SUN Yong and ZHU Yan-qin. Intranet Defense Algorithm Based on Pseudo Boosting Decision Tree[J]. Computer Science, 2018, 45(4): 157 -162 .
[5] WANG Huan, ZHANG Yun-feng and ZHANG Yan. Rapid Decision Method for Repairing Sequence Based on CFDs[J]. Computer Science, 2018, 45(3): 311 -316 .
[6] ZHANG Jia-nan and XIAO Ming-yu. Approximation Algorithm for Weighted Mixed Domination Problem[J]. Computer Science, 2018, 45(4): 83 -88 .
[7] WU Jian-hui, HUANG Zhong-xiang, LI Wu, WU Jian-hui, PENG Xin and ZHANG Sheng. Robustness Optimization of Sequence Decision in Urban Road Construction[J]. Computer Science, 2018, 45(4): 89 -93 .
[8] LIU Qin. Study on Data Quality Based on Constraint in Computer Forensics[J]. Computer Science, 2018, 45(4): 169 -172 .
[9] ZHONG Fei and YANG Bin. License Plate Detection Based on Principal Component Analysis Network[J]. Computer Science, 2018, 45(3): 268 -273 .
[10] SHI Wen-jun, WU Ji-gang and LUO Yu-chun. Fast and Efficient Scheduling Algorithms for Mobile Cloud Offloading[J]. Computer Science, 2018, 45(4): 94 -99, 116 .