A Hybrid Genetic Algorithm with Perturbation for the Multi-depot
Capacitated Arc Routing Problem
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.
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.
REFERENCES
Benavent, E., V. Campos, A. Corberan and E. Mota, 1990. The capacitated arc routing problem. A heuristic algorithm. Questiio, 14: 107-122.
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
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
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
Corberan, A. and C. Prins, 2010. Recent results on arc routing problems: An annotated bibliography. Networks, 56: 50-69.
CrossRef Direct Link
Eglese, R.W., 1994. Routeing winter gritting vehicles. Discrete Applied Math., 48: 231-244.
CrossRef Direct Link
Frederickson, G.N., 1979. Approximation algorithms for some postman problems. J. ACM, 26: 538-554.
CrossRef Direct Link
Golden, B.L. and R.T. Wong, 1981. Capacitated arc routing problems. Networks, 11: 305-315.
CrossRef Direct 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.
CrossRef Direct Link
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
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
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
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.
Pearn, W.L., 1989. Approximate solutions for the capacitated arc routing problem. Comput. Operat. Res., 16: 589-600.
CrossRef Direct 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.
CrossRef Direct 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.
CrossRef Direct Link
Ulusoy, G., 1985. The fleet size and mix problem for capacitated arc routing. Eur. J. Operat. Res., 22: 329-337.
CrossRef Direct Link
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
© Science Alert. All Rights Reserved