Activated Benders Decomposition for Day-Ahead Paratransit Itinerary Planning
针对辅助客运系统面临取消和司机缺席的不确定性，提出两阶段随机优化模型和激活Benders分解算法，在真实数据上比基准方法更快、解更优，能通过增加行程缓冲来降低运营成本。
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/ .