×

zbMATH — the first resource for mathematics

A hybrid metaheuristic approach for the capacitated arc routing problem. (English) Zbl 1346.90087
Summary: The capacitated arc routing problem (CARP) is a difficult combinatorial optimization problem that has been intensively studied in the last decades. We present a hybrid metaheuristic approach (HMA) to solve this problem which incorporates an effective local refinement procedure, coupling a randomized tabu thresholding procedure with an infeasible descent procedure, into the memetic framework. Other distinguishing features of HMA include a specially designed route-based crossover operator for solution recombination and a distance-and-quality based replacement criterion for pool updating. Extensive experimental studies show that HMA is highly scalable and is able to quickly identify either the best known results or improved best known results for almost all currently available CARP benchmark instances. In particular, it discovers an improved best known result for 15 benchmark instances (6 classical instances and 9 large-sized instances whose optima are unknown). Furthermore, we analyze some key elements and properties of the HMA-CARP algorithm to better understand its behavior.

MSC:
90B06 Transportation, logistics and supply chain management
90B10 Deterministic network models in operations research
90C27 Combinatorial optimization
90C59 Approximation methods and heuristics in mathematical programming
Software:
irace; Tabu search
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Baldacci, R.; Maniezzo, V., Exact methods based on noderouting formulations for undirected arcrouting problems, Networks, 47, 1, 52-60, (2006) · Zbl 1090.90030
[2] Bartolini, E.; Cordeau, J. F.; Laporte, G., Improved lower bounds and exact algorithm for the capacitated arc routing problem, Mathematical Programming, 137, 1-2, 409-452, (2013) · Zbl 1262.90100
[3] Benavent, E.; Campos, V.; Corberan, E.; Mota, E., The capacitated arc routing problem: lower bounds, Networks, 22, 4, 669-690, (1992) · Zbl 0762.90077
[4] Beullens, P.; Muyldermans, L.; Cattrysse, D.; Van Oudheusden, D., A guided local search heuristic for the capacitated arc routing problem, European Journal of Operational Research, 147, 3, 629-643, (2003) · Zbl 1026.90015
[5] Birattari, M.; Yuan, Z.; Balaprakash, P.; Stützle, T., F-race and iterated F-race: an overview, Experimental methods for the analysis of optimization algorithms, 311-336, (2010), Springer Berlin, Germany · Zbl 1204.68280
[6] Bode, C.; Irnich, S., Cut-first branch-and-price-second for the capacitated arc-routing problem, Operations research, 60, 5, 1167-1182, (2012) · Zbl 1257.90008
[7] Brandão, J.; Eglese, R., A deterministic tabu search algorithm for the capacitated arc routing problem, Computers & Operations Research, 35, 4, 1112-1126, (2008) · Zbl 1179.90031
[8] Corberán, A.; Laporte, G., Arc routing: problems, methods, and applications, MOS-SIAM series on optimization, 20, (2015), SIAM
[9] DeArmon, J. S., A comparison of heuristics for the capacitated chinese postman problems, (1981), University of Maryland, College Park, MD, Master thesis
[10] Dror, M., Arc routing: Theory, solutions and applications, (2000), Kluwer Academic Publishers · Zbl 0947.00016
[11] Eglese, R. W., Routing winter gritting vehicles, Discrete Applied Mathematics, 48, 3, 231-244, (1994) · Zbl 0790.90031
[12] Glover, F., Tabu thresholding: improved search by nonmonotonic trajectories, ORSA Journal on Computing, 7, 4, 426-442, (1995) · Zbl 0843.90097
[13] Glover, F.; Hao, J. K., The case for strategic oscillation, Annals of Operations Research, 183, 1, 163-173, (2011) · Zbl 1214.90097
[14] (Glover, F.; Kochenberger, G., Handbook of metaheuristics, (2003), Kluwer, Norwell, Massachusetts, USA) · Zbl 1058.90002
[15] Glover, F.; Laguna, M., Tabu search, (1997), Kluwer Academic Publishers · Zbl 0930.90083
[16] Golden, B. L.; DeArmon, J. S.; Baker, E. K., Computational experiments with algorithms for a class of routing problems, Computers & Operations Research, 10, 1, 47-59, (1983)
[17] Golden, B. L.; Wong, R. T., Capacitated arc routing problems, Networks, 11, 3, 305-315, (1981) · Zbl 0459.90083
[18] Hao, J. K., Memetic algorithms in discrete optimization, (Neri, F.; Cotta, C.; Moscato, P., Handbook of memetic algorithms. studies in computational intelligence 379, chapter 6, (2012)), 7394
[19] Hertz, A.; Laporte, G.; Mittaz, M., A tabu search heuristic for the capacitated arc routing problem, Operations research, 48, 1, 129-135, (2000) · Zbl 1106.90384
[20] Hertz, A.; Mittaz, M., A variable neighborhood descent algorithm for the undirected capacitated arc routing problem, Transportation science, 35, 4, 425-434, (2001) · Zbl 1069.90517
[21] Lacomme, P.; Prins, C.; Ramdane-Cherif, W., Competitive memetic algorithms for arc routing problems, Annals of Operations Research, 131, 1-4, 159-185, (2004) · Zbl 1066.90010
[22] López-Ibáñez, M.; Dubois-Lacoste, J.; Stützle, T.; Birattari, M., The irace package, iterated race for automatic algorithm configuration, Technical Report, TR/IRIDIA/2011-004, (2011), IRIDIA, Universit Libre de Bruxelles, Belgium
[23] Martinelli, R.; Poggi, M.; Subramanian, A., Improved bounds for large scale capacitated arc routing problem, Computers & Operations Research, 40, 8, 2145-2160, (2013) · Zbl 1348.90476
[24] Mei, Y.; Li, X.; Yao, X., Cooperative coevolution with route distance grouping for large-scale capacitated arc routing problems, IEEE Transactions on Evolutionary Computation, 18, 3, 435-449, (2014)
[25] Mei, Y.; Tang, K.; Yao, X., A global repair operator for capacitated arc routing problem, IEEE Transactions on Systems, Man, and Cybernetics, Part B: Cybernetics, 39, 3, 723-734, (2009)
[26] Moscato, P., On evolution, search, optimization, genetic algorithms and martial arts: towards memetic algorithms, Caltech Concurrent Computation Program, C3P Report, 826, (1989)
[27] Moscato, P.; Cotta, C., A gentle introduction to memetic algorithms, (Glover, F.; Kochenberger, G. A., Handbook of metaheuristics. Kluwer, Norwell, Massachusetts, USA, (2003)) · Zbl 1107.90459
[28] Neri F., Cotta C. & Moscato P. (Eds.) (2011). Handbook of memetic algorithms. In: Studies in Computational Intelligence 379, Springer.
[29] Polacek, M.; Doerner, K. F.; Hartl, R. F.; Maniezzo, V., A variable neighborhood search for the capacitated arc routing problem with intermediate facilities, Journal of Heuristics, 14, 5, 405-423, (2008) · Zbl 1211.90314
[30] Potvin, J. Y.; Bengio, S., The vehicle routing problem with time windows part II: genetic search, INFORMS Journal on Computing, 8, 2, 165-172, (1996) · Zbl 0866.90058
[31] Santos, L.; Coutinho-Rodrigues, J.; Current, J. R., An improved ant colony optimization based algorithm for the capacitated arc routing problem, Transportation Research Part B: Methodological, 44, 2, 246-266, (2010)
[32] Stern, H. I.; Dror, M., Routing electric meter readers, Computers & Operations Research, 6, 4, 209-223, (1979)
[33] Tang, K.; Mei, Y.; Yao, X., Memetic algorithm with extended neighborhood search for capacitated arc routing problems, IEEE Transactions on Evolutionary Computation, 13, 5, 1151-1166, (2009)
[34] Ulusoy, G., The fleet size and mix problem for capacitated arc routing, European Journal of Operational Research, 22, 3, 329-337, (1985) · Zbl 0576.90094
[35] Usberti, F. L.; Paulo, M. F.; André, L. M.F., GRASP with evolutionary path-relinking for the capacitated arc routing problem, Computers & Operations Research, 40, 12, 3206-3217, (2013) · Zbl 1348.90158
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.