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/ .

Stochastic programming involves large-scale optimization with exponentially many scenarios. This paper proposes an optimization-based scenario reduction approach to generate high-quality solutions and tight lower bounds by only solving small-scale instances, with a limited number of scenarios. First, we formulate a scenario subset selection model that optimizes the recourse approximation over a pool of solutions. We provide a theoretical justification of our formulation, and a tailored heuristic to solve it. Second, we propose a scenario assortment optimization approach to compute a lower bound—hence, an optimality gap—by relaxing nonanticipativity constraints across scenario “bundles.” To solve it, we design a new column-evaluation-and-generation algorithm, which provides a generalizable method for optimization problems featuring many decision variables and hard-to-estimate objective parameters. We test our approach on stochastic programs with continuous and mixed-integer recourse. Results show that (i) our scenario reduction method dominates scenario reduction benchmarks, (ii) our scenario assortment optimization, combined with column-evaluation-and-generation, yields tight lower bounds, and (iii) our overall approach results in stronger solutions, tighter lower bounds, and faster computational times than state-of-the-art stochastic programming algorithms. History: Accepted by Andrea Lodi, Area Editor for Design and Analysis of Algorithms–Discrete. Supplemental Material: The e-companion is available at https://doi.org/10.1287/ijoc.2023.1295 .