Hardness of Pricing Routes for Two-Stage Stochastic Vehicle Routing Problems with Scenarios

References

• 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
• Birge JR, Louveaux F (2011) Introduction to Stochastic Programming (Springer Science & Business Media, New York).Crossref, Google Scholar
• Chen R, Luedtke J (2022) On sample average approximation for two-stage stochastic programs without relatively complete recourse. Math. Program. 196(1–2):719–754.Crossref, Google Scholar
• 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–781.Crossref, Google Scholar
• Cranston DW, West DB (2017) An introduction to the discharging method via graph coloring. Discrete Math. 340(4):766–793.Crossref, Google Scholar
• Cygan M, Fomin FV, Kowalik Ł, Lokshtanov D, Marx D, Pilipczuk M, Pilipczuk M, Saurabh S (2015) Parameterized Algorithms, vol. 4 (Springer, Cham, Switzerland).Crossref, Google Scholar
• Dinh T, Fukasawa R, Luedtke J (2018) Exact algorithms for the chance-constrained vehicle routing problem. Math. Prog. 172(1):105–138.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
• Florio AM, Hartl RF, Minner S (2020) New exact algorithm for the vehicle routing problem with stochastic demands. Transportation Sci. 54(4):1073–1090.Link, Google Scholar
• Florio AM, Gendreau M, Hartl RF, Minner S, Vidal T (2022) Recent advances in vehicle routing with stochastic demands: Bayesian learning for correlated demands and elementary branch-price-and-cut. Eur. J. Oper. Res. 306(3):1081–1093.Crossref, Google Scholar
• Fukasawa R, Gunter J (2023) The complexity of branch-and-price algorithms for the capacitated vehicle routing problem with stochastic demands. Oper. Res. Lett. 51(1):11–16.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
• Ghosal S, Wiesemann W (2020) The distributionally robust chance-constrained vehicle routing problem. Oper. Res. 68(3):716–732.Link, Google Scholar
• Hoogendoorn Y, Spliet R (2023) An improved integer L-shaped method for the vehicle routing problem with stochastic demands. INFORMS J. Comput. 35(2):423–439.Link, Google Scholar
• Impagliazzo R, Paturi R, Zane F (2001) Which problems have strongly exponential complexity? J. Comput. System Sci. 63(4):512–530.Crossref, Google Scholar
• Irnich S, Desaulniers G (2005) Shortest path problems with resource constraints. Desaulniers G, Desrosiers J, Solomon MM, eds. Column Generation (Springer, Boston).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
• 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
• 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 FV, van Hamme L (2002) An integer L-shaped algorithm for the capacitated vehicle routing problem with stochastic demands. Oper. Res. 50(3):415–423.Link, Google Scholar
• Ledvina K, Qin H, Simchi-Levi D, Wei Y (2022) A new approach for vehicle routing with stochastic demand: Combining route assignment with process flexibility. Oper. Res. 70(5):2655–2673.Link, Google Scholar
• Luedtke J, Ahmed S (2008) A sample approximation approach for optimization with probabilistic constraints. SIAM J. Optim. 19(2):674–699.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
• Pessoa A, Sadykov R, Uchoa E, Vanderbeck F (2020) A generic exact solver for vehicle routing and related problems. Math. Program. 183:483–523.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, 2nd ed. (SIAM, Philadelphia), 59–86.Crossref, Google Scholar
• Salavati-Khoshghalb M, Gendreau M, Jabali O, Rei W (2019a) A hybrid recourse policy for the vehicle routing problem with stochastic demands. Eur. J. Transportation Logist. 8(3):269–298.Crossref, Google Scholar
• Salavati-Khoshghalb M, Gendreau M, Jabali O, Rei W (2019b) A rule-based recourse for the vehicle routing problem with stochastic demands. Transportation Sci. 53(5):1334–1353.Link, Google Scholar
• Spliet R (2023) Technical note—The complexity of the pricing problem of the set partitioning formulation of vehicle routing problems. Oper. Res. 71(5):1454–1457.Link, Google Scholar
• Swamy C, Shmoys DB (2012) Sampling-based approximation algorithms for multistage stochastic optimization. SIAM J. Comput. 41(4):975–1004.Crossref, Google Scholar
• Tillman FA (1969) The multiple terminal delivery problem with probabilistic demands. Transportation Sci. 3(3):192–204.Link, Google Scholar
• Toth P, Vigo D, eds. (2014) Vehicle Routing: Problems, Methods, and Applications (SIAM, Philadelphia).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:289–333.Crossref, 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