New exact solution approaches for the split delivery vehicle routing problem
Tóm tắt
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.
Tài liệu tham khảo
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
Aleman RE, Zhang X, Hill RR (2010) An adaptive memory algorithm for the split delivery vehicle routing problem. J Heuristics 16(3):441–473
Archetti C, Speranza MG (2012) Vehicle routing problems with split deliveries. Int Trans Oper Res 19(1–2):3–22
Archetti C, Speranza MG, Hertz A (2006) A tabu search algorithm for the split delivery vehicle routing problem. Transp Sci 40(1):64–73
Archetti C, Speranza MG, Savelsbergh MWP (2008) An optimization-based heuristic for the split delivery vehicle routing problem. Transp Sci 42(1):22–31
Archetti C, Bianchessi N, Speranza MG (2011) A column generation approach for the split delivery vehicle routing problem. Networks 58(4):241–254
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
Atamtürk A (2002) On capacitated network design cut-set polyhedra. Math Program 92(3):425–437
Belenguer JM, Martinez MC, Mota E (2000) A lower bound for the split delivery vehicle routing problem. Oper Res 48(5):801–810
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
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
Brandão J (2004) A tabu search algorithm for the open vehicle routing problem. Eur J Oper Res 157(3):552–564
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
Ceselli A, Righini G, Salani M (2009b) A column generation algorithm for a rich vehicle-routing problem. Transp Sci 43(1):56–69
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
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
Desaulniers G (2010) Branch-and-price-and-cut for the split-delivery vehicle routing problem with time windows. Oper Res 58(1):179–192
Dror M, Trudeau P (1989) Savings by split delivery routing. Transp Sci 23(2):141–145
Dror M, Trudeau P (1990) Split delivery routing. Nav Res Logist 37(3):383–402
Dror M, Laporte G, Trudeau P (1994) Vehicle routing with split deliveries. Discrete Appl Math 50(3):239–254
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
Gouveia L (1995) A result on projection for the vehicle routing problem. Eur J Oper Res 85(3):610–624
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
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
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
Khmelev A, Kochetov Y (2015) A hybrid local search for the split delivery vehicle routing problem. Int J Artif Intell 13(1):147–164
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
Letchford AN, Salazar-González JJ (2006) Projection results for vehicle routing. Math Program 105(2–3):251–274
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
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
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
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
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
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
Ralphs TK, Kopman L, Pulleyblank WR, Trotter LE (2003) On the capacitated vehicle routing problem. Math Program 94(2–3):343–359
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
Sariklis D, Powell S (2000) A heuristic method for the open vehicle routing problem. J Oper Res Soc 51(5):564–573
Schrage L (1981) Formulation and structure of more complex/realistic routing and scheduling problems. Networks 11(2):229–232
Sierksma G, Tijssen GA (1998) Routing helicopters for crew exchanges on off-shore locations. Ann Oper Res 76:261–286
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
Song Q, Liu L (2013) The application of tabu search algorithm on split delivery open vehicle routing problem. BioTechnology 8(8):1088–1094
Tarantilis CD, Kiranoudis CT (2002) Distribution of fresh meat. J Food Eng 51(1):85–91
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
Wilck JH IV, Cavalier TM (2012a) A genetic algorithm for the split delivery vehicle routing problem. Am J Oper Res 2:207–216
Wilck JH IV, Cavalier TM (2012b) A construction heuristic for the split delivery vehicle routing problem. Am J Oper Res 2:153–162
Yi W, Kumar A (2007) Ant colony optimization for disaster relief operations. Transp Res E Logist Transp Rev 43(6):660–672