An exact solution approach for an electric bus dispatch problem

Document Type

Journal Article

Publication Date

2021

Subject Area

mode - bus, place - south america, place - urban, operations - scheduling, infrastructure - fleet management, infrastructure - maintainance, infrastructure - vehicle, technology - alternative fuels

Keywords

Electric vehicles, Vehicle scheduling, Charger scheduling, Integer programming, Benders’ decomposition

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.

Rights

Permission to publish the abstract has been given by Elsevier, copyright remains with them.

Comments

Transportation Research Part E Home Page:

http://www.sciencedirect.com/science/journal/13665545

Link to Full Text

Share

COinS