The Distributionally Robust Chance-Constrained Vehicle Routing Problem

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
• 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
• Bandi C, Bertsimas D (2012) Tractable stochastic analysis in high dimensions via robust optimization. Math. Programming 134(1):23–70.Crossref, 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
• Beck A, Teboulle M (2012) Smoothing and first order methods: A unified framework. SIAM J. Optim. 22(2):557–580.Crossref, Google Scholar
• Ben-Tal A, Nemirovski A (2001) Lectures on Modern Convex Optimization: Analysis, Algorithms, and Engineering Applications (SIAM, Philadelphia).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. Oper. Res. 59(2):341–357.Google Scholar
• Bertsimas D, Sim M (2004) The price of robustness. Oper. Res. 52(1):35–53.Link, Google Scholar
• Bertsimas D, Simchi-Levi D (1996) A new generation of vehicle routing research: Robust algorithms, addressing uncertainty. Oper. Res. 44(2):286–304.Link, Google Scholar
• Bertsimas D, Gupta V, Kallus N (2018) Data-driven robust optimization. Math. Programming 167(2):235–292.Crossref, Google Scholar
• Boyd S, Vandenberghe L (2004) Convex Optimization (Cambridge University Press, Cambridge, UK).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 (2017) Wasserstein distance and the distributionally robust TSP. Oper. Res. 66(6):1457–1759.Google Scholar
• Casella G, Berger RL (2002) Statistical Inference, 2nd ed. (Duxbury Thomson Learning, Pacific Grove, CA).Google Scholar
• Chernick MR (2007) Bootstrap Methods: A Guide for Practitioners and Researchers, 2nd ed. (John Wiley & Sons, Hoboken, NJ).Crossref, Google Scholar
• Cordeau JF, Laporte G, Savelsbergh MWP, Vigo D (2006) Vehicle routing. Barnhart C, Laporte G, eds. Transportation, Handbooks in Operations Research and Management Science, vol. 14 (Elsevier, Amsterdam), 367–428.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):595–612.Link, Google Scholar
• Dhaene J, Denuit M, Goovaerts MJ, Kaas R, Vyncke D (2002) The concept of comonotonicity in actuarial science and finance: Theory. Insurance Math. Econom. 31(1):3–33.Crossref, Google Scholar
• Díaz BD (2006) The VRP web. Accessed September 1, 2019, http://www.bernabe.dorronsoro.es/vrp/.Google Scholar
• Dinh T, Fukasawa R, Luedtke J (2017) Exact algorithms for the chance-constrained vehicle routing problem. Math. Programming 172(1–2):105–138.Crossref, Google Scholar
• Dror M, Trudeau P (1986) Stochastic vehicle routing with modified savings algorithm. Eur. J. Oper. Res. 23(2):228–235.Crossref, Google Scholar
• Dror M, Laporte G, Louveaux FV (1993) Vehicle routing with stochastic demands and restricted failures. Methods Models Oper. Res. 37(3):273–283.Crossref, Google Scholar
• Dyer M, Stougie L (2006) Computational complexity of stochastic programming problems. Math. Programming 106(3):423–432.Crossref, Google Scholar
• El Ghaoui L, Oks M, Oustry F (2003) Worst-case value-at-risk and robust portfolio optimization: A conic programming approach. Oper. Res. 51(4):543–556.Link, 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–2):115–166.Crossref, Google Scholar
• Flajolet A, Blandin S, Jaillet P (2018) Robust adaptive routing under uncertainty. Oper. Res. 66(1):210–229.Link, Google Scholar
• Fukasawa R, Longo H, Lysgaard J, Poggi de Aragão M, Reis M, Uchoa E, Werneck RF (2006) Robust branch-and-cut-and-price for the capacitated vehicle routing problem. Math. Programming 106(3):491–511.Crossref, Google Scholar
• Gendreau M, Laporte G, Séguin R (1996) Stochastic vehicle routing. Eur. J. Oper. Res. 88(1):3–12.Crossref, Google Scholar
• Golden B, Yee J (1979) A framework for probabilistic vehicle routing. AIIE Trans. 11(2):109–112.Crossref, Google Scholar
• Golden BL, Raghavan S, Wasil EA, eds. (2008) The Vehicle Routing Problem: Latest Advances and New Challenges (Springer, New York).Crossref, Google Scholar
• Goldfarb D, Iyengar G (2003) Robust portfolio selection problems. Math. Oper. Res. 28(1):1–38.Link, Google Scholar
• Gounaris C, Wiesemann W, Floudas C (2013) The robust capacitated vehicle routing problem under demand uncertainty. Oper. Res. 61(3):677–693.Link, Google Scholar
• Hanasusanto GA, Kuhn D, Wiesemann W (2016) A comment on “Computational complexity of stochastic programming problems”. Math. Programming 159(1):557–569.Crossref, Google Scholar
• Hanasusanto GA, Roitch V, Kuhn D, Wiesemann W (2015) A distributionally robust perspective on uncertainty quantification and chance constrained programming. Math. Programming 151(1):35–62.Crossref, Google Scholar
• Hanasusanto G, Roitch V, Kuhn D, Wiesemann W (2017) Ambiguous joint chance constraints under mean and dispersion information. Oper. Res. 65(3):751–767.Link, Google Scholar
• Hu Z, Hong LJ (2013) Kullback-Leibler divergence constrained distributionally robust optimization. Accessed September 1, 2019, http://www.optimization-online.org/DB_HTML/2012/11/3677.html.Google Scholar
• Jaillet P, Qi J, Sim M (2016) Routing optimization under uncertainty. Oper. Res. 64(1):186–200.Link, Google Scholar
• Jiang R, Guan Y (2015) Risk-averse two-stage stochastic program with distributional ambiguity. Oper. Res. 66(5):1189–1456.Google Scholar
• Laporte G (2009) Fifty years of vehicle routing. Transportation Sci. 43(4):408–416.Link, 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
• Laporte G, Norbert Y, Desrochers M (1985) Optimal routing under capacity and distance restrictions. Oper. Res. 33(5):1050–1073.Link, Google Scholar
• Li Q, So AMC, Ma WK (2014) Distributionally robust chance-constrained transmit beamforming for multiuser MISO downlink. Proc. 2014 IEEE Internat. Conf. Acoustics Speech Signal Processing (ICASSP) (IEEE, Piscataway, NJ), 3479–3483.Google Scholar
• Luedtke J, Ahmed S (2008) A sample average approximation approach for optimization with probabilistic constraints. SIAM J. Optim. 19(2):674–699.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
• Meng F, Qi J, Zhang M, Ang J, Chu S, Sim M (2015) A robust optimization model for managing elective admission in a public hospital. Oper. Res. 63(6):1452–1467.Link, Google Scholar
• Nemirovski A (2012) On safe tractable approximations of chance constraints. Eur. J. Oper. Res. 219(3):707–718.Crossref, Google Scholar
• O’Donoghue B, Candès E (2015) Adaptive restart for accelerated gradient schemes. Foundations Comput. Math. 15(3):715–732.Crossref, Google Scholar
• Pecin D, Pessoa A, Poggi M, Uchoa E (2017) Improved branch-cut-and-price for capacitated vehicle routing. Math. Programming Comput. 9(1):61–100.Crossref, Google Scholar
• Pessoa AA, Poss M (2015) Robust network design with uncertain outsourcing cost. INFORMS J. Comput. 27(3):507–524.Link, Google Scholar
• Pflug GC (2000) Some remarks on the value-at-risk and the conditional value-at-risk. Uryasev SP, ed. Probabilistic Constrained Optimization (Springer, Boston), 272–281.Crossref, Google Scholar
• Pham-Gia T, Hung T (2001) The mean and median absolute deviations. Math. Comput. Model. 34(7–8):921–936.Crossref, Google Scholar
• Postek K, Ben-Tal A, den Hertog D, Melenberg B (2018) Robust optimization with ambiguous stochastic constraints under mean and dispersion information. Oper. Res. 66(3):814–833.Link, Google Scholar
• Rockafellar RT (1970) Convex Analysis (Princeton University Press, Princeton, NJ).Crossref, Google Scholar
• Rockafellar RT, Wets RJB (1997) Variational Analysis (Springer, Berlin).Google Scholar
• Segers J (2014) On the asymptotic distribution of the mean absolute deviation about the mean. Working paper, Université Catholique de Louvain, Ottignies-Louvain-la-Neuve, Belgium.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. (SIAM, Philadelphia), 37–57.Crossref, Google Scholar
• Shapiro A (2001) On duality theory of conic linear problems. Goberna MA, López MA, eds. Semi-Infinite Programming (Springer, Boston), 135–165.Crossref, Google Scholar
• Shapiro A, Dentcheva D, Ruszczyński A (2014) Lectures on Stochastic Programming: Modeling and Theory, 2nd ed. (SIAM, Philadelphia).Crossref, Google Scholar
• Stewart WR, Golden BL (1983) Stochastic vehicle routing: A comprehensive approach. Eur. J. Oper. Res. 14(4):371–385.Crossref, Google Scholar
• Sungur I, Ordonez 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) Vehicle Routing: Problems, Methods, and Applications, 2nd ed. (SIAM, Philadelphia).Crossref, Google Scholar
• Wiesemann W, Kuhn D, Sim M (2014) Distributionally robust convex optimization. Oper. Res. 62(6):1358–1376.Link, Google Scholar
• Xie W, Ahmed S (2018) On deterministic reformulations of distributionally robust joint chance constrained optimization problems. SIAM. J. Optim. 28(2):1151–1182.Crossref, Google Scholar
• Yang WH, Mathur K, Ballou R (2000) Stochastic vehicle routing problem with restocking. Transportation Sci. 34(1):99–112.Link, Google Scholar
• Zhang Y, Baldacci R, Sim M, Tang J (2018) Routing optimization with time windows under uncertainty. Math. Programming 175(1–2):263–305.Google Scholar
• Zhao C, Guan Y (2018) Data-driven risk-averse stochastic optimization with Wasserstein metric. Oper. Res. Lett. 46(2):262–267.Crossref, Google Scholar
• Zhao C, Jiang R (2018) Distributionally robust contingency-constrained unit commitment. IEEE Trans. Power Systems 33(1):94–102.Crossref, Google Scholar
• Zymler S, Kuhn D, Rustem B (2013) Distributionally robust joint chance constraints with second-order moment information. Math. Programming 137(1–2):167–198.Crossref, Google Scholar