We study the continuous-time service network design problem (CTSNDP) under travel time uncertainty, aiming to design a transportation service network along a continuous-time planning horizon, with robust operational efficiency even in the presence of travel time deviations. Incorporating travel time uncertainty holds a great practical value. However, it poses a significant challenge in both problem formulation and solution computation, as the time-indexed mixed-integer linear programming (MILP) formulations commonly used to solve the CTSNDP with deterministic travel times become impractical. To tackle this challenge, we propose a new consolidation-indexed MILP formulation for the deterministic CTSNDP, which enables us to derive computationally tractable formulations for a robust optimization model and a robust satisficing model. Both of these robust models provide solutions that can mitigate the impact of travel time uncertainty, without knowledge of the precise joint probability distribution of travel times. To compute the exact optimal solutions for these models, we develop two tailored column-and-constraint generation algorithms. This particularly marks the first success of such algorithms in solving a two-stage robust satisficing model, featuring a novel enhanced bisection search procedure for a challenging max-min fractional optimization problem. Our computational results demonstrate the effectiveness of these algorithms, the tractability of the proposed formulations, as well as the trade-offs involved in achieving the robust solutions.
Article
View Robust Service Network Design under Travel Time Uncertainty: Formulations and Exact Solutions