An exact approach for the multi-depot electric bus scheduling problem with time windows

This study extends the multi-depot vehicle scheduling problem with time windows (MDVSPTW) to the case of electric vehicles which can recharge at charging stations located at any point of the service oper-ation area. We propose a mixed-integer nonlinear model for the electric bus multi-depot vehicle schedul-ing problem with time windows (EB-MDVSPTW). Our formulation considers not only the operational cost of vehicles, but also the waiting times. In addition, it explicitly considers the capacity of charging stations and prohibits the simultaneous charging of different vehicles at the same charger. Chargers are modeled as task nodes of an extended network and can be placed at any location utilizing the charging infrastruc-ture of a city instead of using only bus-dedicated chargers. Further, we linearize the MINLP formulation of the EB-MDVSPTW by reformulating it to a mixed-integer linear program (MILP) that can be solved to global optimality. Because EB-MDVSPTW is NP-Hard, we also introduce valid inequalities to tighten the search space of the MILP and we investigate the trade-off between the compactness and the tightness of the problem in benchmark instances with up to 30 trips. In the numerical experiments, we show that the valid inequalities reduce the problem's compactness by increasing up to three times the number of constraints, but, at the same time, improve tightness resulting in computational time improvements of up to 73% in 20-trip instances. The implementation of our exact approach is demonstrated in a toy network and in the benchmark instances of Carpaneto et al. (1989). (c) 2022 The Author(s). Published by Elsevier B.V. This is an open access article under the CC BY license ( http://creativecommons.org/licenses/by/4.0/ )

Automated summary

This study extends the multi-depot vehicle scheduling problem with time windows (MDVSPTW) to incorporate electric vehicles and proposes a mixed-integer nonlinear model for the electric bus multi-depot vehicle scheduling problem with time windows (EB-MDVSPTW). The model considers operational cost, waiting times, capacity of charging stations, and prohibits simultaneous charging of different vehicles at the same charger. Valid inequalities are introduced to improve the computational efficiency of the problem. Numerical experiments show the effectiveness of the approach and the reduction in computational time.