Online Optimal Scheduling For Battery Swapping Charging Systems With Partial Delivery

Battery swapping–charging system (BSCS) is a promising operating paradigm to provide centering charging and battery swapping service for electric vehicles in transportation electrification. Facing real-time information on battery demand under the limited transporting trucks, flexible online optimization of battery delivery and transportation routing is essential for meeting practical requirements. This paper investigates the realtime scheduling problem in BSCS, considering the battery partial delivery, energy demand, delivery deadline, and vehicle routing. Considering the non-deterministic polynomiaR1 hardness of battery transportation, the offline BSCS is a time-consuming task and is unsuitable for the online setting. A Lagrangian relaxationbased Benders decomposition is proposed for parallel and realtime implementation, improving the scheduling efficiency. To tackle future information such as battery demands and delivery deadlines, by introducing the dummy copy, the offline algorithm is embedded within a rolling horizon framework to solve in realtime repeatedly. Case studies using real road maps in Shanghai and Belgium have verified the validity of the proposed online framework and confirmed the necessity of considering partial delivery in enhancing the operation flexibility of BSCS. The computational efficiency of the proposed algorithm is studied under different scales of the road network, and the profit from partial delivery and online implementation are highlighted.