Generalized Riskiness Index in Vehicle Routing Under Uncertain Travel Times: Formulations, Properties, and Exact Solution Framework

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
• Agra A, Christiansen M, Figueiredo R, Hvattum LM, Poss M, Requejo C (2012) Layered formulation for the robust vehicle routing problem with time windows. Combinatorial Optimization. ISCO 2012, Lecture Notes in Computer Science (Springer, Berlin, Heidelberg), 249–260.Crossref, Google Scholar
• Agra A, Christiansen M, Figueiredo R, Hvattum LM, Poss M, Requejo C (2013) The robust vehicle routing problem with time windows. Comput. Oper. Res. 40(3):856–866.Crossref, Google Scholar
• Archetti C, Bouchard M, Desaulniers G (2011) Enhanced branch and price and cut for vehicle routing with split deliveries and time windows. Transportation Sci. 45(3):285–298.Link, Google Scholar
• Aumann RJ, Serrano R (2008) An economic index of riskiness. J. Political Econom. 116(5):810–836.Crossref, Google Scholar
• Baldacci R, Christofides N, Mingozzi A (2008) An exact algorithm for the vehicle routing problem based on the set partitioning formulation with additional cuts. Math. Programming 115:351–385.Crossref, Google Scholar
• Baldacci R, Mingozzi A, Roberti R (2011) New route relaxation and pricing strategies for the vehicle routing problem. Oper. Res. 59(5):1269–1283.Link, Google Scholar
• Baldacci R, Mingozzi A, Roberti R (2012) Recent exact algorithms for solving the vehicle routing problem under capacity and time window constraints. Eur. J. Oper. Res. 218(1):1–6.Crossref, Google Scholar
• Baldacci R, Bartolini E, Mingozzi A, Roberti R (2010) An exact solution framework for a broad class of vehicle routing problems. Comput. Management Sci. 7(3):229–268.Crossref, Google Scholar
• Bartolini E, Goeke D, Schneider M, Ye M (2021) The robust traveling salesman problem with time windows under knapsack-constrained travel time uncertainty. Transportation Sci. 55(2):371–394.Link, Google Scholar
• Ben-Tal A, Den Hertog D, De Waegenaere A, Melenberg B, Rennen G (2013) Robust solutions of optimization problems affected by uncertain probabilities. Management Sci. 59(2):341–357.Link, Google Scholar
• Bertsimas D, Sim M (2004) The price of robustness. Oper. Res. 52(1):35–53.Link, Google Scholar
• Bertsimas DJ, Jaillet P, Odoni AR (1990) A priori optimization. Oper. Res. 38(6):1019–1033.Link, Google Scholar
• Birge JR, Louveaux F (2011) Introduction to Stochastic Programming (Springer Science & Business Media, Boston).Crossref, Google Scholar
• Bräysy O, Gendreau M (2005a) Vehicle routing problem with time windows, part I: Route construction and local search algorithms. Transportation Sci. 39(1):104–118.Link, Google Scholar
• Bräysy O, Gendreau M (2005b) Vehicle routing problem with time windows, part II: Metaheuristics. Transportation Sci. 39(1):119–139.Link, Google Scholar
• Campbell AM, Thomas BW (2008) Probabilistic traveling salesman problem with deadlines. Transportation Sci. 42(1):1–21.Link, Google Scholar
• Chen Z, Sim M, Xiong P (2020) Robust stochastic optimization made easy with rsome. Management Sci. 66(8):3329–3339.Link, Google Scholar
• Contardo C, Martinelli R (2014) A new exact algorithm for the multi-depot vehicle routing problem under capacity and route length constraints. Discrete Optim. 12:129–146.Crossref, Google Scholar
• Cordeau JF (2006) A branch-and-cut algorithm for the dial-a-ride problem. Oper. Res. 54(3):573–586.Link, Google Scholar
• Cordeau JF, Desaulniers G, Desrosiers J, Solomon MM, Soumis F (2002) VRP with time windows. The Vehicle Routing Problem (Society for Industrial & Applied Mathematics, Philadelphia), 157–193.Crossref, Google Scholar
• Costa L, Contardo C, Desaulniers G (2019) Exact branch-price-and-cut algorithms for vehicle routing. Transportation Sci. 53(4):946–985.Link, Google Scholar
• Dantzig GB, Ramser JH (1959) The truck dispatching problem. Management Sci. 6(1):80–91.Link, Google Scholar
• De Maio A, Laganà D, Musmanno R, Vocaturo F (2021) Arc routing under uncertainty: Introduction and literature review. Comput. Oper. Res. 135:105442.Crossref, Google Scholar
• Desaulniers G (2010) Branch-and-price-and-cut for the split-delivery vehicle routing problem with time windows. Oper. Res. 58(1):179–192.Link, Google Scholar
• Dinh T, Fukasawa R, Luedtke J (2018) Exact algorithms for the chance-constrained vehicle routing problem. Math. Programming 172(1):105–138.Crossref, 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
• 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
• Esfahani PM, Kuhn D (2018) Data-driven distributionally robust optimization using the wasserstein metric: Performance guarantees and tractable reformulations. Math. Programming 171(1):115–166.Crossref, Google Scholar
• Gendreau M, Jabali O, Rei W (2014) Stochastic vehicle routing problems. MOS-SIAM Series on Optimization (Society for Industrial and Applied Mathematics, Philadelphia), 213–239.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
• Ghosal S, Wiesemann W (2020) The distributionally robust chance-constrained vehicle routing problem. Oper. Res. 68(3):716–732.Link, Google Scholar
• Gounaris CE, Wiesemann W, Floudas CA (2013) The robust capacitated vehicle routing problem under demand uncertainty. Oper. Res. 61(3):677–693.Link, Google Scholar
• Han J, Lee C, Park S (2014) A robust scenario approach for the vehicle routing problem with uncertain travel times. Transportation Sci. 48(3):373–390.Link, Google Scholar
• Ho SC, Szeto WY, Kuo YH, Leung JM, Petering M, Tou TW (2018) A survey of dial-a-ride problems: Literature review and recent developments. Transportation Res. Part B Methodological 111:395–421.Crossref, Google Scholar
• Irnich S, Desaulniers G (2005) Shortest path problems with resource constraints. Desaulniers G, Desrosiers J, Solomon MM, eds. Column Generation (Springer, Berlin), 33–65.Crossref, Google Scholar
• Jaillet P, Qi J, Sim M (2016) Routing optimization under uncertainty. Oper. Res. 64(1):186–200.Link, Google Scholar
• Jepsen M, Petersen B, Spoorendonk S, Pisinger D (2008) Subset-row inequalities applied to the vehicle-routing problem with time windows. Oper. Res. 56(2):497–511.Link, Google Scholar
• Kenyon AS, Morton DP (2003) Stochastic vehicle routing with random travel times. Transportation Sci. 37(1):69–82.Link, Google Scholar
• Kohl N, Desrosiers J, Madsen OBG, Solomon MM, Soumis F (1999) 2-path cuts for the vehicle routing problem with time windows. Transportation Sci. 33(1):101–116.Link, Google Scholar
• Laporte G (2009) Fifty years of vehicle routing. Transportation Sci. 43(4):408–416.Link, Google Scholar
• Laporte G, Nobert Y (1983) A branch and bound algorithm for the capacitated vehicle routing problem. Oper. Res. Spektrum 5(2):77–85.Crossref, Google Scholar
• Laporte G, Louveaux F, Mercure H (1992) The vehicle routing problem with stochastic travel times. Transportation Sci. 26(3):161–170.Link, Google Scholar
• 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–1306.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
• Lübbecke ME, Desrosiers J (2005) Selected topics in column generation. Oper. Res. 53:1007–1023.Link, Google Scholar
• Lysgaard J, Letchford AN, Eglese RW (2004) A new branch-and-cut algorithm for the capacitated vehicle routing problem. Math. Programming 100(2):423–445.Crossref, Google Scholar
• Martinelli R, Pecin D, Poggi M (2014) Efficient elementary and restricted non-elementary route pricing. Eur. J. Oper. Res. 239(1):102–111.Crossref, Google Scholar
• Munari P, Moreno A, De La Vega J, Alem D, Gondzio J, Morabito R (2019) The robust vehicle routing problem with time windows: Compact formulation and branch-price-and-cut method. Transportation Sci. 53(4):1043–1066.Link, Google Scholar
• Nemirovski A, Shapiro A (2006) Convex approximations of chance constrained programs. SIAM J. Optim. 17(4):969–996.Crossref, Google Scholar
• Oyola J, Arntzen H, Woodruff DL (2017) The stochastic vehicle routing problem, a literature review, part II: Solution methods. EURO 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. EURO J. Transportation Logist. 7(3):193–221.Crossref, Google Scholar
• Park J, Kim BI (2010) The school bus routing problem: A review. Eur. J. Oper. Res. 202(2):311–319.Crossref, Google Scholar
• Pecin D, Contardo C, Desaulniers G, Uchoa E (2017) New enhancements for the exact solution of the vehicle routing problem with time windows. INFORMS J. Comput. 29(3):489–502.Link, Google Scholar
• Pessoa AA, Poss M, Sadykov R, Vanderbeck F (2021) Branch-cut-and-price for the robust capacitated vehicle routing problem with knapsack uncertainty. Oper. Res. 69(3):739–754.Link, Google Scholar
• Pessoa A, Sadykov R, Uchoa E, Vanderbeck F (2020) A generic exact solver for vehicle routing and related problems. Math. Programming 183(1):483–523.Crossref, Google Scholar
• Poggi M, Uchoa E (2014) New Exact Algorithms for the Capacitated Vehicle Routing Problem (SIAM, Philadelphia).Crossref, Google Scholar
• Righini G, Salani M (2006) Symmetry helps: Bounded bi-directional dynamic programming for the elementary shortest path problem with resource constraints. Discrete Optim. 3(3):255–273.Crossref, Google Scholar
• Ritzinger U, Puchinger J, Hartl RF (2016) A survey on dynamic and stochastic vehicle routing problems. Internat. J. Production Res. 54(1):215–231.Crossref, Google Scholar
• Rockafellar RT, Uryasev S (2002) Conditional value-at-risk for general loss distributions. J. Bank. Finance 26(7):1443–1471.Crossref, Google Scholar
• Rostami B, Desaulniers G, Errico F, Lodi A (2021) Branch-price-and-cut algorithms for the vehicle routing problem with stochastic and correlated travel times. Oper. Res. 69(2):436–455.Link, Google Scholar
• Russell RA, Urban TL (2007) Vehicle routing with soft time windows and erlang travel times. J. Oper. Res. Soc. 59(9):1220–1228.Crossref, Google Scholar
• Ryan DM, Foster BA (1981) An integer programming approach to scheduling. Wren A, ed. Computer Scheduling of Public Transport Urban Passenger Vehicle and Crew Scheduling (North-Holland, Amsterdam), 269–280.Google Scholar
• Sadykov R, Uchoa E, Pessoa A (2021) A bucket graph–based labeling algorithm with application to vehicle routing. Transportation Sci. 55(1):4–28.Link, Google Scholar
• Secomandi N, Margot F (2009) Reoptimization approaches for the vehicle-routing problem with stochastic demands. Oper. Res. 57(1):214–230.Link, 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
• Srinivasan KK, Prakash A, Seshadri R (2014) Finding most reliable paths on networks with correlated and shifted log–normal travel times. Transportation Res. Part B Methodological 66:110–128.Crossref, Google Scholar
• Subramanyam A, Mufalli F, Laínez-Aguirre JM, Pinto JM, Gounaris CE (2021) Robust multiperiod vehicle routing under customer order uncertainty. Oper. Res. 69(1):30–60.Link, Google Scholar
• Sungur I, Ren Y, Ordóñez F, Dessouky M, Zhong H (2010) A model and algorithm for the courier delivery problem with uncertainty. Transportation Sci. 44(2):193–205.Link, 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, Gendreau M, Dellaert N, van Woensel T, de Kok A (2014) 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
• Verweij B, Ahmed S, Kleywegt AJ, Nemhauser G, Shapiro A (2003) The sample average approximation method applied to stochastic routing problems: A computational study. Comput. Optim. Appl. 24(2–3):289–333.Crossref, Google Scholar
• Vidal T (2017) Node, edge, arc routing and turn penalties: Multiple problems-one neighborhood extension. Oper. Res. 65(4):992–1010.Link, Google Scholar
• Vidal T, Laporte G, Matl P (2020) A concise guide to existing and emerging vehicle routing problem variants. Eur. J. Oper. Res. 286(2):401–416.Crossref, Google Scholar
• Vidal T, Crainic TG, Gendreau M, Prins C (2014) A unified solution framework for multi-attribute vehicle routing problems. Eur. J. Oper. Res. 234(3):658–673.Crossref, Google Scholar
• Wang A, Subramanyam A, Gounaris CE (2021) Robust vehicle routing under uncertainty via branch-price-and-cut. Optim. Engrg. 23:1895–1948.Google Scholar
• Wiesemann W, Kuhn D, Sim M (2014) Distributionally robust convex optimization. Oper. Res. 62(6):1358–1376.Link, Google Scholar
• Zhang Y, Baldacci R, Sim M, Tang J (2019a) Routing optimization with time windows under uncertainty. Math. Programming 175(1–2):263–305.Crossref, Google Scholar
• Zhang Y, Zhang Z, Lim A, Sim M (2021) Robust data-driven vehicle routing with time windows. Oper. Res. 69(2):469–485.Link, Google Scholar
• Zhang Z, Luo Z, Qin H, Lim A (2019b) Exact algorithms for the vehicle routing problem with time windows and combinatorial auction. Transportation Sci. 53(2):427–441.Link, Google Scholar
• Zhu S, Fukushima M (2009) Worst-case conditional value-at-risk with application to robust portfolio management. Oper. Res. 57(5):1155–1168.Link, Google Scholar