Designing reliable bus services with on-time arrival via lane reservation under uncertain travel times

The deployment of dedicated bus lanes is a crucial strategy to improve the appeal of bus transit and is significantly affected by a variety of unpredictable events. This study proposes and investigates a novel optimization problem that jointly considers bus lane deployment and bus routing under uncertain travel times, with the objective of achieving reliable bus services with on-time arrivals. We first formulate it as a stochastic programming model. By leveraging prior data, we then construct a flexible moment information-based ambiguity set to capture uncertain link travel times and incorporate it into a distributionally robust optimization (DRO) model with a probabilistic objective function. The DRO model maximizes the reliability of bus services, defined as the probability of ensuring that a bus arrives on time at each stop in the worst-case scenario while simultaneously limiting passenger waiting times. Furthermore, we introduce a convex decision measure called Probability of Violation Risk to evaluate the risk of any stop not being arrived at within the predetermined expected time window. The designed model is then reformulated as a more tractable mixed-integer second-order cone program, upon which a two-stage matheuristic algorithm (TSMA) is developed specifically to solve large-scale realistic networks. Extensive computational tests are performed to verify the effectiveness and efficiency of the TSMA. The results demonstrate that the DRO model can generate robust dedicated lane deployment and bus routing schemes, with worst-case performance that surpasses those achieved using the widely adopted sample average approximation-based approach, an adapted Monte Carlo simulation-based metaheuristic algorithm, and the conventional Bonferroni correction-based method. Moreover, we compare the obtained solutions with those derived from deterministic and robust optimization models, as well as the DRO model based on the traditional moment ambiguity set. Additionally, we conduct numerical experiments to draw meaningful conclusions regarding the budget, maximum negative impact, tightness of expected arrival time windows, and on-time stop arrival rates.