Ricard, L., Desaulniers, G., Lodi, A., and Rousseau, L.

Stochastic optimization of bus schedules

Speaker: Ricard L�a

International Symposium on Mathematical Programming, GERAD

July 21, 2024

The vehicle scheduling problem (VSP) is one of the sub-problems of public transport planning. It aims to minimize operational costs while assigning exactly one bus per timetabled trip and respecting the capacity of each depot. Public transport planning is subject to various endogenous and exogenous causes of uncertainty, notably affecting travel time and energy consumption. Despite the uncertainties involved, the VSP and its variants are usually solved deterministically to address trackability issues. However, considering deterministic travel time in the VSP can compromise schedule adherence, whereas considering deterministic energy consumption in the electric VSP (E-VSP) may lead to solutions with sub-optimal true costs (including recourse costs and the cost of ownership of battery electric buses). This presentation proposes a methodological framework aimed at integrating uncertainties, specifically travel time and energy consumption uncertainties, into the VSP. Three distinct stochastic, data-driven mathematical models and branch-and-price algorithms are introduced to address two variations of the problem: the multi-depot VSP (MDVSP) and the electric VSP (E-VSP). The objective is to find bus schedules that offer a good trade-off between operational costs and service reliability, as well as between operational costs and battery degradation in electric buses.