nach oben

EURO Journal on Transportation and Logistics

Erschienen in:

02.11.2016 | Survey

The stochastic vehicle routing problem, a literature review, Part II: solution methods

verfasst von: Jorge Oyola, Halvard Arntzen, David L. Woodruff

Erschienen in: EURO Journal on Transportation and Logistics | Ausgabe 4/2017

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

Building on the work of Gendreau et al. (Oper Res 44(3):469–477, 1996), and complementing the first part of this survey, we review the solution methods used for the past 20 years in the scientific literature on stochastic vehicle routing problems (SVRP). We describe the methods and indicate how they are used when dealing with stochastic vehicle routing problems.

Vorheriger Artikel New models and algorithms for the container stack rearrangement problem by yard cranes in maritime ports

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Adulyasak Y, Jaillet P (2016) Models and algorithms for stochastic and robust vehicle routing with deadlines. Transp Sci 50(2):608–626CrossRef

Ahmadi-Javid A, Seddighi AH (2013) A location-routing problem with disruption risk. Transp Res Part E Log Transp Rev 53:63–82CrossRef

Ak A, Erera AL (2007) A paired-vehicle recourse strategy for the vehicle-routing problem with stochastic demands. Transp Sci 41(2):222–237CrossRef

Ando N, Taniguchi E (2006) Travel time reliability in vehicle routing and scheduling with time windows. Netw Spat Econ 6(3–4):293–311CrossRef

Beraldi P, Ghiani G, Musmanno R, Vocaturo F (2010) Efficient neighborhood search for the probabilistic multi-vehicle pickup and delivery problem. Asia Pac J Oper Res 27(3):301–314CrossRef

Beraldi P, Bruni ME, Lagana D, Musmanno R (2015) The mixed capacitated general routing problem under uncertainty. Eur J Oper Res 240(2):382–392CrossRef

Bertsimas D, Chervi P, Peterson M (1995) Computational approaches to stochastic vehicle routing problems. Transp Sci 29(4):342–352CrossRef

Bianchi L, Birattari M, Chiarandini M, Manfrin M, Mastrolilli M, Paquete L, Rossi-Doria O, Schiavinotto T (2005) Hybrid metaheuristics for the vehicle routing problem with stochastic demands. Technical report, Dalle Molle Institute for Artificial Intelligence, Manno

Chang MS (2005) A vehicle routing problem with time windows and stochastic demands. J Chin Inst Eng 28(5):783–794CrossRef

Chang TS, Wan YW, Ooi WT (2009) A stochastic dynamic traveling salesman problem with hard time windows. Eur J Oper Res 198(3):748–759

Chen L, Ha MH, Langevin A, Gendreau M (2014) Optimizing road network daily maintenance operations with stochastic service and travel times. Transp Res Part E Log Transp Rev 64:88–102

Chepuri K, Homem-de Mello T (2005) Solving the vehicle routing problem with stochastic demands using the cross-entropy method. Ann Oper Res 134(1):153–181CrossRef

Christiansen CH, Lysgaard J (2007) A branch-and-price algorithm for the capacitated vehicle routing problem with stochastic demands. Oper Res Lett 35(6):773–781CrossRef

Christiansen CH, Lysgaard J, Wøhlk S (2009) A branch-and-price algorithm for the capacitated arc routing problem with stochastic demands. Oper Res Lett 37(6):392–398CrossRef

Clarke C, Wright J (1964) Scheduling of vehicles from a central depot to a number of delivery points. Oper Res 12:432–441CrossRef

Cordeau J-F, Gendreau M, Laporte G, Potvin J-Y, Semet F (2002) A guide to vehicle routing heuristics. J Oper Res Soc 53(5):512

Dantzig GB, Ramser JH (1959) The truck dispatching problem. Manag Sci (pre-1986) 6(1):80

Desrochers M (1988) An algorithm for the shortest path problem with resource constraints. In: Technical report, Cahiers du GERAD G-88-27, University of Montreal

Dueck G (1993) New optimization heuristics: the Great Deluge algorithm and the record-to-record travel. J Comput Phys 104(1):86–92CrossRef

Ehmke JF, Campbell AM, Urban TL (2015) Ensuring service levels in routing problems with time windows and stochastic travel times. Eur J Oper Res 240(2):539–550CrossRef

Eksioglu B, Vural AV, Reisman A (2009) The vehicle routing problem: a taxonomic review. Comput Ind Eng 57(4):1472–1483CrossRef

Erera AL, Savelsbergh M, Uyar E (2009) Fixed routes with backup vehicles for stochastic vehicle routing problems with time constraints. Networks 54(4):270–283CrossRef

