Electric bus charging scheduling on a bus network

This study addresses the electric bus charging scheduling problem (EBCSP) within a bus network comprising multiple bus routes, depots, and a fleet of heterogeneous electric buses (EBs) operated by a public transport (PT) operator. The EBCSP aims to minimize total costs by concurrently determining the assignment of EBs to trips(i.e., EB-to-trip assignment) and their corresponding charging schedules. A partial charging policy allows for flexible charging durations, considering a published timetable consisting of trip tasks. We formulate the EBCSP as a mixed-integer linear programming model and a set-covering formulation. For small-scale EBCSPs, we propose a branch-and-price algorithm utilizing the set-covering formulation for exact solutions. As large-scale EBCSPs pose computational challenges, we develop an optimization-based adaptive large neighborhood search (opt-ALNS) method. The opt-ALNS method employs ALNS operators for EB-to-trip assignment and solves the remaining linear programming problem efficiently. To enhance the opt-ALNS process, we introduce a labeling method to assess solution feasibility and rebuild solutions. Moreover, we incorporate EB battery degradation effects into the proposed method. Finally, we assess the performance of the opt-ALNS method on real-life instances and compare it with the branch-and-price algorithm.