×

zbMATH — the first resource for mathematics

An adaptive large neighborhood search heuristic for the cumulative capacitated vehicle routing problem. (English) Zbl 1251.90057
Summary: The cumulative capacitated vehicle routing problem (CCVRP) is a variation of the classical capacitated vehicle routing problem in which the objective is the minimization of the sum of arrival times at customers, instead of the total routing cost. This paper presents an adaptive large neighborhood search heuristic for the CCVRP. This algorithm is applied to a set of benchmark instances and compared with two recently published memetic algorithms.

MSC:
90B06 Transportation, logistics and supply chain management
90C59 Approximation methods and heuristics in mathematical programming
Software:
VRP
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Lucena, A., Time-dependent traveling salesman problem: the deliveryman case, Networks, 20, 753-763, (1990) · Zbl 0744.90063
[2] Fischetti, M.; Laporte, G.; Martello, S., The delivery man problem and cumulative matroids, Operations research, 41, 1055-1064, (1993) · Zbl 0791.90062
[3] Picard, J.-C.; Queyranne, M., The time-dependent traveling salesman problem and its application to the tardiness problem in one-machine scheduling, Operations research, 26, 86-110, (1978) · Zbl 0371.90066
[4] Stecco, G.; Cordeau, J.-F.; Moretti, E., A tabu search heuristic for a sequence-dependent and time-dependent scheduling problem on a single machine, Journal of scheduling, 12, 3-16, (2009) · Zbl 1168.90472
[5] Heilporn, G.; Cordeau, J.-F.; Laporte, G., The delivery man problem with time windows, Discrete optimization, 7, 269-282, (2010) · Zbl 1241.90110
[6] Park, J.; Kim, B.-I., The school bus routing problem: a review, European journal of operational research, 202, 311-319, (2010) · Zbl 1175.90339
[7] Ogryczak, W., Inequality measures and equitable approaches to location problems, European journal of operational research, 122, 374-391, (2000) · Zbl 0961.90053
[8] Campbell, A.M.; Vandenbussche, D.; Hermann, W., Routing for relief efforts, Transportation science, 42, 127-145, (2008)
[9] Ngueveu, S.U.; Prins, C.; Wolfler-Calvo, R., An effective memetic algorithm for the cumulative capacitated vehicle routing problem, Computers & operations research, 37, 1877-1885, (2010) · Zbl 1188.90037
[10] Nolz, P.C.; Doerner, K.F.; Gutjahr, W.J.; Hartl, R.F., A bi-objective metaheuristic for disaster relief operation planning, (), 167-187 · Zbl 1187.90259
[11] Augerat P, Belenguer J, Benavent E, Corberán A, Naddef D, Rinaldi G. Computational results with a branch and cut code for the capacitated vehicle routing problem. Technical Report 949-M, Université Joseph Fourier, Grenoble; 1995.
[12] Golden, B.L.; Wasil, E.A.; Kelly, J.P.; Chao, I.-M., Metaheuristics in vehicle routing, (), 33-56 · Zbl 0997.90021
[13] Prins, C., A simple and effective evolutionary algorithm for the vehicle routing problem, Computers & operations research, 31, 1985-2002, (2004) · Zbl 1100.90504
[14] Ropke, S.; Pisinger, D., An adaptive large neighborhood search heuristic for the pickup and delivery problem with time windows, Transportation science, 40, 455-472, (2006)
[15] Shaw P. A new local search algorithm providing high quality solutions to vehicle routing problems. Technical Report, University of Strathclyde, Glasgow; 1997.
[16] Pisinger, D.; Ropke, S., Large neighborhood search, (), 399-419
[17] Ropke, S.; Pisinger, D., A unified heuristic for a large class of vehicle routing problems with backhauls, European journal of operational research, 171, 750-775, (2006) · Zbl 1116.90019
[18] Pisinger, D.; Ropke, S., A general heuristic for the vehicle routing problem, Computers & operations research, 34, 2403-2435, (2007) · Zbl 1144.90318
[19] Azi N, Gendreau M, Potvin J.-Y. An adaptive large neighborhood search for a vehicle routing problem with multiple trips. Technical Report 2010-08, CIRRELT, Montréal, Available at \(\langle\)https://www.cirrelt.ca/DocumentsTravail/CIRRELT-2010-08.pdf〉; 2010. · Zbl 1348.90065
[20] Pepin, A.-S.; Desaulniers, G.; Hertz, A.; Huisman, D., A comparison of five heuristics for the multiple depot vehicle scheduling problem, Journal of scheduling, 12, 17-30, (2009) · Zbl 1168.90464
[21] Kruskal JB. On the shortest spanning subtree of a graph and the traveling salesman problem. In: Proceedings of the American Mathematical Society, vol. 7. American Mathematical Society; 1956. p. 48-50. · Zbl 0070.18404
[22] Potvin, J.-Y.; Rousseau, J.-M., A parallel route building algorithm for the vehicle routing and scheduling problem with time windows, European journal of operational research, 66, 331-340, (1993) · Zbl 0775.90154
[23] Christofides, N.; Mingozzi, A.; Toth, P., The vehicle routing problem, (), 315-338
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.