Abstract
This paper studies the multitrip cumulative capacitated vehicle routing problem (mt-CCVRP), a variant of the classical capacitated vehicle routing problem (CVRP). In the mt-CCVRP the objective function becomes the minimization of the sum of arrival times at required nodes and each vehicle may perform more than one trip. Applications of this NP-Hard problem can be found in disaster logistics. This article presents a Multistart Evolutionary Local Search (MS-ELS) that alternates between giant tour and mt-CCVRP solutions, and uses an adapted split procedure and a variable neighborhood descent (VND). The results on two sets of instances show that this approach finds very good results in relatively short computing time compared with a multistart iterated local search which works directly on the mt-CCVRP solution space.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Campbell, A.M., Vandenbussche, D., Hermann, W.: Routing for relief efforts. Transp. Sci. 42(2), 127–145 (2008)
Rivera, J.C., Afsar, M.H.: Christian: A multi-start iterated local search for the multitrip cumulative capacitated vehicle routing problem. Technical report, Troyes University of Technology (2013)
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)
Fischetti, M., Laporte, G., Martello, S.: The delivery man problem and cumulative matroids. Oper. Res. 41(6), 1055–1064 (1993)
Jothi, R., Raghavachari, B.: Approximating the k-traveling repairman problem with repairtimes. J. Discrete Algorithms 5(2), 293–303 (2007)
Tsitsiklis, J.N.: Special cases of traveling salesman and repairman problems with time windows. Networks 22, 263–282 (1992)
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)
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)
Ke, L., Feng, Z.: A two-phase metaheuristic for the cumulative capacitated vehicle routing problem. Comput. Oper. Res. 40, 633–638 (2013)
Prins, C.: A simple and effective evolutionary algorithm for the vehicle routing problem. Comput. Oper. Res. 31(12), 1985–2002 (2004)
Boland, N., Clarke, L., Nemhauser, G.: The asymmetric traveling salesman problem with replenishment arcs. Eur. J. Oper. Res. 123(2), 408–427 (2000)
Silva, M.M., Subramanian, A., Vidal, T., Ochi, L.S.: A simple and effective metaheuristic for the minimum latency problem. Eur. J. Oper. Res. 221(3), 513–520 (2012)
Petch, R.J., Salhi, S.: A multi-phase constructive heuristic for the vehicle routing problem with multiple trips. Discrete Appl. Math. 133, 69–92 (2004)
Christofides, N., Mingozzi, A., Toth, P.: The Vehicle Routing Problem. Wiley, Chichester (1979)
Golden, B.L., Wasil, E., Kelly, J.P., Chao, I.M.: Metaheuristics in Vehicle Routing. Kluwer, Boston (1998)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2014 Springer International Publishing Switzerland
About this paper
Cite this paper
Rivera, J.C., Afsar, H.M., Prins, C. (2014). Multistart Evolutionary Local Search for a Disaster Relief Problem. In: Legrand, P., Corsini, MM., Hao, JK., Monmarché, N., Lutton, E., Schoenauer, M. (eds) Artificial Evolution. EA 2013. Lecture Notes in Computer Science(), vol 8752. Springer, Cham. https://doi.org/10.1007/978-3-319-11683-9_11
Download citation
DOI: https://doi.org/10.1007/978-3-319-11683-9_11
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-11682-2
Online ISBN: 978-3-319-11683-9
eBook Packages: Computer ScienceComputer Science (R0)