Activated Benders Decomposition for Day-Ahead Paratransit Itinerary Planning

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
• Bandi C, Gupta D (2020) Operating room staffing and scheduling. Manufacturing Service Oper. Management 22(5):958–974.Link, Google Scholar
• Bard JF, Kontoravdis G, Yu G (2002) A branch-and-cut procedure for the vehicle routing problem with time windows. Transportation Sci. 36(2):250–269.Link, Google Scholar
• Bertsimas D, Mundru N (2023) Optimization-based scenario reduction for data-driven two-stage stochastic optimization. Oper. Res. 71(4):1343–1361.Link, Google Scholar
• Bertsimas D, Yan J (2020) The edge of optimization in large-scale vehicle routing for paratransit. Working paper, Massachusetts Institute of Technology, Cambridge, MA.Google Scholar
• Bertsimas D, Jaillet P, Martin S (2019) Online vehicle routing: The edge of optimization in large-scale applications. Oper. Res. 67(1):143–162.Link, Google Scholar
• Bodur M, Luedtke JR (2017) Mixed-integer rounding enhanced benders decomposition for multiclass service-system staffing and scheduling with arrival rate uncertainty. Management Sci. 63(7):2073–2091.Link, Google Scholar
• Bodur M, Dash S, Günlük O, Luedtke J (2017) Strengthened benders cuts for stochastic integer programs with continuous recourse. INFORMS J. Comput. 29(1):77–91.Link, Google Scholar
• Contreras I, Cordeau JF, Laporte G (2011) Benders decomposition for large-scale uncapacitated hub location. Oper. Res. 59(6):1477–1490.Link, Google Scholar
• Cordeau JF, Soumis F, Desrosiers J (2000) A benders decomposition approach for the locomotive and car assignment problem. Transportation Sci. 34(2):133–149.Link, Google Scholar
• Cordeau JF, Stojković G, Soumis F, Desrosiers J (2001) Benders decomposition for simultaneous aircraft routing and crew scheduling. Transportation Sci. 35(4):375–388.Link, Google Scholar
• Cummings K, Jacquillat A, Vaze V (2025) Activated Benders decomposition for day-before paratransit itinerary planning. http://dx.doi.org/10.1287/ijoc.2023.0311, https://github.com/INFORMSJoC/2023.0311.Google Scholar
• Dai H, Liu P (2020) Workforce planning for O2O delivery systems with crowdsourced drivers. Ann. Oper. Res. 291(1):219–245.Crossref, Google Scholar
• Desrochers M, Desrosiers J, Solomon M (1992) A new optimization algorithm for the vehicle routing problem with time windows. Oper. Res. 40(2):342–354.Link, Google Scholar
• Dunning I, Huchette J, Lubin M (2017) JuMP: A modeling language for mathematical optimization. SIAM Rev. 59(2):295–320.Crossref, Google Scholar
• Fischetti M, Lodi A (2003) Local branching. Math. Programming 98(1):23–47.Crossref, Google Scholar
• Fisher ML, Jörnsten KO, Madsen OB (1997) Vehicle routing with time windows: Two optimization algorithms. Oper. Res. 45(3):488–492.Link, Google Scholar
• Fu L (2002) Scheduling dial-a-ride paratransit under time-varying, stochastic congestion. Transportation Res. Part B Methodological 36(6):485–506.Crossref, Google Scholar
• Goel A (2009) Vehicle scheduling and routing with drivers’ working hours. Transportation Sci. 43(1):17–26.Link, Google Scholar
• Goel A, Vidal T (2014) Hours of service regulations in road freight transport: An optimization-based international assessment. Transportation Sci. 48(3):391–412.Link, Google Scholar
• Groër C, Golden B, Wasil E (2009) The consistent vehicle routing problem. Manufacturing Service Oper. Management 11(4):630–643.Link, Google Scholar
• Guo X, Samaranayake S (2022) Shareability network based decomposition approach for solving large-scale single school routing problems. Transportation Res. Part C Emerging Tech. 140:103691.Crossref, Google Scholar
• Ioachim I, Desrosiers J, Dumas Y, Solomon MM, Villeneuve D (1995) A request clustering algorithm for door-to-door handicapped transportation. Transportation Sci. 29(1):63–78.Link, Google Scholar
• Karabuk S (2009) A nested decomposition approach for solving the paratransit vehicle scheduling problem. Transportation Res. Part B Methodological 43(4):448–465.Crossref, Google Scholar
• Kim K, Mehrotra S (2015) A two-stage stochastic integer programming approach to integrated staffing and scheduling with application to nurse management. Oper. Res. 63(6):1431–1451.Link, Google Scholar
• Kınay ÖB, Gzara F, Alumur SA (2021) Full cover charging station location problem with routing. Transportation Res. Part B Methodological 144:1–22.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
• Magnanti TL, Wong RT (1981) Accelerating benders decomposition: Algorithmic enhancement and model selection criteria. Oper. Res. 29(3):464–484.Link, Google Scholar
• Meshram A (2018) Best Practices in ADA Paratransit: Cost Reduction and Service Enhancement (University of California, Davis).Google Scholar
• Muter I, Birbil Şİ, Bülbül K (2013) Simultaneous column-and-row generation for large-scale linear programs with column-dependent-rows. Math. Programming 142(1):47–82.Crossref, Google Scholar
• Muter I, Birbil Şİ, Bülbül K (2018) Benders decomposition and column-and-row generation for solving large-scale linear programs with column-dependent-rows. Eur. J. Oper. Res. 264(1):29–45.Crossref, Google Scholar
• National Transit Database (2021) National transit summaries & trends. Technical report, Federal Transit Administration. Accessed August 31, 2023, https://www.transit.dot.gov/sites/fta.dot.gov/files/2022-11/2021\%20National\%20Transit\%20Summaries\%20and\%20Trends_1-1.pdf.Google Scholar
• Papadakos N (2008) Practical enhancements to the Magnanti–Wong method. Oper. Res. Lett. 36(4):444–449.Crossref, Google Scholar
• Prescott-Gagnon E, Desaulniers G, Drexl M, Rousseau LM (2010) European driver rules in vehicle routing with time windows. Transportation Sci. 44(4):455–473.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
• Rei W, Cordeau JF, Gendreau M, Soriano P (2009) Accelerating benders decomposition by local branching. INFORMS J. Comput. 21(2):333–345.Link, Google Scholar
• Restrepo MI, Semet F, Pocreau T (2019) Integrated shift scheduling and load assignment optimization for attended home delivery. Transportation Sci. 53(4):1150–1174.Link, Google Scholar
• Römisch W (2009) Scenario reduction techniques in stochastic programming. Proc. Internat. Sympos. Stochastic Algorithms (Springer, Berlin), 1–14.Google Scholar
• Sherali HD, Lunday BJ (2013) On generating maximal nondominated benders cuts. Ann. Oper. Res. 210(1):57–72.Crossref, Google Scholar
• Sivagnanam A, Kadir SU, Mukhopadhyay A, Pugliese P, Dubey A, Samaranayake S, Laszka A (2022) Offline vehicle routing problem with online bookings: A novel problem formulation with applications to paratransit. Preprint, submitted May 5, https://arxiv.org/abs/2204.11992.Google Scholar
• Smilowitz K, Nowak M, Jiang T (2013) Workforce management in periodic delivery operations. Transportation Sci. 47(2):214–230.Link, Google Scholar
• Taherkhani G, Alumur SA, Hosseini M (2020) Benders decomposition for the profit maximizing capacitated hub location problem with multiple demand classes. Transportation Sci. 54(6):1446–1470.Link, Google Scholar
• Ulmer MW, Savelsbergh M (2020) Workforce scheduling in the era of crowdsourced delivery. Transportation Sci. 54(4):1113–1133.Link, Google Scholar
• Vazifeh MM, Santi P, Resta G, Strogatz SH, Ratti C (2018) Addressing the minimum fleet problem in on-demand urban mobility. Nature 557(7706):534–538.Crossref, Google Scholar
• Véricourt F, Jennings OB (2011) Nurse staffing in medical units: A queueing perspective. Oper. Res. 59(6):1320–1331.Link, Google Scholar
• Wang K, Zhen L, Xia J, Baldacci R, Wang S (2022) Routing optimization with generalized consistency requirements. Transportation Sci. 56(1):223–244.Link, Google Scholar
• Wilbur M, Kadir SU, Kim Y, Pettet G, Mukhopadhyay A, Pugliese P, Samaranayake S, et al. (2022) An online approach to solve the dynamic vehicle routing problem with stochastic trip requests for paratransit services. Proc. ACM/IEEE 13th Internat. Conf. Cyber-Physical Systems (IEEE, Piscataway, NJ), 147–158.Google Scholar
• World Health Organization (2001) IFC: International Classification of Functioning, Disability and Health (World Health Organization, Geneva).Google Scholar
• Wu L, Adulyasak Y, Cordeau JF, Wang S (2022) Vessel service planning in seaports. Oper. Res. 70(4):2032–2053.Link, Google Scholar
• Yankovic N, Green LV (2011) Identifying good nursing levels: A queuing approach. Oper. Res. 59(4):942–955.Link, Google Scholar
• Yen JY (1971) Finding the K shortest loopless paths in a network. Management Sci. 17(11):712–716.Link, Google Scholar
• Zhang W, Jacquillat A, Wang K, Wang S (2023a) Routing optimization with vehicle–customer coordination. Management Sci. 69(11):6876–6897.Link, Google Scholar
• Zhang W, Wang K, Jacquillat A, Wang S (2023b) Optimized scenario reduction: Solving large-scale stochastic programs with quality guarantees. INFORMS J. Comput. 35(4):886–908.Link, Google Scholar