The continuous-time service network design problem (CTSNDP) has wide applications in the field of transportation, but it is complicated by travel time uncertainty resulting from unpredictable traffic conditions. Incorporating uncertain travel times poses a significant challenge, as time-indexed mixed-integer linear programming (MILP) formulations commonly used to solve the CTSNDP with deterministic travel times become impractical. This is due to their inability to distinguish between decisions that rely on travel times and those that do not. To tackle this challenge, we study a robust CTSNDP under travel time uncertainty, aiming to design a transportation service network with reliable operational efficiency even in the presence of travel time deviations. To incorporate the travel time uncertainty in a tractable manner, we propose a novel consolidation-indexed MILP formulation for the deterministic CTSNDP, eliminating the requirement for time indices. This enables us to derive MILP formulations for both a robust optimization model and a robust satisficing model of the CTSNDP under travel time uncertainty. To solve these formulations exactly, we have developed two tailored column-and-constraint generation methods. Our computational results demonstrate the effectiveness of these solution methods and the tractability of the proposed formulations. Furthermore, the robustness of the solutions obtained has also been verified, and the trade-off between the robustness and its price has been highlighted.
Article
View Robust Continuous-Time Service Network Design under Travel Time Uncertainty