Optimal public transport timetabling and vehicle scheduling with multi-depot multi-type battery-electric vehicles

To accommodate fluctuated public transport (PT) passenger demand and recharging management of battery-electric vehicles (BEVs), a multi-depot vehicle-type scheduling problem (MDVTSP) is modeled to consider not only heterogeneous batteries and load capacities, but also timetabling as an emerging study for BEVs. The objective is to minimize the cost of the number of chargers, recharging queue times, fleet size. The PT network-level operations planning is extended to include arcs to represent deadheading trips. A mixed integer linear programming model is derived by means of linearization techniques. The complex multidimensional computation problem is solved by a Lagrangian-relaxation (LR)-based algorithm. Specifically, the decomposition subproblems are modeled individually and resolved as per a tailored heuristic, especially using the deficit function to track the dynamic number of chargers. The results show a significant total cost reduction of 35.37% with a 36.11% decrease of the total PT fleet size compared with the original scheme.