×

A novel approach to solve the split delivery vehicle routing problem. (English) Zbl 1358.90015

Summary: The split delivery vehicle routing problem (SDVRP) is a relaxed version of the classic capacitated vehicle routing problem (CVRP). Customer demands are allowed to split among vehicles. This problem is computationally challenging and the state-of-the-art heuristics are often complicated to describe and difficult to implement, and usually have long computing times. All these hinder their application by practitioners to solve real-world problems. We propose a novel, efficient, and easily implemented approach to solve the SDVRP using an a priori split strategy, that is, each customer demand is split into small pieces in advance. Our computational experiments on 82 benchmark instances show that our algorithm is overall much more efficient and produces results that are comparable to those from the state-of-the-art approaches.

MSC:

90B06 Transportation, logistics and supply chain management
90C59 Approximation methods and heuristics in mathematical programming

Software:

VRPH
Full Text: DOI

References:

[1] Aleman, R., Hill, R., 2010. A tabu search with vocabulary building approach for the vehicle routing problem with split demands. International Journal of Metaheuristics1, 1, 55-80. · Zbl 1219.90018
[2] Aleman, R., Zhang, X., Hill, R., 2010. An adaptive memory algorithm for the split delivery vehicle routing problem. Journal of Heuristics16, 3, 441-473. · Zbl 1187.90036
[3] Archetti, C., Bianchessi, N., Speranza, M., 2011a. A column generation approach for the split delivery vehicle routing problem. Networks58, 4, 241-254. · Zbl 1231.90074
[4] Archetti, C., Bianchessi, N., Speranza, M., 2014. Branch‐and‐cut algorithms for the split delivery vehicle routing problem. Annals of Operations Research238, 3, 685-698. · Zbl 1338.90042
[5] Archetti, C., Feillet, D., Gendreau, M., Speranza, M., 2011b. Complexity of the VRP and SDVRP. Transportation Research Part C19, 5, 741-750.
[6] Archetti, C., Savelsbergh, M., Speranza, M., 2006a. Worst‐case analysis for split delivery vehicle routing problems. Transportation Science40, 2, 226-234.
[7] Archetti, C., Speranza, M., 2012. Vehicle routing problems with split deliveries. International Transactions in Operational Research39, 1, 3-22. · Zbl 1267.90030
[8] Archetti, C., Speranza, M., Hertz, A., 2006b. A tabu search algorithm for the split delivery vehicle routing problem. Transportation Science40, 1, 64-73.
[9] Archetti, C., Speranza, M., Savelsbergh, M., 2008. An optimization‐based heuristic for the split delivery vehicle routing problem. Transportation Science42, 1, 22-31.
[10] Belenguer, J., Martinez, M., Mota, E., 2000. A lower bound for the split delivery vehicle routing problem. Operations Research48, 5, 801-810. · Zbl 1106.90380
[11] Berbotto, L., García, S., Nogales, F., 2014. A randomized granular tabu search heuristic for the split delivery vehicle routing problem. Annals of Operations Research222, 1, 153-173. · Zbl 1303.90008
[12] Boudia, M., Prins, C., Reghioui, M., 2007. An effective memetic algorithm with population management for the split delivery vehicle routing problem. In Bartz‐Beielstein, T. (ed.), Blesa Aguilera, M. (ed.), Blum, C. (ed.), Naujoks, B. (ed.), Roli, A. (ed.), Rudolph, G. (ed.), Sampels, M. (ed.) (eds) Hybrid Metaheuristics, Vol. 4771 of Lecture Notes in Computer Science. Springer, Berlin/Heidelberg, pp. 16-30. · Zbl 1147.68303
[13] Burrows, W., 1988. The vehicle routing problem with loadsplitting: a heuristic approach. Proceedings of the 24th Annual Conference of the Operational Research Society of New Zealand, Auckland, pp. 33-38.
[14] Campos, V., Corberán, A., Mota, E., 2008. A scatter search algorithm for the split delivery vehicle routing problem. In Fink, A. (ed.), Rothlauf, F. (ed.) (eds) Advances in Computational Intelligence in Transport, Logistics, and Supply Chain Management, Vol. 144 of Studies in Computational Intelligence. Springer, Berlin/Heidelberg, pp. 137-152. · Zbl 1181.68267
[15] Chen, S., Golden, B., Wasil, E., 2007. The split delivery vehicle routing problem: applications, algorithms, test problems, and computational results. Networks49, 4, 318-329. · Zbl 1141.90335
[16] Derigs, U., Li, B., Vogel, U., 2010. Local search‐based metaheuristics for the split delivery vehicle routing problem. Journal of the Operational Research Society61, 9, 1356-1364.
[17] Dror, M., Trudeau, P., 1989. Savings by split delivery routing. Transportaion Science23, 2, 141-145. · Zbl 0668.90044
[18] Dror, M., Trudeau, P., 1990. Split delivery routing. Naval Research Logistics37, 3, 383-402. · Zbl 0692.90044
[19] Groër, C., 2011. VRPH. Available at http://www.coin‐or.org/projects/VRPH.xml (accessed August 1, 2014).
[20] Groër, C., Golden, B., Wasil, E., 2010. A library of local search heuristics for the vehicle routing problem. Mathematical Programming Computation2, 2, 79-101. · Zbl 1230.90033
[21] Jin, M., Liu, K., Eksioglu, B., 2008. A column generation approach for the split delivery vehicle routing problem. Operations Research Letters36, 2, 265-270. · Zbl 1144.90339
[22] Moreno, L., deAragão, M.P., Uchoa, E., 2010. Improved lower bounds for the split delivery vehicle routing problem. Operations Research Letters38, 4, 302-306. · Zbl 1193.90068
[23] Silva, M., Subramanian, A., Ochi, L., 2015. An iterated local search heuristic for the split delivery vehicle routing problem. Computers & Operations Research53, 234-249. · Zbl 1348.90129
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.