Empowering MetroAccess Service with Nested Decomposition and Service Type Integration

Tens of millions of Americans face severe mobility barriers because of travel-limiting disabilities and thus depend on paratransit, a door-to-door shared-ride service. However, this crucial service faces significant operational and financial challenges. Therefore, through a university-industry collaboration, we have identified (1) modernizing the optimization engine in paratransit scheduling software suites, and (2) incorporating alternative service providers in paratransit service optimization as two critical steps in overcoming some challenges in paratransit practice. We thus developed a nested decomposition method in which a column generation–based solution approach is embedded in a temporal decomposition framework. Additionally, we integrated alternative service types, such as accessible taxis, in paratransit scheduling and designed a reoptimization procedure. The new optimization methods were implemented in a software suite of IT Curves and deployed in paratransit operations in the Washington, DC, metro area. It was found that the improved optimization engine, relative to the legacy, led to significant improvements in key operational metrics and yielded substantial operating cost reductions (approximately 15%). The fruitful collaboration not only showcases the potential for advanced algorithms to significantly enhance the financial sustainability of paratransit services but also reflects the importance of bridging the gap between theoretical research and practical application in transit vehicle routing.