Erera AL, Morales JC, Savelsbergh M (2010) The vehicle routing problem with stochastic demand and duration constraints. Transp Sci 44(4):474–492CrossRef

Errico F, Desaulniers G, Gendreau M, Rei W, Rousseau L-M (2016) A priori optimization with recourse for the vehicle routing problem with hard time windows and stochastic service times. Eur J Oper Res 249(1):55–66CrossRef

Fallahi AE, Prins C, Wolfler Calvo R (2008) A memetic algorithm and a tabu search for the multi-compartment vehicle routing problem. Comput Oper Res 35(5):1725–1741CrossRef

Feillet D, Dejax P, Gendreau M, Gueguen C (2004) An exact algorithm for the elementary shortest path problem with resource constraints: application to some vehicle routing problems. Networks 44(3):216–229CrossRef

Fleury G, Lacomme P, Prins C, Randame-Chérif W (2002) Robustness evaluation of solutions for the capacitated arc routing problem. In: Barros FJ, Gambiasi N (eds) Simulation and planning in high autonomy systems. CARP, Lisbon

Fleury G, Lacomme P, Prins C (2004) Evolutionary algorithms for stochastic arc routing problems. Lecture notes in computer science, vol 3005. Springer, Berlin, pp 501–512

Fleury G, Lacomme P, Prins C, Ramdane-Cérif W (2005) Improving robustness of solutions to arc routing problems. J Oper Res Soc 56(5):526–538

Fleury G, Philippe L, Prins C (2005) Stochastic capacitated arc routing problem. In: Technical report LIMOS/RR-05-12, Laboratorie d’informatique (LIMOS), Université Blaise Pascal

Gauvin C, Desaulniers G, Gendreau M (2014) A branch-cut-and-price algorithm for the vehicle routing problem with stochastic demands. Comput Oper Res 50:141–153CrossRef

Gendreau M, Laporte G, Seguin R (1996) A tabu search heuristic for the vehicle routing problem with stochastic demands and customers. Oper Res 44(3):469–477CrossRef

Gendreau M, Jabali O, Rei W (2014) Stochastic vehicle routing problems. In: Toth P, Vigo D (eds) Vehicle routing: problems, methods, and applications, 2nd edn, Society for Industrial and Applied Mathematics, pp 213–239

Gómez A, No RM, Akhavan-Tabatabaei R, Medaglia AL, Mendoza JE (2016) On modeling stochastic travel and service times in vehicle routing. Transp Sci 50(2):627–641

Goodson JC (2015) A priori policy evaluation and cyclic-order-based simulated annealing for the multi-compartment vehicle routing problem with stochastic demands. Eur J Oper Res 241(2):361–369CrossRef

Goodson JC, Ohlmann JW, Thomas BW (2012) Cyclic-order neighborhoods with application to the vehicle routing problem with stochastic demand. Eur J Oper Res 217(2):312–323CrossRef

Gounaris CE, Wiesemann W, Floudas CA (2013) The robust capacitated vehicle routing problem under demand uncertainty. Oper Res 61(3):677–693CrossRef

Groër C, Golden B, Wasil E (2009) The consistent vehicle routing problem. Manuf Serv Oper Manag 11(4):630–643CrossRef

Haugland D, Ho SC, Laporte G (2007) Designing delivery districts for the vehicle routing problem with stochastic demands. Eur J Oper Res 180(3):997–1010CrossRef

Hjorring C, Holt J (1999) New optimality cuts for a single-vehicle stochastic routing problem. Ann Oper Res 86:569–584CrossRef

Hvattum LM, Løkketangen A, Laporte G (2006) Solving a dynamic and stochastic vehicle routing problem with a sample scenario hedging heuristic. Transp Sci 40(4):421–438CrossRef

Jabali O, Rei W, Gendreau M, Laporte G (2014) Partial-route inequalities for the multi-vehicle routing problem with stochastic demands. Discrete Appl Math 177:121–136CrossRef

