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!
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!