A Unifying Framework for the Capacitated Vehicle Routing Problem Under Risk and Ambiguity

References

• Adulyasak Y, Jaillet P (2015) Models and algorithms for stochastic and robust vehicle routing with deadlines. Transportation Sci. 50(2):608–626.Link, Google Scholar
• Agra A, Christiansen M, Hvattum LM, Rodrigues F (2013a) Robust optimization for a maritime inventory routing problem. Transportation Sci. 52(3):509–525.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. Ridha Mahjoub A, Markakis V, Milis I, Paschos VT, eds. Combin. Optim. Second Internat. Sympos. (Springer, Berlin, Heidelberg), 249–260.Google Scholar
• Agra A, Christiansen M, Figueiredo R, Hvattum LM, Poss M, Requejo C (2013b) The robust vehicle routing problem with time windows. Comput. Oper. Res. 40(3):856–866.Crossref, Google Scholar
• Augerat P, Belenguer JM, Benavent E, Corberán A, Naddef D (1998) Separating capacity constraints in the CVRP using tabu search. Eur. J. Oper. Res. 106(2–3):546–557.Crossref, Google Scholar
• Bayraksan G, Love DK (2015) Data-driven stochastic programming using phi-divergences. INFORMS TutORials in Operations Research, 1–19.Google Scholar
• Beck A, Teboulle M (2009) A fast iterative shrinkage-thresholding algorithm for linear inverse problems. SIAM J. Imaging Sci. 2(1):183–202.Crossref, Google Scholar
• Bellini F, Bignozzi V (2015) On elicitable risk measures. Quant. Finance 15(5):725–733.Crossref, Google Scholar
• Ben-Tal A, El Ghaoui L, Nemirovski A (2009) Robust Optimization (Princeton University Press, Princeton, NJ).Crossref, 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 D, Brown DB, Caramanis C (2011) Theory and applications of robust optimization. SIAM Rev. 53(3):464–501.Crossref, Google Scholar
• Bertsimas D, Shtern S, Sturt B (2023) A data-driven approach to multi-stage stochastic linear optimization. Management Sci. 69(1):51–74.Link, Google Scholar
• Birge JR, Louveaux F (2011) Introduction to Stochastic Programming, 2nd ed. (Springer, New York).Crossref, Google Scholar
• Boyd S, Vandenberghe L (2004) Convex Optimization (Cambridge University Press, Cambridge, UK).Crossref, Google Scholar
• Carlsson JG, Behroozi M (2017) Worst-case demand distributions in vehicle routing. Eur. J. Oper. Res. 256(2):462–472.Crossref, Google Scholar
• Carlsson JG, Delage E (2013) Robust partitioning for stochastic multivehicle routing. Oper. Res. 61(3):546–557.Link, Google Scholar
• Carlsson JG, Behroozi M, Mihic K (2018) Wasserstein distance and the distributionally robust TSP. Oper. Res. 66(6):1603–1624.Link, Google Scholar
• Chen Z, Sim M, Xu H (2019) Distributionally robust optimization with infinitely constrained ambiguity sets. Oper. Res. 67(5):1328–1344.Link, Google Scholar
• Christofides N (1976) The vehicle routing problem. RAIRO 10(1):55–70.Google Scholar
• Cornuejols G, Harche F (1993) Polyhedral study of the capacitated vehicle routing problem. Math. Programming 60(1):21–52.Crossref, Google Scholar
• Cui Z, Long DZ, Qi J, Zhang L (2022) The inventory routing problem under uncertainty. Oper. Res 71(1):378–395.Link, Google Scholar
• Dantzig GB, Ramser JH (1959) The truck dispatching problem. Management Sci. 6(1):80–91.Link, Google Scholar
• Delage E, Ye Y (2010) Distributionally robust optimization under moment uncertainty with application to data-driven problems. Oper. Res. 58(3):596–612.Link, Google Scholar
• Di Puglia Pugliese L, Guerriero F, Poss M (2019) The resource constrained shortest path problem with uncertain data: A robust formulation and optimal solution approach. Comput. Oper. Res. 107:140–155.Crossref, Google Scholar
• Díaz BD (2006) The VRP web. Accessed October 1, 2021, http://www.bernabe.dorronsoro.es/vrp/.Google Scholar
• Dinh T, Fukasawa R, Luedtke J (2018) Exact algorithms for the chance-constrained vehicle routing problem. Math. Programming 172(1–2):105–138.Crossref, Google Scholar
• Erdoğan E, Iyengar G (2006) Ambiguous chance constrained problems and robust optimization. Math. Programming 107(1–2):37–61.Crossref, Google Scholar
• Eufinger L, Kurtz J, Buchheim C, Clausen U (2020) A robust approach to the capacitated vehicle routing problem with uncertain costs. INFORMS J. Optim. 2(2):79–95.Link, Google Scholar
• Gendreau M, Jabali O, Rei W (2014) Stochastic vehicle routing problems. Toth P, Vigo D, eds. Vehicle Routing: Problems, Methods, and Applications, 2nd ed. (MOS-SIAM, Philadelphia), 213–239.Crossref, Google Scholar
• Gendreau M, Jabali O, Rei W (2016) 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
• Hall NG, Long DZ, Qi J, Sim M (2015) Managing underperformance risk in project portfolio selection. Oper. Res. 63(3):660–675.Link, Google Scholar
• Hoogeboom M, Adulyasak Y, Dullaert W, Jaillet P (2021) The robust vehicle routing problem with time window assignments. Transportation Sci. 55(2):395–413.Link, Google Scholar
• Irnich S, Toth P, Vigo D (2014) The family of vehicle routing problems. Toth P, Vigo D, eds. Vehicle Routing: Problems, Methods, and Applications, 2nd ed. (MOS-SIAM, Philadelphia), 1–33.Crossref, Google Scholar
• Iyengar G (2005) Robust dynamic programming. Math. Oper. Res. 30(2):257–280.Link, Google Scholar
• Jaillet P, Qi J, Sim M (2016) Routing optimization under uncertainty. Oper. Res. 64(1):186–200.Link, Google Scholar
• Kuhn D, Mohajerin Esfahani P, Nguyen VA, Shafieezadeh-Abadeh S (2019) Wasserstein distributionally robust optimization: Theory and applications in machine learning. INFORMS TutORials in Operations Research, 130–166.Google Scholar
• Laporte G, Norbert 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 (1989) The vehicle routing problem with stochastic travel times. Eur. J. Oper. Res. 39(1):71–78.Crossref, 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
• Long DZ, Qi J, Zhang A (2023) Supermodularity in two-stage distributionally robust optimization. Management Sci., ePub ahead of print April 3, https://doi.org/10.1287/mnsc.2023.4748.Link, Google Scholar
• Lu D, Gzarao F (2019) The robust vehicle routing problem with time windows: Solution by branch and price and cut. Eur. J. Oper. Res. 275(3):925–938.Crossref, 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
• Mohajerin Esfahani P, Kuhn D (2018) Data-driven distributionally robust optimization using the Wasserstein metric: Performance guarantees and tractable reformulations. Math. Programming 171(1–2):115–166.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
• Nilim A, El Ghaoui L (2005) Robust control of Markov decision processes with uncertain transition matrices. Oper. Res. 53(5):780–798.Link, Google Scholar
• Ordóñez F. (2010) Robust vehicle routing. INFORMS TutORials in Operations Research, 153–178.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
• Pessoa AA, Di Puglia Pugliese L, Guerriero F, Poss M (2015) Robust constrained shortest path problems under budgeted uncertainty. Networks 66(2):98–111.Crossref, 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
• Rockafeller RT, Uryasev S (2002) Conditional value-at-risk for general loss distributions. J. Banking Finance 26(7):1443–1471.Crossref, Google Scholar
• Semet F, Toth P, Vigo D (2014) Classical exact algorithms for the capacitated vehicle routing problem. Toth P, Vigo D, eds. Vehicle Routing: Problems, Methods, and Applications, 2nd ed. (MOS-SIAM, Philadelphia), 37–57.Crossref, Google Scholar
• Shapiro A, Dentcheva D, Ruszczyński A (2014) Lectures on Stochastic Programming: Modeling and Theory, 2nd ed. (SIAM).Crossref, Google Scholar
• Subramanyam A, Repoussis PP, Gounaris CE (2020) Robust optimization of a broad class of heterogeneous vehicle routing problems under demand uncertainty. INFORMS J. Comput. 32(3):661–681.Link, 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, Ordóñez F (2008) A robust optimization approach for the capacitated vehicle routing problem with demand uncertainty. IIE Trans. 40(5):509–523.Crossref, Google Scholar
• Toth P, Vigo D, eds. (2014) The Vehicle Routing Problem, 2nd ed. (SIAM, Philadelphia).Crossref, Google Scholar
• Wang A, Subramanyam A, Gounaris CE (2022) Robust vehicle routing under uncertainty via branch-price-and-cut. Optim. Engrg. 23(4):1895–1948.Crossref, Google Scholar
• Wiesemann W, Kuhn D, Rustem B (2013) Robust Markov decision processes. Math. Oper. Res. 38(1):153–183.Link, 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 (2019) Routing optimization with time windows under uncertainty. Math. Programming 175(1):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
• 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