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

A battery-swapping station must provide every arriving vehicle with a charged battery while minimizing the time-of-use cost of recharging returned units.

Coordinating heterogeneous compatibility, vehicle-specific return times, and finite charger capacity requires service-aware recharge decisions across the planning horizon.

We formulate a per-battery mixed-integer linear program that captures these operational features under a hard no-stockout constraint and derive a provably equivalent reduced form with fewer explicit binary variables.

In the synthetic scaling study, a price-guided battery-path heuristic returned a full-service schedule for every instance; regime-level median solve times ranged from 0.24 to 8.0 seconds.

Its median cost premiums were 7-8% over certified reference costs at the Small and Medium scales, and its certified ex post optimality-gap upper bounds were 9-12% at the Large and xlarge scales.

For each operational baseline, the certified reference schedules reduced charging-energy cost by 50-60% on instances that the baseline fully served and for which a certified reference was available.

In a 30-day replay of 1,002 swaps recorded at a commercial station, the reduced-model and heuristic rolling controllers served every swap and reduced charging-energy cost by approximately 50% relative to immediate charging.