Hongtao Hu
Logistics Engineering College, Shanghai Maritime University, Shanghai, China
Tiantang Liu
School of Mechanical Engineering, Shanghai Jiao Tong University, Shanghai, China
Ning Zhao
Logistics Engineering College, Shanghai Maritime University, Shanghai, China
Yiting Zhou
Logistics Engineering College, Shanghai Maritime University, Shanghai, China
Dequan Min
Transportation Management College, Dalian Maritime University, Dalian, China
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.
PDF References 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
DOI: 10.3923/jas.2013.3239.3244
URL: https://scialert.net/abstract/?doi=jas.2013.3239.3244
REFERENCES
- 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.
CrossRefDirect Link - Brandao, J. and R. Eglese, 2008. A deterministic tabu search algorithm for the capacitated arc routing problem. Comput. Operat. Res., 35: 1112-1126.
CrossRefDirect Link - 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.
CrossRefDirect Link - Corberan, A. and C. Prins, 2010. Recent results on arc routing problems: An annotated bibliography. Networks, 56: 50-69.
CrossRefDirect Link - Eglese, R.W., 1994. Routeing winter gritting vehicles. Discrete Applied Math., 48: 231-244.
CrossRefDirect Link - Frederickson, G.N., 1979. Approximation algorithms for some postman problems. J. ACM, 26: 538-554.
CrossRefDirect Link - Golden, B.L. and R.T. Wong, 1981. Capacitated arc routing problems. Networks, 11: 305-315.
CrossRefDirect Link - 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.
CrossRefDirect Link - Hertz, A., G. Laporte and M. Mittaz, 2000. A tabu search heuristic for the capacitated arc routing problem. Operat. Res., 48: 129-135.
CrossRefDirect Link - Kansou, A. and A. Yassine, 2010. New upper bounds for the multi-depot capacitated arc routing problem. Int. J. Metaheuristics, 1: 81-95.
CrossRefDirect Link - Lacomme, P., C. Prins and W. Ramdane-Cherif, 2004. Competitive memetic algorithms for arc routing problems. Ann. Operat. Res., 131: 159-185.
CrossRefDirect Link - 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.
CrossRef - Pearn, W.L., 1989. Approximate solutions for the capacitated arc routing problem. Comput. Operat. Res., 16: 589-600.
CrossRefDirect Link - 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.
CrossRefDirect Link - 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.
CrossRefDirect Link - Ulusoy, G., 1985. The fleet size and mix problem for capacitated arc routing. Eur. J. Operat. Res., 22: 329-337.
CrossRefDirect Link - Hertz, A. and M. Mittaz, 2001. A variable neighborhood descent algorithm for the undirected capacitated arc routing problem. Transport. Sci., 35: 425-434.
CrossRefDirect Link