We study how to efficiently plan the daily bus dispatch operation within a public transport terminal working with a fleet of electric buses. This requires to formulate and solve a new variant of the Vehicle Scheduling Problem model, in which one has to assign trip itineraries to each vehicle considering that driving ranges are limited, that each battery’s stage-of-charge must be kept within feasible ranges, and a limited parallel charging capacity. Under this problem setting, one has to simultaneously assign bus itineraries and sequence charging tasks with variable duration to each charging station. To optimally solve our problem, we decompose it into two decision stages; (1) assigning trip itineraries to each vehicle and (2) sequencing battery charging tasks to each station given a set of bus itineraries. Our decomposition is naturally suited for a customized variant of the L-shaped method, in which feasibility cuts are dynamically injected to the LP relaxation to remove itinerary assignments leading to an infeasible second stage. The effectiveness of our solution is tested in computational experiments inspired by a bus operator from Santiago, Chile. We assess the benefits over a single-stage optimization approach and provide managerial insights for planners, such as the marginal benefits provided by an additional charging station and electric bus. Also, we study the flexibility added to the operation when combining electric and conventional buses.
Citation
School of Engineering, Pontificia Universidad Católica de Chile, Santiago, Chile. December 2020.
Article
View An exact solution approach for an electric bus dispatch problem