A Branch-and-Price Algorithm for the Vehicle Routing Problem with Stochastic Demands and Probabilistic Duration Constraints

References

• Adulyasak Y, Jaillet P (2016) Models and algorithms for stochastic and robust vehicle routing with deadlines. Transportation Sci. 50(2):608–626.Link, Google Scholar
• Agresti A, Coull BA (1998) Approximate is better than “exact” for interval estimation of binomial proportions. Amer. Statist. 52(2):119–126.Google Scholar
• Barnhart C, Johnson EL, Nemhauser GL, Savelsbergh MWP, Vance PH (1998) Branch-and-price: Column generation for solving huge integer programs. Oper. Res. 46(3):316–329.Link, Google Scholar
• Brown LD, Cai TT, DasGupta A (2001) Interval estimation for a binomial proportion. Statist. Sci. 16(2):101–117.Crossref, Google Scholar
• Desaulniers G, Desrosiers J, Solomon MM (2005) Column Generation (Springer, New York).Crossref, Google Scholar
• Dror M, Laporte G, Trudeau P (1989) Vehicle routing with stochastic demands: Properties and solution frameworks. Transportation Sci. 23(3):166–176.Link, Google Scholar
• 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–550.Crossref, Google Scholar
• Erera AL, Morales JC, Savelsbergh MWP (2010) The vehicle routing problem with stochastic demand and duration constraints. Transportation Sci. 44(4):474–492.Link, Google Scholar
• Errico F, Desaulniers G, Gendreau M, Rei W, Rousseau LM (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–66.Crossref, Google Scholar
• Errico F, Desaulniers G, Gendreau M, Rei W, Rousseau LM (2018) The vehicle routing problem with hard time windows and stochastic service times. Eur. J. Transportation Logist. 7(3):223–251.Crossref, Google Scholar
• Feller W (2008) An Introduction to Probability Theory and Its Applications, vol. 2 (John Wiley & Sons, Hoboken, NJ).Google Scholar
• Florio AM, Feillet D, Hartl RF (2018) The delivery problem: Optimizing hit rates in e-commerce deliveries. Transportation Res. Part B: Methodological 117:455–472.Crossref, Google Scholar
• Florio AM, Hartl RF, Minner S (2020a) New exact algorithm for the vehicle routing problem with stochastic demands. Transportation Sci. Forthcoming.Link, Google Scholar
• Florio AM, Hartl RF, Minner S (2020b) Optimal a priori tour and restocking policy for the single-vehicle routing problem with stochastic demands. Eur. J. Oper. Res. 285(1):172–182.Crossref, Google Scholar
• 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–153.Crossref, Google Scholar
• Gendreau M, Jabali O, Rei W (2016) 50th anniversary invited article—future research directions in stochastic vehicle routing. Transportation Sci. 50(4):1163–1173.Link, Google Scholar
• Goodson JC, Ohlmann JW, Thomas BW (2013) Rollout policies for dynamic solutions to the multivehicle routing problem with stochastic demand and duration limits. Oper. Res. 61(1):138–154.Link, Google Scholar
• Goodson JC, Thomas BW, Ohlmann JW (2016) Restocking-based rollout policies for the vehicle routing problem with stochastic demand and duration limits. Transportation Sci. 50(2):591–607.Link, Google Scholar
• Gunawan A, Lau HC, Vansteenwegen P (2016) Orienteering problem: A survey of recent variants, solution approaches and applications. Eur. J. Oper. Res. 255(2):315–332.Crossref, Google Scholar
• 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–136.Crossref, Google Scholar
• Laporte G, Martello S (1990) The selective travelling salesman problem. Discrete Appl. Math. 26(2-3):193–207.Crossref, Google Scholar
• Li X, Tian P, Leung SC (2010) Vehicle routing problems with time windows and stochastic travel and service times: Models and algorithm. Internat. J. Production Econom. 125(1):137–145.Crossref, Google Scholar
• Louveaux FV, Salazar-González JJ (2018) Exact approach for the vehicle routing problem with stochastic demands and preventive returns. Transportation Sci. 52(6):1463–1478.Link, Google Scholar
• Lübbecke ME, Desrosiers J (2005) Selected topics in column generation. Oper. Res. 53(6):1007–1023.Link, Google Scholar
• Mendoza JE, Rousseau LM, Villegas JG (2016) A hybrid metaheuristic for the vehicle routing problem with stochastic demand and duration constraints. J. Heuristics 22(4):539–566.Crossref, Google Scholar
• Oyola J, Arntzen H, Woodruff DL (2017) The stochastic vehicle routing problem, a literature review, part II: Solution methods. Eur. J. Transportation Logist. 6(4):349–388.Crossref, Google Scholar
• Oyola J, Arntzen H, Woodruff DL (2018) The stochastic vehicle routing problem, a literature review, part I: Models. Eur. J. Transportation Logist. 7(3):193–221.Crossref, Google Scholar
• Poggi M, Uchoa E (2014) New exact algorithms for the capacitated vehicle routing problem. Toth P, Vigo D, eds. Vehicle Routing: Problems, Methods, and Applications, MOS-SIAM Series on Optimization (SIAM, Philadelphia), 59–86.Crossref, Google Scholar
• Salavati-Khoshghalb M, Gendreau M, Jabali O, Rei W (2019) An exact algorithm to solve the vehicle routing problem with stochastic demands under an optimal restocking policy. Eur. J. Oper. Res. 273(1):175–189.Crossref, Google Scholar
• Solomon MM (1987) Algorithms for the vehicle routing and scheduling problems with time window constraints. Oper. Res. 35(2):254–265.Link, Google Scholar
• Tan KC, Cheong CY, Goh CK (2007) Solving multiobjective vehicle routing problem with stochastic demand via evolutionary computation. Eur. J. Oper. Res. 177(2):813–839.Crossref, Google Scholar
• 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–224.Crossref, Google Scholar
• 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. Transportation Res. Part C: Emerging Tech. 48:66–83.Crossref, Google Scholar
• 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–799.Crossref, Google Scholar
• Vareias AD, Repoussis PP, Tarantilis CD (2019) Assessing customer service reliability in route planning with self-imposed time windows and stochastic travel times. Transportation Sci. 53(1):256–281.Link, Google Scholar
• Yang WH, Mathur K, Ballou RH (2000) Stochastic vehicle routing problem with restocking. Transportation Sci. 34(1):99–112.Link, Google Scholar
• Yee JR, Golden BL (1980) A note on determining operating strategies for probabilistic vehicle routing. Naval Res. Logist. Quart. 27(1):159–163.Crossref, Google Scholar
• Zhang J, Lam WH, Chen BY (2013) A stochastic vehicle routing problem with travel time uncertainty: Trade-off between cost and customer service. Networks Spatial Econom. 13(4):471–496.Crossref, Google Scholar