Branch and Price for the Stochastic Traveling Salesman Problem with Generalized Latency

References

• Atamtürk A (2001) Flow pack facets of the single node fixed-charge flow polytope. Oper. Res. Lett. 29(3):107–114.Crossref, Google Scholar
• Atamtürk A (2002) On capacitated network design cut–set polyhedra. Math. Programming 92:425–437.Crossref, Google Scholar
• Birge JR (1982) The value of the stochastic solution in stochastic linear programs with fixed recourse. Math. Programming 24(1):314–325.Crossref, Google Scholar
• Birge J, Louveaux F (2011) Introduction to Stochastic Programming (Springer, Cham, Switzerland).Crossref, Google Scholar
• Chouman M, Crainic TG, Gendron B (2017) Commodity representations and cut-set-based inequalities for multicommodity capacitated fixed-charge network design. Transportation Sci. 51(2):650–667.Link, Google Scholar
• Costa A (2005) A survey on Benders decomposition applied to fixed-charge network design problems. Comput. Oper. Res. 32(6):1429–1450.Crossref, Google Scholar
• Costa A, Cordeau JF, Gendron B (2009) Benders, metric and cutset inequalities for multicommodity capacitated network design. Comput. Optim. Appl. 42(3):371–392.Crossref, Google Scholar
• Costa A, Cordeau JF, Gendron B, Laporte G (2012) Accelerating Benders decomposition with heuristicmaster problem solutions. Pesquisa Operacional 32(1):3–20.Crossref, Google Scholar
• Crainic TG (2019) Parallel metaheuristics and cooperative search. Gendreau M, Potvin JY, eds. Handbook of Metaheuristics (Springer, Cham, Switzerland), 419–451.Crossref, Google Scholar
• Crainic TG, Gendreau M (2007) A scatter search heuristic for the fixed-charge multicommodity flow network design problem. Doerner KF, Gendreau M, Greistorfer P, Gutjahr W, Hartl RF, Reimann M, eds. Metaheuristics, Operations Research/Computer Science Interfaces Series, vol. 39 (Springer, Boston), 25–40.Crossref, Google Scholar
• Crainic TG, Frangioni A, Gendron B (2001) Bundle-based relaxation methods for multicommodity capacitated fixed charge network design. Discrete Appl. Math. 112(1–3):73–99.Crossref, Google Scholar
• Crainic TG, Gendreau M, Farvolden JM (2000) A simplex-based tabu search method for capacitated network design. INFORMS J. Comput. 12(3):223–236.Link, Google Scholar
• Crainic TG, Gendreau M, Gendron B (2021) Fixed-charge network design problems. Crainic TG, Gendreau M, Gendron B, eds. Network Design with Applications to Transportation and Logistics (Springer, Cham, Switzerland), 15–28.Crossref, Google Scholar
• Crainic TG, Errico F, Malucelli F, Nonato M (2012) Designing the master schedule for demand-adaptive transit systems. Ann. Oper. Res. 194(1):151–166.Crossref, Google Scholar
• d’Antonio G, Frangioni A (2009) Convergence analysis of deflected conditional approximate subgradient methods. SIAM J. Optim. 20(1):357–386.Crossref, Google Scholar
• Delahaye D, Chaimatanan S, Mongeau M (2019) Simulated annealing: From basics to applications. Gendreau M, Potvin JY, eds. Handbook of Metaheuristics (Springer, Cham, Switzerland), 1–35.Crossref, Google Scholar
• Errico F (2008) The design of flexible transit systems: Models and solution methods. PhD thesis, Polytechnic University of Milan, Milan.Google Scholar
• Errico F, Crainic TG, Malucelli F, Nonato M (2013) A survey on planning semi-flexible transit systems: Methodological issues and a unifying framework. Transportation Res. Part C Emerging Tech. 36:324–338.Crossref, Google Scholar
• Errico F, Crainic TG, Malucelli F, Nonato M (2017) A Benders decomposition approach for the symmetric TSP with generalized latency arising in the design of semiflexible transit systems. Transportation Sci. 51(2):706–722.Link, Google Scholar
• Errico F, Crainic T, Malucelli F, Nonato M (2021) The single-line design problem for demand-adaptive transit systems: A modeling framework and decomposition approach for the stationary-demand case. Transportation Sci. 55(6):1300–1321.Link, Google Scholar
• Fischetti M, Lodi A (2003) Local branching. Math. Programming 98(1):23–47.Crossref, Google Scholar
• Frangioni A, Gorgone E (2014) Bundle methods for sum-functions with “easy” components: Applications to multicommodity network design. Math. Programming 145(1):133–161.Crossref, Google Scholar
• Frangioni A, Gendron B, Gorgone E (2017) On the computational efficiency of subgradient methods: A case study with Lagrangian bounds. Math. Programming Comput. 9(4):573–604.Crossref, Google Scholar
• Gendreau M, Potvin JY (2019) Tabu search. Gendreau M, Potvin JY, eds. Handbook of Metaheuristics (Springer, Cham, Switzerland), 37–55.Crossref, Google Scholar
• Gendron B (2011) Decomposition methods for network design. Procedia Soc. Behav. Sci. 20:31–37.Crossref, Google Scholar
• Gendron B (2019) Revisiting Lagrangian relaxation for network design. Discrete Appl. Math. 261:203–218.Crossref, Google Scholar
• Gendron B, Crainic TG, Frangioni A (1999) Multicommodity capacitated network design. Sansò B, Soriano P, eds. Telecommunications Network Planning (Springer, Boston), 1–19.Crossref, Google Scholar
• Ghamlouche I, Crainic TG, Gendreau M (2003) Cycle-based neighbourhoods for fixed-charge capacitated multicommodity network design. Oper. Res. 51(4):655–667.Link, Google Scholar
• Ghamlouche I, Crainic TG, Gendreau M (2004) Path relinking, cycle-based neighbourhoods and capacitated multicommodity network design. Ann. Oper. Res. 131(1):109–133.Crossref, Google Scholar
• Gkiotsalitis K, Alesiani F (2019) Robust timetable optimization for bus lines subject to resource and regulatory constraints. Transportation Res. Part E Logist. Transportation Rev. 128:30–51.Crossref, Google Scholar
• Hewitt M, Nemhauser GL, Savelsbergh M (2010) Combining exact and heuristic approaches for the capacitated fixed-charge network flow problem. INFORMS J. Comput. 22(2):314–325.Link, Google Scholar
• Higle JL, Wallace SW (2003) Sensitivity analysis and uncertainty in linear programming. Interfaces 33(4):53–60.Link, Google Scholar
• Ibarra-Rojas O, Delgado F, Giesen R, Muñoz J (2015) Planning, operation, and control of bus transport systems: A literature review. Transportation Res. Part B Methodological 77:38–75.Crossref, Google Scholar
• Ioachim I, Desrosiers J, Dumas Y, Solomon M, Villeneuve D (1995) A request clustering algorithm for door-to-door handicapped transportation. Transportation Sci. 29(1):63–78.Link, Google Scholar
• Kall P, Wallace S (1994) Stochastic Programming (Wiley, Chichester, UK).Google Scholar
• Katayama N, Yurimoto S (2011) Combining capacity scaling and local branch approaches for the logistics network design problem. Krause T, Spath D, Ilg R, eds. Proc. 21st Internat. Conf. Production Res. ICPR 2011 (Fraunhofer Verlag, Stuttgart, Deutschland), 772–777.Google Scholar
• Li S, Liu L, Yang L, Gao Z (2019) Robust dynamic bus controls considering delay disturbances and passenger demand uncertainty. Transportation Res. Part B Methodological 123:88–109.Crossref, Google Scholar
• Lotfi MM, Tavakkoli-Moghaddam R (2013) A genetic algorithm using priority-based encoding with new operators for fixed charge transportation problems. Appl. Soft Comput. 13(5):2711–2726.Crossref, Google Scholar
• Lourenço HR, Martin OC, Stützle T (2019) Iterated local search: Framework and applications. Gendreau M, Potvin JY, eds. Handbook of Metaheuristics (Springer, Cham, Switzerland), 129–168.Crossref, Google Scholar
• Ma Q, Li S, Zhang H, Yuan Y, Yang L (2021) Robust optimal predictive control for real-time bus regulation strategy with passenger demand uncertainties in urban rapid transit. Transportation Res. Part C Emerging Tech. 127:103086.Crossref, Google Scholar
• Maggioni F, Wallace SW (2012) Analyzing the quality of the expected value solution in stochastic programming. Ann. Oper. Res. 200(1):37–54.Crossref, Google Scholar
• Malucelli F, Nonato M, Pallottino S (1999) Demand adaptive systems: Some proposals on flexible transit. Ciriani TA, Gliozzi S, Johnson EL, Tadei R, eds. Operational Research in Industry (Palgrave Macmillan, London), 157–182.Crossref, Google Scholar
• Padberg MW, Van Roy TJ, Wolsey LA (1985) Valid linear inequalities for fixed charge problems. Oper. Res. 33(4):842–861.Link, Google Scholar
• Quadrifoglio L, Dessouky M, Palmer K (2007) An insertion heuristic for scheduling mobility allowance shuttle transit (mast) services. J. Scheduling 10(1):25–40.Crossref, Google Scholar
• Rodríguez-Martín I, Salazar-González JJ (2010) A local branching heuristic for the capacitated fixed-charge network design problem. Comput. Oper. Res. 37(3):575–581.Crossref, Google Scholar
• Sun M, Aronson JE, McKeown PG, Drinka D (1998) A tabu search heuristic procedure for the fixed charge transportation problem. Eur. J. Oper. Res. 106(2–3):441–456.Crossref, Google Scholar
• Thapalia BK, Crainic TG, Kaut M, Wallace SW (2011) Single-commodity network design with stochastic demand and multiple sources and sinks. INFOR Inform. Systems Oper. Res. 49(3):193–211.Crossref, Google Scholar
• Tian Q, Lin YH, Wang D (2021) Autonomous and conventional bus fleet optimization for fixed-route operations considering demand uncertainty. Transportation 48(5):2735–2763.Crossref, Google Scholar
• Toth P, Vigo D (1996) Fast local search algorithms for the handicapped persons transportation problem. Osman IH, Kelly JP, eds. Meta-Heuristics (Springer, Boston), 677–690.Crossref, Google Scholar
• Walker WE (1976) A heuristic adjacent extreme point algorithm for the fixed charge problem. Management Sci. 22(5):587–596.Link, Google Scholar
• Wallace SW (2000) Decision making under uncertainty: Is sensitivity analysis of any use? Oper. Res. 48(1):20–25.Link, Google Scholar
• Whitley D (2019) Next generation genetic algorithms: A user’s guide and tutorial. Gendreau M, Potvin JY, eds. Handbook of Metaheuristics (Springer, Cham, Switzerland), 245–274.Crossref, Google Scholar
• Wilson N, Sussman J, Wong H, Higonnet B (1971) Scheduling Algorithms for Dial-a-Ride Systems (Urban Systems Laboratory, Massachusetts Institute of Technology, Cambridge, MA).Google Scholar
• Wolsey L (2003) Strong formulations for mixed integer programs: Valid inequalities and extended formulations. Math. Programming 97(1):423–447.Crossref, Google Scholar
• Yaghini M, Karimi M, Rahbar M, Sharifitabar MH (2015) A cutting-plane neighborhood structure for fixed-charge capacitated multicommodity network design problem. INFORMS J. Comput. 27(1):48–58.Link, Google Scholar