Metaheuristic for the integrated electric vehicle and crew scheduling problem


Hubert Maximilian Sistig, Dirk Uwe Sauer, Applied Energy, Vol. 339, 17 March 2023.



Encouraged by international efforts to reduce greenhouse gases and local emissions, many public transport operators are converting their fleets to battery-powered electric buses. Public transport operators can choose between different electric bus concepts, with the total cost of ownership being the most important decision criterion. The associated strategic decisions regarding charging strategy, vehicle concept, and charging infrastructure have a significant impact on the operational planning of the electric buses.

Motivated by this, this paper aims to analyze the interactions between electrification and operational planning, especially vehicle scheduling and crew scheduling. This allows us to make a more comprehensive comparison of different electrification concepts. Prior work has addressed the impact of electrification on vehicle scheduling but has neglected the interactions with crew scheduling. Crew scheduling dominates operational costs and planning for many public transport operators and must therefore be considered in all strategic decisions. For this reason, in this work we focused on integrated electric vehicle and crew scheduling problem. This allows us to calculate the total cost of ownership of different electric bus concepts under better representation of local conditions. We deal with the electric vehicle and crew scheduling problem with a metaheuristic based on Adaptive Large Neighborhood Search. We tested the developed methodology for a real-world bus route. Our results indicate that the constraints for crew scheduling significantly impact the total cost of ownership and the required number of vehicles of the different electrification concepts. Our case study suggests that the choice of the most cost-effective concept depends significantly on crew scheduling constraints. These findings imply that crew scheduling constraints should be considered as part of the local framework for bus fleet electrification.