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.