Subscribe Now Subscribe Today
Research Article
 

A Hybrid Genetic Algorithm with Perturbation for the Multi-depot Capacitated Arc Routing Problem



Hongtao Hu, Tiantang Liu, Ning Zhao, Yiting Zhou and Dequan Min
 
Facebook Twitter Digg Reddit Linkedin StumbleUpon E-mail
ABSTRACT

The Capacitated Arc Routing Problem (CARP) is a difficult vehicle routing problem, where given an undirected graph, the objective is to minimize the total cost of all vehicle tours that serve all required edges under vehicle capacity constraints. In this study, a Hybrid Genetic Algorithm with Perturbation (HGAP) is proposed to solve the multi-depot CARP (MDCARP) which generalizes the CARP by extending the single-depot to the multi-depot. The proposed HGAP incorporates a Genetic Algorithm (GA), a local search, a new replacement method and a perturbation mechanism. The proposed HGAP is evaluated on the MDCARP benchmark instances and computational results show that the HGAP is very competitive.

Services
Related Articles in ASCI
Similar Articles in this Journal
Search in Google Scholar
View Citation
Report Citation

 
  How to cite this article:

Hongtao Hu, Tiantang Liu, Ning Zhao, Yiting Zhou and Dequan Min, 2013. A Hybrid Genetic Algorithm with Perturbation for the Multi-depot Capacitated Arc Routing Problem. Journal of Applied Sciences, 13: 3239-3244.

DOI: 10.3923/jas.2013.3239.3244

URL: https://scialert.net/abstract/?doi=jas.2013.3239.3244
 

REFERENCES
1:  Benavent, E., V. Campos, A. Corberan and E. Mota, 1990. The capacitated arc routing problem. A heuristic algorithm. Questiio, 14: 107-122.

2:  Beullens, P., L. Muyldermans, D. Cattrysse and D. van Oudheusden, 2003. A guided local search heuristic for the capacitated arc routing problem. Eur. J. Operat. Res., 147: 629-643.
CrossRef  |  Direct Link  |  

3:  Brandao, J. and R. Eglese, 2008. A deterministic tabu search algorithm for the capacitated arc routing problem. Comput. Operat. Res., 35: 1112-1126.
CrossRef  |  Direct Link  |  

4:  Chapleau, L., J.A. Ferland, G. Lapalme and J.M. Rousseau, 1984. A parallel insert method for the capacitated arc routing problem. Operat. Res. Lett., 3: 95-99.
CrossRef  |  Direct Link  |  

5:  Corberan, A. and C. Prins, 2010. Recent results on arc routing problems: An annotated bibliography. Networks, 56: 50-69.
CrossRef  |  Direct Link  |  

6:  Eglese, R.W., 1994. Routeing winter gritting vehicles. Discrete Applied Math., 48: 231-244.
CrossRef  |  Direct Link  |  

7:  Frederickson, G.N., 1979. Approximation algorithms for some postman problems. J. ACM, 26: 538-554.
CrossRef  |  Direct Link  |  

8:  Golden, B.L. and R.T. Wong, 1981. Capacitated arc routing problems. Networks, 11: 305-315.
CrossRef  |  Direct Link  |  

9:  Golden, B.L., J.S. DeArmon and E.K. Baker, 1983. Computational experiments with algorithms for a class of routing problems. Comput. Operat. Res., 10: 47-59.
CrossRef  |  Direct Link  |  

10:  Hertz, A., G. Laporte and M. Mittaz, 2000. A tabu search heuristic for the capacitated arc routing problem. Operat. Res., 48: 129-135.
CrossRef  |  Direct Link  |  

11:  Kansou, A. and A. Yassine, 2010. New upper bounds for the multi-depot capacitated arc routing problem. Int. J. Metaheuristics, 1: 81-95.
CrossRef  |  Direct Link  |  

12:  Lacomme, P., C. Prins and W. Ramdane-Cherif, 2004. Competitive memetic algorithms for arc routing problems. Ann. Operat. Res., 131: 159-185.
CrossRef  |  Direct Link  |  

13:  Liu, T., Z. Jiang, F. Chen, R. Liu and S. Liu, 2008. Combined Location-arc routing problems: A survey and suggestions for future research. Proceedings of the International Conference Service Operations and Logistics and Informatics, October 12-15, 2008, Beijing, pp: 2336-2341.

14:  Pearn, W.L., 1989. Approximate solutions for the capacitated arc routing problem. Comput. Operat. Res., 16: 589-600.
CrossRef  |  Direct Link  |  

15:  Polacek, M., K.F. Doerner, R.F. Hartl and V. Maniezzo, 2008. A variable neighborhood search for the capacitated arc routing problem with intermediate facilities. J. Heuristics, 14: 405-423.
CrossRef  |  Direct Link  |  

16:  Santos, L., J. Coutinho-Rodrigues and J.R. Current, 2010. An improved ant colony optimization based algorithm for the capacitated arc routing problem. Transport. Res. B: Meth., 44: 246-266.
CrossRef  |  Direct Link  |  

17:  Ulusoy, G., 1985. The fleet size and mix problem for capacitated arc routing. Eur. J. Operat. Res., 22: 329-337.
CrossRef  |  Direct Link  |  

18:  Hertz, A. and M. Mittaz, 2001. A variable neighborhood descent algorithm for the undirected capacitated arc routing problem. Transport. Sci., 35: 425-434.
CrossRef  |  Direct Link  |  

©  2021 Science Alert. All Rights Reserved