🔢 mathematics

Scalable No-Stockout Charging Scheduling for Battery Swapping Under Time-of-Use Prices

This paper proposes a scalable, price-guided scheduling framework for battery swapping stations that guarantees no stockouts while minimizing time-of-use charging costs, demonstrating through synthetic and real-world data that it achieves near-optimal solutions with significant cost reductions compared to baseline strategies.

Original authors: Eunbin Cho, Junki Cho, Hakjin Lee, Jaehoon Sim, Junghoon Seo

Published 2026-07-28

📖 4 min read🧠 Deep dive

CC BY 4.0

Original authors: Eunbin Cho, Junki Cho, Hakjin Lee, Jaehoon Sim, Junghoon Seo

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine a world where electric vehicles (EVs) don't just sit at a plug for an hour; instead, they zip into a station, swap their dead battery for a fresh one in seconds, and zoom back onto the road. This is the magic of battery swapping. But behind the scenes, the station faces a tricky puzzle: it has a limited number of batteries and chargers, and electricity prices change throughout the day, getting cheaper at night and expensive during the day. The station manager's goal is simple but hard: make sure every car that arrives gets a full battery (no one gets left stranded), while charging the returned batteries only when electricity is cheap. If they charge too early, they waste money; if they wait too long, they might run out of batteries for the next car. This paper dives into that exact puzzle, trying to find the perfect schedule that saves money without ever leaving a customer waiting.

The authors of this paper tackled this scheduling headache by building a super-smart mathematical model. Think of the station as a busy kitchen where the "chefs" are chargers and the "ingredients" are batteries. The challenge is that every time a car leaves with a fresh battery, that specific battery goes on a "trip" and comes back empty at a specific time. The station has to decide: Which empty battery goes to which charger, and when do we start charging it?

To solve this, the team created two versions of a "recipe" (a mathematical program) for the station. The first version, called Model F, was like a massive, detailed instruction manual that tracked every single battery, every charger, and every second of the day. It was accurate but so heavy that it took a long time for computers to solve, especially when the station got big. So, the authors invented a second version, Model R. They realized that many of the steps in the first recipe were redundant. By simplifying the instructions—focusing only on the critical decisions of "which battery for which car" and "when to start charging"—they created a streamlined version that was mathematically identical but much faster. It's like realizing you don't need to write down every step of tying your shoes to know how to do it; you just need the key knots.

The paper then tested these models against a third, faster method called P-BPD (Price-Guided Battery-Path Decomposition). Imagine this as a clever shortcut where the computer doesn't look at every single second of the day. Instead, it looks at the entire "life story" of a single battery: "It serves Car A, then gets charged, then serves Car B." The computer builds these stories like LEGO blocks and snaps them together to form a full schedule. This method is designed to be incredibly fast, even for huge stations.

When they ran simulations, the results were impressive. For small and medium-sized stations, the simplified Model R was able to find the perfect schedule (proven to be the best possible) in less than a second to a few seconds. It was 3 to 7 times faster than the original heavy model. For the massive "xlarge" stations, the exact models sometimes got stuck or took too long, but the P-BPD shortcut always found a working schedule. While the shortcut wasn't perfectly optimal (it was about 7–8% more expensive than the theoretical best in smaller tests, and had a small gap of 9–12% in the largest tests), it was still vastly superior to the old ways of doing things.

The team also tested their methods on real-world data from a commercial battery-swapping station in South Korea, replaying 30 days of actual traffic involving over 1,000 swaps. They compared their smart schedulers against two "dumb" baselines: one that charged batteries immediately when they returned (ASAP) and one that just tried to pick the cheapest slot without worrying about running out of batteries (TOU baseline). The results were clear: the smart schedulers served every single car (100% service rate) and cut the electricity bill by about 50% compared to the "charge immediately" method. Even compared to the smarter "cheapest slot" baseline, they still saved about 1.3%.

In short, the paper proves that you don't have to choose between saving money and keeping customers happy. By using a streamlined mathematical model or a clever "story-based" shortcut, a battery-swapping station can automatically figure out the perfect charging schedule. This ensures that no car ever waits for a battery, while the station owner pays the lowest possible price for electricity, turning a chaotic logistical nightmare into a smooth, profitable operation.

Technical Summary: Scalable No-Stockout Charging Scheduling for Battery Swapping Under Time-of-Use Prices

Problem Definition
The paper addresses the operational challenge of scheduling battery recharging at a battery-swapping station serving a commercial electric vehicle (EV) fleet. The station must guarantee a "no-stockout" service level, ensuring every arriving vehicle receives a fully charged battery immediately, while simultaneously minimizing the total cost of recharging returned batteries under a Time-of-Use (TOU) electricity tariff.

The problem is characterized by three complex constraints:

