Activated Benders Decomposition for Day-Ahead Paratransit Itinerary Planning

Paratransit operators have access to advance reservations but face uncertainty from trip cancellations and driver no-shows. This paper optimizes driver itineraries in such reservation-based systems while capturing routing adjustments following operating disruptions. Using a shareability network, we formalize the stochastic itinerary planning problem with advance requests (SIPPAR) via two-stage stochastic optimization with a strong second-stage relaxation. This formulation involves exponentially many variables and constraints. We develop an activated Benders decomposition algorithm that exploits linking relationships between the first-stage and second-stage problems to (i) accelerate the generation of Benders cuts by solving a restricted subproblem and reconstructing global optimality and feasibility cuts and to (ii) strengthen the Benders cuts with locally Pareto-optimal cuts. Using data from a major paratransit platform, we show that our algorithm scales to real-world instances, outperforming several benchmarks in terms of computational times, solution quality, and solution guarantees. From a practical standpoint, the SIPPAR model mitigates operating costs by strategically adding slack to driver itineraries to create flexibility and robustness against disruptions.

History: Accepted by Alice E. Smith, Area Editor for Other.

Funding: This work was supported by the MIT Center for Transportation and Logistics [UPS Fellowship].

Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplemental Information (https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2023.0311) as well as from the IJOC GitHub software repository (https://github.com/INFORMSJoC/2023.0311). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/.