An exact solution approach for an electric bus dispatch problem

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.