Heterogeneous Compatibility: Batteries and chargers belong to specific compatibility classes; a battery can only be recharged on a compatible charger.
Event-Specific Dynamics: Each vehicle swap is a distinct event with a specific arrival time and a deterministic return delay. The battery becomes available for recharging only after the trip ends.
Finite Capacity: The station has a limited number of chargers, creating competition for low-price charging slots among waiting batteries.

The objective is to determine, for every service event, which physical battery to dispatch and when to schedule the recharging of the returned battery, such that the total TOU energy cost is minimized without ever failing to serve an arriving vehicle.

Methodology
The authors propose a unified framework combining exact optimization and heuristic decomposition:

Exact Formulations (Model F and Model R):
- Model F: A direct Mixed-Integer Linear Program (MILP) that tracks five families of binary variables: service assignment, charging start times, battery availability, waiting status, and charger occupancy. It explicitly models the state of every physical battery over a finite horizon.
- Model R: A mathematically equivalent reduced formulation. The authors prove that the variables for charger occupancy ( $x$ ), waiting status ( $W$ ), and availability ( $A$ ) can be derived algebraically from the service assignment ( $y$ ) and charging start ( $\sigma$ ) variables. By eliminating $x$ and $W$ and relaxing $A$ to continuous variables (while preserving integrality), Model R significantly reduces the number of explicit binary variables, improving computational tractability without sacrificing optimality.
Price-Guided Battery-Path Decomposition (P-BPD):
- To handle large-scale instances where exact certification is computationally prohibitive, the authors develop a column-generation-based heuristic.
- Path Concept: Each column represents a complete feasible "path" for a single physical battery, encoding a sequence of service events and the associated charging blocks between them.
- Master Problem: A set-partitioning problem selects one path per battery to cover all customer events exactly once while respecting charger capacity constraints.
- Pricing Subproblem: A dynamic programming algorithm generates new paths with negative reduced costs. This subproblem is "price-guided," utilizing dual prices from the master problem to identify charging blocks that minimize the adjusted cost (electricity price plus capacity shadow prices).
- Heuristics: The implementation includes band-limited pricing (restricting the search space to recent predecessors) and greedy warm starts to accelerate convergence.
Rolling-Horizon Control:
- Both Model R and P-BPD are deployed as window solvers within a rolling-horizon controller. At each decision epoch (vehicle arrival or charge completion), the system re-optimizes over a 24-hour look-ahead window using updated fleet information, committing only to immediate actions.

Key Contributions

Exact Per-Battery Model and Reduction: The paper introduces a unified MILP that integrates TOU cost minimization with a hard, per-event no-stockout constraint. The derivation of Model R demonstrates that binary decisions can be concentrated solely on service assignments and charging starts, reducing the explicit binary dimension significantly.
Certified Scaling and Fast Scheduling: Model R extends the range of instances that can be solved to exact certification. The P-BPD heuristic constructs feasible large-scale schedules with certified ex post optimality-gap upper bounds, bridging the gap between theoretical optimality and practical scalability.
Commercial Validation: The study includes a 30-day replay of 1,002 swaps from a real commercial station in South Korea, as well as synthetic scaling studies, quantifying the trade-offs between solution quality, service reliability, and computation time.

Results

Computational Efficiency: In synthetic studies, Model R reduced median certification times by factors of 3.1 to 7.2 compared to the full Model F. For small and medium scales, P-BPD solved instances in 0.24 to 1.4 seconds with cost premiums of only 7–8% over certified optimal solutions.
Scalability: At large scales (54–72 batteries), Model F failed to certify solutions within time limits, while Model R certified a subset of instances. P-BPD successfully generated full-service schedules for all large-scale instances with median solve times of 4.9 to 8.0 seconds and certified optimality gaps of 9–12%.
Cost Savings: Compared to an "immediate charging" baseline (ASAP), the optimized schedules reduced charging energy costs by 50–60%. Compared to a TOU-aware baseline that ignores stockout risks, the proposed method reduced costs by approximately 1.3% while guaranteeing 100% service reliability.
Real-World Replay: In the 30-day replay of the commercial station, both the reduced-model and heuristic controllers served every swap (100% reliability) and achieved the ~50% cost reduction relative to immediate charging. The controllers operated within a 120-second re-planning budget, with median solve times of 3.2 seconds (Model R) and under 2.2 seconds (P-BPD).

Significance
The paper claims to provide a scalable scheduling framework that enforces event-level service guarantees at the resolution of individual physical batteries. By unifying hard service constraints with price-aware optimization, the proposed methods allow battery-swapping stations to shift recharging to low-price periods without compromising fleet availability. The work demonstrates that exact certification is possible for moderate scales via Model R, and that near-optimal, full-service schedules can be generated in real-time for large-scale operations using the P-BPD heuristic. This addresses a critical operational gap in the literature, which often treats inventory and pricing separately or relies on soft service penalties.

Technical Summary: Scalable No-Stockout Charging Scheduling for Battery Swapping Under Time-of-Use Prices

More like this