Exact Two-Step Benders Decomposition for the Time Window Assignment Traveling Salesperson Problem

References

• Benders J (1962) Partitioning procedures for solving mixed-variables programming problems. Numerische Mathematik 4(1):238–252.Crossref, Google Scholar
• Birge JR, Louveaux FV (1988) A multicut algorithm for two-stage stochastic linear programs. Eur. J. Oper. Res. 34(3):384–392.Crossref, Google Scholar
• Chen R, Luedtke J (2022) On generating Lagrangian cuts for two-stage stochastic integer programs. INFORMS J. Comput. 34(4):2332–2349.Link, Google Scholar
• Crainic TG, Hewitt M, Maggioni F, Rei W (2021) Partial Benders decomposition: General methodology and application to stochastic network design. Transportation Sci. 55(2):414–435.Link, Google Scholar
• Dantzig GB (1955) Linear programming under uncertainty. Management Sci. 1(3–4):197–206.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
• Gendreau M, Hertz A, Laporte G, Stan M (1998) A generalized insertion heuristic for the traveling salesman problem with time windows. Oper. Res. 46(3):330–335.Link, Google Scholar
• Henrion R, Römisch W (2022) Problem-based optimal scenario generation and reduction in stochastic programming. Math. Programming 191:183–205.Crossref, Google Scholar
• Henrion R, Küchler C, Römisch W (2009) Scenario reduction in stochastic programming with respect to discrepancy distances. Comput. Optim. Appl. 43(1):67–93.Crossref, Google Scholar
• Jabali O, Leus R, Van Woensel T, De Kok T (2015) Self-imposed time windows in vehicle routing problems. OR Spectrum 37(2):331–352.Crossref, Google Scholar
• Keutchayan J, Munger D, Gendreau M (2020) On the scenario-tree optimal-value error for stochastic programming problems. Math. Oper. Res. 45(4):1572–1595.Link, Google Scholar
• Keutchayan J, Ortmann J, Rei W (2023) Problem-driven scenario clustering in stochastic optimization. Comput. Management Sci. 20(1):13.Crossref, Google Scholar
• Kleywegt AJ, Shapiro A, Homem-de Mello T (2002) The sample average approximation method for stochastic discrete optimization. SIAM J. Optim. 12(2):479–502.Crossref, Google Scholar
• Paradiso R, Roberti R, Laganá D, Dullaert W (2020) An exact solution framework for multitrip vehicle-routing problems with time windows. Oper. Res. 68(1):180–198.Link, Google Scholar
• Pflug GC, Pichler A (2015) Dynamic generation of scenario trees. Comput. Optim. Appl. 62(3):641–668.Crossref, Google Scholar
• Potvin JY, Bengio S (1996) The vehicle routing problem with time windows part II: Genetic search. INFORMS J. Comput. 8(2):165–172.Link, Google Scholar
• Rahmaniani R, Crainic TG, Gendreau M, Rei W (2017) The Benders decomposition algorithm: A literature review. Eur. J. Oper. Res. 259(3):801–817.Crossref, Google Scholar
• Rahmaniani R, Ahmed S, Crainic TG, Gendreau M, Rei W (2020) The Benders dual decomposition method. Oper. Res. 68(3):878–895.Link, Google Scholar
• Spliet R, Gabor AF (2015) The time window assignment vehicle routing problem. Transportation Sci. 49(4):721–731.Link, Google Scholar
• Spliet R, Dabia S, Van Woensel T (2018) The time window assignment vehicle routing problem with time-dependent travel times. Transportation Sci. 52(2):261–276.Link, Google Scholar
• Van Slyke RM, Wets R (1969) L-shaped linear programs with applications to optimal control and stochastic programming. SIAM J. Appl. Math. 17(4):638–663.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
• Wölck M, Meisel S (2022) Branch-and-price approaches for real-time vehicle routing with picking, loading, and soft time windows. INFORMS J. Comput. 34(4):2192–2211.Link, Google Scholar