Top

Published in:

2018 | OriginalPaper | Chapter

A Metaheuristic Approach for the Cumulative Capacitated Arc Routing Problem

Authors : Sergio Andrés Lenis, Juan Carlos Rivera

Published in: Applied Computer Sciences in Engineering

Publisher: Springer International Publishing

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

In this paper we propose a new variant of the capacitated arc routing problem (CARP). In this new problem the objective function becomes a cumulative objective computed as the traveled distance multiplied by the vehicle load. A metaheuristic approach is proposed which is based on the hybridization of three known procedures: GRASP, VND and Set covering model. The metaheuristic is tested with some benchmark instances from CARP. The results allow to evaluate the performance with the different metaheuristic components and to compare the solutions with the classical objective function.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

previous chapter Modeling Strategy for Supply Chain Design Considering Multiple Periods and Backlogging

next chapter A Mixed-Integer Linear Programming Model for a Selective Vehicle Routing Problem

Archer, A., Williamson, D.P.: Faster approximation algorithms for the minimum latency problem. In: Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) (2003)

Belenguer, J.M., Benavent, E.: The capacitated arc routing problem: valid inequalities and facets. Comput. Optim. Appl. 10(2), 165–187 (1998)MathSciNetCrossRef

Belenguer, J.M., Benavent, E.: A cutting plane algorithm for the capacitated arc routing problem. Comput. Oper. Res. 30(5), 705–728 (2003)MathSciNetCrossRef

Beullens, P., Muyldermans, L., Cattrysse, D., Oudheusden, D.V.: A guided local search heuristic for the capacitated arc routing problem. Eur. J. Oper. Res. 147(3), 629–643 (2003). https://doi.org/10.1016/S0377-2217(02)00334-X. http://www.sciencedirect.com/science/article/pii/S037722170200334XMathSciNetCrossRefMATH

Blum, A., Chalasani, P., Coppersmith, D., Pulleyblank, B., Raghavan, P., Sudan, M.: The minimum latency problem. In: Proceedings of the Twenty-Sixth Annual ACM Symposium on Theory of Computing, STOC 1994, pp. 163–171. ACM, New York (1994)

Brandao, J., Eglese, R.: A deterministic tabu search algorithm for the capacitated arc routing problem. Comput. Oper. Res. 35(4), 1112–1126 (2008). https://doi.org/10.1016/j.cor.2006.07.007. http://www.sciencedirect.com/science/article/pii/S0305054806001535MathSciNetCrossRefMATH

Campbell, A.M., Vandenbussche, D., Hermann, W.: Routing for relief efforts. Transp. Sci. 42(2), 127–145 (2008). https://doi.org/10.1287/trsc.1070.0209CrossRef

Corberán, A., Laporte, G.: Arc routing: problem, methods, and applications. In: SIAM (2014)

Dror, M.: Arc Routing. Theory, Solutions and Applications. Springer, Boston (2000). https://doi.org/10.1007/978-1-4615-4495-1CrossRefMATH

10.

Fischetti, M., Laporte, G., Martello, S.: The delivery man problem and cumulative matroids. Oper. Res. 41(6), 1055–1064 (1993)MathSciNetCrossRef

11.

Golden, B., Dearmon, J., Baker, E.: Computational experiments with algorithms for a class of routing problems. Comput. Oper. Res. 10(1), 47–59 (1983). https://doi.org/10.1016/0305-0548(83)90026-6. http://www.sciencedirect.com/science/article/pii/0305054883900266MathSciNetCrossRef

12.

Golden, B.L., Wong, R.T.: Capacitated arc routing problems. Networks 11(3), 305–315 (1981)MathSciNetCrossRef

13.

Hirabayashi, R., Saruwatari, Y., Nishida, N.: Tour construction algorithm for the capacitated arc routing problem. Asia-Pac. J. Oper. Res. 9, 155–175 (1992)MathSciNetMATH

14.

Jothi, R., Raghavachari, B.: Minimum latency tours and the k-traveling repairmen problem. In: Farach-Colton, M. (ed.) LATIN 2004. LNCS, vol. 2976, pp. 423–433. Springer, Heidelberg (2004). https://doi.org/10.1007/978-3-540-24698-5_46CrossRef

15.

Kara, I., Kara, B., Kadri, M.: Cumulative vehicle routing problems, pp. 85–98 (2008)

16.

Ke, L., Feng, Z.: A two-phase metaheuristic for the cumulative capacitated vehicle routing problem. Comput. Oper. Res. 40, 633–638 (2013)CrossRef

17.

Lacomme, P., Prins, C., Ramdane-Chérif, W.: A genetic algorithm for the capacitated arc routing problem and its extensions. In: Boers, E.J.W. (ed.) EvoWorkshops 2001. LNCS, vol. 2037, pp. 473–483. Springer, Heidelberg (2001). https://doi.org/10.1007/3-540-45365-2_49CrossRefMATH

18.

Lin, C., Choy, K., Ho, G., Chung, S., Lam, H.: Survey of green vehicle routing problem: past and future trends. Expert. Syst. Appl. 41(4), 1118–1138 (2014). https://doi.org/10.1016/j.eswa.2013.07.107. http://www.sciencedirect.com/science/article/pii/S095741741300609XCrossRef

19.

Lysgaard, J., Wøhlk, S.: A branch-and-cut-and-price algorithm for the cumulative capacitated vehicle routing problem. Eur. J. Oper. Res. 236(3), 800–810 (2014)MathSciNetCrossRef

20.

Ngueveu, S.U., Prins, C., Calvo, R.W.: An effective memetic algorithm for the cumulative capacitated vehicle routing problem. Comput. Oper. Res. 37(11), 1877–1885 (2010)MathSciNetCrossRef

21.

Prins, C., Labadi, N., Reghioui, M.: Tour splitting algorithms for vehicle routing problems. Int. J. Prod. Res. 47(2), 507–535 (2009)CrossRef

22.

Ribeiro, G.M., Laporte, G.: An adaptive large neighborhood search heuristic for the cumulative capacitated vehicle routing problem. Comput. Oper. Res. 39(3), 728–735 (2012)MathSciNetCrossRef

23.

Tsitsiklis, J.N.: Special cases of traveling salesman and repairman problems with time windows. Networks 22, 263–282 (1992)MathSciNetCrossRef

24.

Wøhlk, S.: A decade of capacitated arc routing. In: Wasil, E. (ed.) The Vehicle Routing Problem: Latest Advances and New Challenges. Operations Research/Computer Science Interfaces Series, vol. 43, pp. 29–48. Springer, Boston (2008). https://doi.org/10.1007/978-0-387-77778-8_2CrossRefMATH

Title: A Metaheuristic Approach for the Cumulative Capacitated Arc Routing Problem
Authors: Sergio Andrés Lenis
Juan Carlos Rivera
Publisher: Springer International Publishing
Book: Applied Computer Sciences in Engineering
Print ISBN: 978-3-030-00352-4

Electronic ISBN: 978-3-030-00353-1

Copyright Year: 2018
DOI: https://doi.org/10.1007/978-3-030-00353-1_9

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner