×

New exact solution approaches for the split delivery vehicle routing problem. (English) Zbl 1393.90015

Summary: In this study, we propose exact solution methods for the split delivery vehicle routing problem (SDVRP). We first give a new vehicle-indexed flow formulation for the problem and then a relaxation obtained by aggregating the vehicle-indexed variables over all vehicles. This relaxation may have optimal solutions where several vehicles exchange loads at some customers. We cut off such solutions, in a nontraditional way, either by extending the formulation locally with vehicle-indexed variables or by node splitting. We compare these approaches using instances from the literature and new randomly generated instances. Additionally, we introduce two new extensions of the SDVRP by restricting the number of splits and by relaxing the depot return requirement and modify our algorithms to handle these extensions.

MSC:

90B06 Transportation, logistics and supply chain management
90C10 Integer programming
90-04 Software, source code, etc. for problems pertaining to operations research and mathematical programming
90-08 Computational methods for problems pertaining to operations research and mathematical programming

Software:

VRP
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] Aleman RE, Hill RR (2010) A tabu search with vocabulary building approach for the vehicle routing problem with split demands. Int J Metaheuristics 1(1):55-80 · Zbl 1219.90018 · doi:10.1504/IJMHEUR.2010.033123
[2] Aleman RE, Zhang X, Hill RR (2010) An adaptive memory algorithm for the split delivery vehicle routing problem. J Heuristics 16(3):441-473 · Zbl 1187.90036 · doi:10.1007/s10732-008-9101-3
[3] Archetti C, Speranza MG (2012) Vehicle routing problems with split deliveries. Int Trans Oper Res 19(1-2):3-22 · Zbl 1267.90030 · doi:10.1111/j.1475-3995.2011.00811.x
[4] Archetti C, Speranza MG, Hertz A (2006) A tabu search algorithm for the split delivery vehicle routing problem. Transp Sci 40(1):64-73 · doi:10.1287/trsc.1040.0103
[5] Archetti C, Speranza MG, Savelsbergh MWP (2008) An optimization-based heuristic for the split delivery vehicle routing problem. Transp Sci 42(1):22-31 · doi:10.1287/trsc.1070.0204
[6] Archetti C, Bianchessi N, Speranza MG (2011) A column generation approach for the split delivery vehicle routing problem. Networks 58(4):241-254 · Zbl 1231.90074 · doi:10.1002/net.20467
[7] Archetti C, Bianchessi N, Speranza MG (2014) Branch-and-cut algorithms for the split delivery vehicle routing problem. Eur J Oper Res 238(3):685-698 · Zbl 1338.90042 · doi:10.1016/j.ejor.2014.04.026
[8] Atamtürk A (2002) On capacitated network design cut-set polyhedra. Math Program 92(3):425-437 · Zbl 1008.90003 · doi:10.1007/s101070100284
[9] Belenguer JM, Martinez MC, Mota E (2000) A lower bound for the split delivery vehicle routing problem. Oper Res 48(5):801-810 · Zbl 1106.90380 · doi:10.1287/opre.48.5.801.12407
[10] Berbotto L, García S, Nogales FJ (2014) A randomized granular tabu search heuristic for the split delivery vehicle routing problem. Ann Oper Res 222(1):153-173 · Zbl 1303.90008 · doi:10.1007/s10479-012-1282-3
[11] Boudia M, Prins C, Reghioui M (2007) An effective memetic algorithm with population management for the split delivery vehicle routing problem. In: Hybrid metaheuristics. Springer, pp 16-30
[12] Brandão J (2004) A tabu search algorithm for the open vehicle routing problem. Eur J Oper Res 157(3):552-564 · Zbl 1068.90026 · doi:10.1016/S0377-2217(03)00238-8
[13] Ceselli A, Righini G, Salani M (2009a) Column generation for the split delivery vehicle routing problem. Technical report, University of Milan-DTI-Note del Polo · Zbl 1144.90339
[14] Ceselli A, Righini G, Salani M (2009b) A column generation algorithm for a rich vehicle-routing problem. Transp Sci 43(1):56-69 · doi:10.1287/trsc.1080.0256
[15] Chen S, Golden B, Wasil E (2007) The split delivery vehicle routing problem: applications, algorithms, test problems, and computational results. Networks 49(4):318-329 · Zbl 1141.90335 · doi:10.1002/net.20181
[16] Chen Q, Li K, Liu Z (2014) Model and algorithm for an unpaired pickup and delivery vehicle routing problem with split loads. Transpn Rese E Logist Transpo Revi 69:218-235 · doi:10.1016/j.tre.2014.06.010
[17] Desaulniers G (2010) Branch-and-price-and-cut for the split-delivery vehicle routing problem with time windows. Oper Res 58(1):179-192 · Zbl 1233.90065 · doi:10.1287/opre.1090.0713
[18] Dror M, Trudeau P (1989) Savings by split delivery routing. Transp Sci 23(2):141-145 · Zbl 0668.90044 · doi:10.1287/trsc.23.2.141
[19] Dror, M.; Trudeau, P., No article title, Split delivery routing. Nav Res Logist, 37, 383-402 (1990) · Zbl 0692.90044 · doi:10.1002/nav.3800370304
[20] Dror M, Laporte G, Trudeau P (1994) Vehicle routing with split deliveries. Discrete Appl Math 50(3):239-254 · Zbl 0801.90082 · doi:10.1016/0166-218X(92)00172-I
[21] Fu Z, Eglese R, Li LY (2005) A new tabu search heuristic for the open vehicle routing problem. J Oper Res Soc 56(3):267-274 · Zbl 1114.90003 · doi:10.1057/palgrave.jors.2601817
[22] Gouveia L (1995) A result on projection for the vehicle routing problem. Eur J Oper Res 85(3):610-624 · Zbl 0912.90118 · doi:10.1016/0377-2217(94)00025-8
[23] Gulczynski D, Golden B, Wasil E (2010) The split delivery vehicle routing problem with minimum delivery amounts. Transp Res E Logist Transpo Rev 46(5):612-626 · doi:10.1016/j.tre.2009.12.007
[24] Jin M, Liu K, Bowden RO (2007) A two-stage algorithm with valid inequalities for the split delivery vehicle routing problem. Int J Prod Econ 105(1):228-242 · doi:10.1016/j.ijpe.2006.04.014
[25] Jin M, Liu K, Eksioglu B (2008) A column generation approach for the split delivery vehicle routing problem. Oper Res Lett 36(2):265-270 · Zbl 1144.90339 · doi:10.1016/j.orl.2007.05.012
[26] Khmelev A, Kochetov Y (2015) A hybrid local search for the split delivery vehicle routing problem. Int J Artif Intell 13(1):147-164 · Zbl 1362.90091
[27] Lee C, Epelman MA, White CC, Bozer YA (2006) A shortest path approach to the multiple-vehicle routing problem with split pick-ups. Transp Res B Methodol 40(4):265-284 · doi:10.1016/j.trb.2004.11.004
[28] Letchford AN, Salazar-González JJ (2006) Projection results for vehicle routing. Math Program 105(2-3):251-274 · Zbl 1085.90032 · doi:10.1007/s10107-005-0652-x
[29] Letchford AN, Lysgaard J, Eglese RW (2007) A branch-and-cut algorithm for the capacitated open vehicle routing problem. J Oper Res Soc 58(12):1642-1651 · doi:10.1057/palgrave.jors.2602345
[30] Li F, Golden B, Wasil E (2007) The open vehicle routing problem: algorithms, large-scale test problems, and computational results. Comput Oper Res 34(10):2918-2930 · Zbl 1185.90173 · doi:10.1016/j.cor.2005.11.018
[31] Moreno L, Aragão MP, Uchoa E (2010) Improved lower bounds for the split delivery vehicle routing problem. Oper Res Lett 38(4):302-306 · Zbl 1193.90068 · doi:10.1016/j.orl.2010.04.008
[32] Mota E, Campos V, Corberán Á (2007) A new metaheuristic for the vehicle routing problem with split demands. In: Evolutionary computation in combinatorial optimization. Springer, pp 121-129
[33] Naddef D, Rinaldi G (2002) Branch-and-cut algorithms for the capacitated VRP. In: Toth P, Vigo D (eds) The vehicle routing problem, SIAM monographs on discrete mathematics and applications. SIAM, Philadelphia, PA, USA, pp 53-81 · Zbl 1076.90550
[34] Ozdamar L, Demir O (2012) A hierarchical clustering and routing procedure for large scale disaster relief logistics planning. Transp Res E Logist Transp Revi 48(3):591-602 · doi:10.1016/j.tre.2011.11.003
[35] Ralphs TK, Kopman L, Pulleyblank WR, Trotter LE (2003) On the capacitated vehicle routing problem. Math Program 94(2-3):343-359 · Zbl 1030.90131 · doi:10.1007/s10107-002-0323-0
[36] Sahin M, Cavuslar G, Oncan T, Sahin G, Tuzun D (2013) Aksu. An efficient heuristic for the multi-vehicle one-to-one pickup and delivery problem with split loads. Transp Res C Emerg Technol 27:169-188 · doi:10.1016/j.trc.2012.04.014
[37] Sariklis D, Powell S (2000) A heuristic method for the open vehicle routing problem. J Oper Res Soc 51(5):564-573 · Zbl 1055.90530 · doi:10.1057/palgrave.jors.2600924
[38] Schrage L (1981) Formulation and structure of more complex/realistic routing and scheduling problems. Networks 11(2):229-232 · doi:10.1002/net.3230110212
[39] Sierksma G, Tijssen GA (1998) Routing helicopters for crew exchanges on off-shore locations. Ann Oper Res 76:261-286 · Zbl 0895.90133 · doi:10.1023/A:1018900705946
[40] Silva MM, Subramanian A, Ochi LS (2015) An iterated local search heuristic for the split delivery vehicle routing problem. Comput Oper Res 53:234-249 · Zbl 1348.90129 · doi:10.1016/j.cor.2014.08.005
[41] Song Q, Liu L (2013) The application of tabu search algorithm on split delivery open vehicle routing problem. BioTechnology 8(8):1088-1094
[42] Tarantilis CD, Kiranoudis CT (2002) Distribution of fresh meat. J Food Eng 51(1):85-91 · doi:10.1016/S0260-8774(01)00040-1
[43] Wang H, Du L, Ma S (2014) Multi-objective open location-routing model with split delivery for optimized relief distribution in post-earthquake. Transp Res E Logist Transp Rev 69:160-179 · doi:10.1016/j.tre.2014.06.006
[44] Wilck JH IV, Cavalier TM (2012a) A genetic algorithm for the split delivery vehicle routing problem. Am J Oper Res 2:207-216 · doi:10.4236/ajor.2012.22024
[45] Wilck JH IV, Cavalier TM (2012b) A construction heuristic for the split delivery vehicle routing problem. Am J Oper Res 2:153-162 · doi:10.4236/ajor.2012.22018
[46] Yi W, Kumar A (2007) Ant colony optimization for disaster relief operations. Transp Res E Logist Transp Rev 43(6):660-672 · doi:10.1016/j.tre.2006.05.004
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.