Overnight and daytime joint charging scheduling of battery electric buses considering heterogeneous charging piles and depot assignment decision preference

Battery electric buses (BEBs) have been an increasingly important solution in public transport systems to alleviate environmental problems in urban areas due to their energy efficiency and eco-friendliness. With the rapid development of BEB applications, however, there emerge new challenges in BEB charging activities, including the shortage of charging resources and finite charging chances. To cope with the challenges, this work investigates the problem of overnight and daytime joint charging scheduling of BEBs, and focuses on the scenario with heterogeneous charging piles in each charging depot. A mixed integer linear programming (MILP) model is developed with the objective of optimizing the total operational cost. The minimization objective consists of two components: the total charging cost, and the penalty cost incurred by not assigning BEBs to their nearest depots. We first prove that the considered problem is NP-hard, and then prove a theoretical lower bound. Furthermore, we propose a heuristic algorithm and an improved genetic algorithm to solve large-scale instances of the problem. Numerical experiments and sensitivity analyses demonstrate the effectiveness of the established model and the proposed algorithms.