A Constraint Programming Model for the Electric Bus Assignment Problem with Parking Constraints

Electric buses serve as a key leverage in mitigating the transportation sector’s carbon footprint. However, they pose a challenge, requiring transit agencies to adapt to a new operational approach. In particular, the assignment of buses to trips is more complex because it must consider the planning of the recharging activities. Unlike diesel buses, electric buses have less autonomy and take longer to refuel. In this paper, we address the assignment of electric buses to trips and the scheduling of charging events, taking into account parking constraints at the depot (a novelty in the literature). These constraints are particularly relevant in countries such as Canada where the buses are parked indoors to shelter them from harsh winter conditions. This problem, called the electric Bus Assignment Problem with Parking Constraints (eBAP-PC), is a feasibility problem. We propose a Constraint Programming model to solve it and compare it to mixed-integer linear programming approaches. In particular, we show its benefits for solving this problem with a one-day horizon and minimum end-of-day charge level constraints.

Recommended citation: Azéma, M., Desaulniers, G., Mendoza, J.E., Pesant, G. (2024). A Constraint Programming Model for the Electric Bus Assignment Problem with Parking Constraints. In: Dilkina, B. (eds) Integration of Constraint Programming, Artificial Intelligence, and Operations Research. CPAIOR 2024. Lecture Notes in Computer Science, vol 14742. Springer, Cham.
Download Paper | Download Slides