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 .
[3] ZHANG Jia-nan and XIAO Ming-yu. Approximation Algorithm for Weighted Mixed Domination Problem[J]. Computer Science, 2018, 45(4): 83 -88 .
[4] 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 .
[5] 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 .
[6] ZHOU Yan-ping and YE Qiao-lin. L1-norm Distance Based Least Squares Twin Support Vector Machine[J]. Computer Science, 2018, 45(4): 100 -105 .
[7] LIU Bo-yi, TANG Xiang-yan and CHENG Jie-ren. Recognition Method for Corn Borer Based on Templates Matching in Muliple Growth Periods[J]. Computer Science, 2018, 45(4): 106 -111 .
[8] GENG Hai-jun, SHI Xin-gang, WANG Zhi-liang, YIN Xia and YIN Shao-ping. Energy-efficient Intra-domain Routing Algorithm Based on Directed Acyclic Graph[J]. Computer Science, 2018, 45(4): 112 -116 .
[9] CUI Qiong, LI Jian-hua, WANG Hong and NAN Ming-li. Resilience Analysis Model of Networked Command Information System Based on Node Repairability[J]. Computer Science, 2018, 45(4): 117 -121 .
[10] WANG Zhen-chao, HOU Huan-huan and LIAN Rui. Path Optimization Scheme for Restraining Degree of Disorder in CMT[J]. Computer Science, 2018, 45(4): 122 -125 .