Juan A, Faulin J, Grasman S, Riera D, Marull J, Mendez C (2011) Using safety stocks and simulation to solve the vehicle routing problem with stochastic demands. Transp Res Part C Emerg Technol 19(5):751–765 (Freight Transportation and Logistics (selected papers from ODYSSEUS 2009—the 4th international workshop on Freight Transportation and Logistics)

Kenyon AS, Morton DP (2003) Stochastic vehicle routing with random travel times. Transp Sci 37(1):69–82CrossRef

Lacomme P, Prins C, Ramdane-Chérif W (2001) A genetic algorithm for the capacitated arc routing problem and its extensions. In: Boers E (ed) Lecture notes in computer science, vol 2037. Springer, Berlin, pp 473–483

Laporte G, Louveaux FV, Hamme LV (2002) An integer L-shaped algorithm for the capacitated vehicle routing problem with stochastic demands. Oper Res 50(3):415–423CrossRef

Laporte G, Musmanno R, Vocaturo F (2010) An adaptive large neighbourhood search heuristic for the capacitated arc-routing problem with stochastic demands. Transp Sci 44(1):125–135CrossRef

Lecluyse C, Van Woensel T, Peremans H (2009) Vehicle routing with stochastic time-dependent travel times. 4OR 7(4):363–377

Lee C, Lee K, Park S (2012) Robust vehicle routing problem with deadlines and travel time/demand uncertainty. J Oper Res Soc 63(9):1294–1306CrossRef

Lei H, Laporte G, Guo B (2011) The capacitated vehicle routing problem with stochastic demands and time windows. Comput Oper Res 38(12):1775–1783CrossRef

Lei H, Laporte G, Guo B (2012) A generalized variable neighborhood search heuristic for the capacitated vehicle routing problem with stochastic service times. TOP 20(3):99–118CrossRef

Li X, Tian P, Leung SC (2010) Vehicle routing problems with time windows and stochastic travel and service times: models and algorithm. Int J Prod Econ 125(1):137–145CrossRef

Maden W, Eglese R, Black D (2010) Vehicle routing and scheduling with time-varying data: a case study. J Oper Res Soc 61(3):515–522CrossRef

Marinakis Y, Iordanidou G-R, Marinaki M (2013) Particle swarm optimization for the vehicle routing problem with stochastic demands. Appl Soft Comput 13(4):1693–1704CrossRef

Mendoza J, Villegas J (2013) A multi-space sampling heuristic for the vehicle routing problem with stochastic demands. Optim Lett 7(7):1503–1516CrossRef

Mendoza JE, Castanier B, Guéret C, Medaglia AL, Velasco N (2010) A memetic algorithm for the multi-compartment vehicle routing problem with stochastic demands. Comput Oper Res 37(11):1886–1898CrossRef

Mendoza JE, Castanier B, Guéret C, Medaglia AL, Velasco N (2011) Constructive heuristics for the multicompartment vehicle routing problem with stochastic demands. Transp Sci 45(3):346–363CrossRef

Mendoza J, Rousseau L-M, Villegas J (2015) A hybrid metaheuristic for the vehicle routing problem with stochastic demand and duration constraints. J Heuristics 1–28

Miranda DM, Conceição SV (2016) The vehicle routing problem with hard time windows and stochastic travel and service time. Expert Syst Appl 64:104–116CrossRef

Novoa C, Storer R (2009) An approximate dynamic programming approach for the vehicle routing problem with stochastic demands. Eur J Oper Res 196(2):509–515CrossRef

Oyola J, Arntzen H, Woodruff DL (2016) The stochastic vehicle routing problem, a literature review, part I: models. EURO J Transp Logist. doi:10.1007/s13676-016-0100-5

Prins C (2004) A simple and effective evolutionary algorithm for the vehicle routing problem. Comput Oper Res 31(12):1985–2002CrossRef

Rei W, Gendreau M, Soriano P (2007) Local branching cuts for the 0–1 integer L-shaped algorithm. In: Technical report, CIRRELT-2007-23, Centre interuniversitaire de recherche sur les réseaux d’enterprise, la logistique et le transport, vol 44(1), pp 136–146

Rei W, Gendreau M, Soriano P (2010) A hybrid Monte Carlo local branching algorithm for the single vehicle routing problem with stochastic demands. Transp Sci 44(1):136–146CrossRef

Resende MGC, Celso CR (2010) Greedy randomized adaptive search procedures: advances, hybridizations, and applications. In: Gendreau M, Potvin J-Y (eds) Handbook of metaheuristics. Springer, New York, pp 283–319

Ritzinger U, Puchinger J, Hartl RF (2016) A survey on dynamic and stochastic vehicle routing problems. Int J Prod Res 54:215–231CrossRef

Rockafellar R, Wets R-B (1991) Scenarios and policy aggregation in optimization under uncertainty. Math Oper Res 16(1):119–147CrossRef

Rubinstein R (1999) The cross-entropy method for combinatorial and continuous optimization. Methodol Comput Appl Probab 1(2):127–190CrossRef

Russell RA, Urban TL (2008) Vehicle routing with soft time windows and erlang travel times. J Oper Res Soc 59(9):1220–1228CrossRef

Secomandi N (2000) Comparing neuro-dynamic programming algorithms for the vehicle routing problem with stochastic demands. Comput Oper Res 27(1112):1201–1225

Secomandi N (2001) A rollout policy for the vehicle routing problem with stochastic demands. Oper Res 49(5):796–802CrossRef

Secomandi N (2003) Analysis of a rollout approach to sequencing problems with stochastic routing applications. J Heuristics 9(4):321–352CrossRef

Secomandi N, Margot F (2009) Reoptimization approaches for the vehicle-routing problem with stochastic demands. Oper Res 57(1):214–230CrossRef

Solano-Charris E, Prins C, Santos AC (2015) Local search based metaheuristics for the robust vehicle routing problem with discrete scenarios. Appl Soft Comput 32:518–531CrossRef

Solomon MM (1987) Algorithms for the vehicle routing and scheduling problems with time window constraints. Oper Res 35(2):254

Sörensen K, Sevaux M (2009) A practical approach for robust and flexible vehicle routing using metaheuristics and Monte Carlo sampling. J Math Model Algorithms 8(4):387–407CrossRef

Sungur I, Ordóñez F, Dessouky M (2008) A robust optimization approach for the capacitated vehicle routing problem with demand uncertainty. IIE Trans 40:509–523CrossRef

Sungur I, Ren Y, Ordez F, Dessouky M, Zhong H (2010) A model and algorithm for the courier delivery problem with uncertainty. Transp Sci 44(2):193–205

Taş D, Dellaert N, van Woensel T, de Kok T (2013) Vehicle routing problem with stochastic travel times including soft time windows and service costs. Comput Oper Res 40(1):214–224CrossRef

Taş D, Dellaert N, van Woensel T, de Kok T (2014a) The time-dependent vehicle routing problem with soft time windows and stochastic travel times. Transp Res Part C Emerg Technol 48:66–83CrossRef

Taş D, Gendreau M, Dellaert N, van Woensel T, de Kok A (2014b) Vehicle routing with soft time windows and stochastic travel times: a column generation and branch-and-price solution approach. Eur J Oper Res 236(3):789–799CrossRef

Tan K, Cheong C, Goh C (2007) Solving multiobjective vehicle routing problem with stochastic demand via evolutionary computation. Eur J Oper Res 177(2):813–839CrossRef

Toth P, Vigo D (1998) Exact algorithms for vehicle routing. In: Crainic T, Laporte G (eds) Fleet management and logistics. Kluwer Academic Publishers, New York, pp 1–31

Toth P, Vigo D (2002) Models, relaxations and exact approaches for the capacitated vehicle routing problem. Discrete Appl Math 123(1–3):487–512CrossRef

Voß S, Fink A, Duin C (2005) Looking ahead with the pilot method. Ann Oper Res 136(1):285–302CrossRef

Woensel TV, Kerbache L, Peremans H, Vandaele N (2007) A queueing framework for routing problems with time-dependent travel times. J Math Model Algorithms 6(1):151–173CrossRef

Yan S, Wang S-S, Chang Y-H (2014) Cash transportation vehicle routing and scheduling under stochastic travel times. Eng Optim 46(3):289–307CrossRef

Yang W-H, Mathur K, Ballou RH (2000) Stochastic vehicle routing problem with restocking. Transp Sci 34(1):99–112CrossRef

Zhang T, Chaovalitwongse W, Zhang Y (2012) Scatter search for the stochastic travel-time vehicle routing problem with simultaneous pick-ups and deliveries. Comput Oper Res 39(10):2277–2290CrossRef

Zhang J, Lam WHK, Chen BY (2013) A stochastic vehicle routing problem with travel time uncertainty: trade-off between cost and customer service. Netw Spat Econ 13(4):471–496CrossRef

Zhong H, Hall RW, Dessouky M (2007) Territory planning and vehicle dispatching with driver learning. Transp Sci 41(1):74–89CrossRef

Zhu L, Rousseau L-M, Rei W, Li B (2014) Paired cooperative reoptimization strategy for the vehicle routing problem with stochastic demands. Comput Oper Res 50:1–13CrossRef

Titel: The stochastic vehicle routing problem, a literature review, Part II: solution methods
verfasst von: Jorge Oyola
Halvard Arntzen
David L. Woodruff
Publikationsdatum: 02.11.2016
Verlag: Springer Berlin Heidelberg
Erschienen in: EURO Journal on Transportation and Logistics / Ausgabe 4/2017
Print ISSN: 2192-4376
Elektronische ISSN: 2192-4384
DOI: https://doi.org/10.1007/s13676-016-0099-7