The multi-depot electric vehicle scheduling problem with power grid characteristics

Electric buses can bring significant environmental and social benefits in the future public transportation systems. However, the large-scale adoption of electric buses faces major technical challenges caused by not only the limited running range and long charging time, but also the complex power grid characteristics, such as time-of-use (TOU) electricity tariffs and peak load risk. On one hand, the operation cost is determined by the TOU pricing and vehicle schedule. On the other hand, the unbalanced charging demand resulting from the vehicle schedule will cause peak load risk and pose a potential threat to the power grid safety. With the increasing penetration of electric buses, there is a real need to carefully design and manage electric bus scheduling to not only reduce the system costs but also ensure power grid safety. In this paper, we introduce a bi-objective multi-depot electric vehicle scheduling problem, a new generalization to the vehicle scheduling problem where the effects of TOU pricing and peak load risk are explicitly considered. The dual objectives are to minimize the total operation cost and to minimize the peak load resulting from concurrent recharging activities, as constrained by the running range of the electric buses and the capacity of charging depots/stations. A time-expanded network model is devised to represent this problem, while the bi-objective optimization model is reformulated by the lexicographic method. We propose a tailored branch-and-price method to solve the problem. Heuristics and a trip chain pool strategy are embedded into the branch-and-price method to expedite the computation time. Our method is validated through a benchmark network and a real-world bus network in Guangzhou, China. The results demonstrate that our method is effective in cost savings and peak load leveling, and far outperforms the off-the-shelf solver with respect to solution quality and computation efficiency. The real-world application results show that compared to state-of-the-practice, the peak load can be significantly reduced, on top of cost and fleet size savings.