Novel Aggregation Framework for Electric Bus Fleet Scheduling

In recent years, electric buses have become a more environmentally friendly alternative to combustion buses. However, their specific barriers, such as limited battery capacity, long charging times, and a limited number of charging stations, make their deployment in public transportation difficult. In this paper, we propose a new aggregation framework for the electric bus scheduling problem. Specifically, each electric bus is assigned a list of daily tasks representing service trips and charging sessions. Charging stations are distributed in the road network, and the charging can be done in-between service trips. We present a mixed-integer linear problem formulation to assign vehicles to service trips and find a suitable charging schedule. As it can be very time-consuming to solve this problem by an exact or heuristic algorithm, we propose a new aggregation framework. The aggregation is performed by a two-phase heuristic algorithm that combines a group of service trips into one, which is then served by a single vehicle. We designed different prioritization criteria to select which trips to aggregate. The efficiency of our framework was evaluated by comparing it with the average objective function and average computation time achieved by a genetic algorithm without aggregation and an exact solution, if possible. The testing instances were generated from real-life data, representing three types of scenarios that differ in maximum battery capacity and energy consumption. The experiments confirm a significant reduction (up to 30-70%) in computational time without worsening the quality of solutions for almost all prioritization criteria and scenarios tested compared to the genetic algorithm without aggregation. These improvements are especially notable on large-scale benchmarks of the electric bus scheduling problem.