An exact solution approach for an electric bus dispatch problem. (December 2021)

• Record Type: Journal Article
• Authors: Alvo, Matías; Angulo, Gustavo; Klapp, Mathias A.
• Is Part Of: Transportation research. Volume 156(2021)
• Publication Date: 2021-12
• Subjects: Electric vehicles -- Vehicle scheduling -- Charger scheduling -- Integer programming -- Benders' decomposition; Logistics -- Periodicals; Transportation -- Periodicals; 388.011
• DOI: 10.1016/j.tre.2021.102528
• Languages: English
• ISSNs: 1366-5545

Abstract

Abstract: We study how to efficiently plan a bus dispatch operation within a public transport terminal working with a mixed fleet of electric and diesel buses and a restricted number of chargers. To meet the daily trip demand, the terminal dispatcher has to assign a trip schedule and a battery charge plan to each bus and also feasibly sequence charging tasks at each charger. We model this problem as an extension of the Vehicle Scheduling Problem, which we later reformulate via a Benders' type decomposition approach into two sub-problems; (1) a master problem assigning bus trip schedules and (2) a satellite problem sequencing charging tasks for a given set of bus trip schedules. Our exact decomposition approach dynamically injects feasibility cuts into the branch-and-bound tree to remove bus trip schedules leading to an infeasible bus charging operation. We assess the effectiveness of our approach and its advantage over a single-stage model in computational experiments inspired by a bus operator from Santiago, Chile. Finally, we provide several managerial insights for planners such as the marginal benefit per additional charger or electric bus and the value added by a mixed fleet compared to a pure electric one. Highlights: We study electric bus dispatch decisions at a terminal with charge task duration decisions and limited parallel charging capacity. We present a novel formulation for the problem, in which decisions are decomposed into two stages. We provide insights, such as estimating the benefit of an additional electric charger and bus and the operational flexibility of a mixed fleet.