CS Paper Radar

Scalable Vehicle Charging Coordination for Online Operations: A Column Generation Approach

Joas Kahlert, Ruiting Wang, Gabrijela Obradović, Henrik Svärd, Jonas Mårtensson

eess.SY ·submitted 2026-11-18 08:16 UTC · v1

Abstract

We consider an electric vehicle charging scheduling problem for long-haul freight transport. To mitigate unforeseen waiting times caused by congestion and limited charger capacity, we consider a coordinated scheduling approach that prioritizes scalable, computationally efficient scheduling for ongoing or online operations. We formulate the problem as a set partitioning model and develop a column generation framework with a label-correcting algorithm to solve it efficiently. We assess the scalability of our algorithm through both theoretical complexity analysis and empirical measurements, highlighting the role of feasibility and dominance pruning in limiting label growth. Finally, using freight telematics data from Sweden, we show that the proposed method computes optimized schedules for realistic instances with 1000 vehicles within seconds and reduces vehicle operation downtime by 78.6% compared to uncoordinated scheduling.

Closest papers

Nearest neighbours by meaning across the whole index.

Hours-of-service-aware siting of charging and battery-swapping stations for long-haul electric trucks under adoption uncertainty

cs.CE ·2026-10-06 ·Elnaz Irannezhad, Jia Guo
similarity 0.62
Abstract · 43 pages, 6 figures, 10 tables

Planning en-route charging and battery-swapping infrastructure for long-haul battery-electric trucks (BETs) requires models that reflect how trucks actually operate. This paper develops a mixed-integer programming framework that jointly sites charging or swapping stations and schedules each truck's charging, swapping and mandatory driver rest, so that charging time overlaps with regulated rest instead of being added to it. Energy use is derived segment by segment from road terrain with a tractive-force model, and the truck battery is modelled as a set of independently swappable packs. Staged investment under uncertain BET adoption is formulated as a multistage stochastic program with Markovian demand and solved by stochastic dual dynamic integer programming (SDDiP) with Lagrangian cuts; we show that the Lagrangian multipliers can be bounded by each station's annualised cost without weakening the cuts. Applied to twelve freight corridors on Australia's East Coast, the algorithm jointly optimises charging and battery-swapping events as well as mandatory break events. A +/- 30\% change in adoption alters the final charge-only network by only -12\% to +13\% of stations, with over 95\% of stations built by the second stage. Hedging against uncertainty mainly changes which sites are chosen (71\% overlap with a deterministic rolling-horizon model), not when they are built.

0.14

MAC+: Mobility-Aware Co-Expansion Planning for Distribution Grid and Electric Vehicle Charging Infrastructure

eess.SY ·2026-11-09 ·Yi Ju, Lunlong Li, Jingchun Wang, Scott Moura
similarity 0.62
Abstract · 20 pages, 6 figures, 7 tables

We study the least-cost co-expansion of power distribution networks and public charging ports to accommodate the growth of electric vehicles (EVs). Our approach, MAC+, exploits the flexibility of charging along each EV's itinerary and coordinates it across the fleet to reduce the peak violations of each feeder's hosting capacity and port capacity. This coordination is an extremely large, spatio-temporally coupled optimization problem with binary plug-in variables. We solve it by iterated price response (IPR), which repeatedly posts a two-tier tariff on feeder load and port occupancy, lets millions of EVs best-respond in parallel, and certifies the optimality gap at every iteration. We develop a custom exact dynamic-programming algorithm that solves each EV's best-response problem, a mixed-integer quadratic program, about 20 times faster than off-the-shelf solvers. The case study covers the San Francisco Bay Area at 30% EV adoption, with 1.8 million EVs on week-long itineraries and 1,303 feeder service regions, each with a utility-published hosting capacity and a port capacity set by its existing public ports. On this instance, IPR reaches a certified gap below 10% in a few hours. MAC+ saves about $15 billion of the upgrade investment that unmanaged charging would require. It also needs over 90% less investment than charging that is fully coordinated but flexible only within each session, and over 80% less than charging that is flexible along the itinerary but uncoordinated.

0.26

Rethinking electrified transportation: The case for dynamic wireless charging

eess.SY ·2026-10-13 ·Dipanjan Ghose, Junjie Qin, S. Sivaranjani
similarity 0.60
Abstract

Long-term infrastructure investment often requires choosing between an established technology and a capital-intensive alternative that gains value as demand matures. For electric vehicle (EV) charging, this trade-off is between incumbent stationary charging technology and emerging dynamic wireless charging (DWC). DWC could fundamentally alter transportation electrification by enabling high-throughput charging in motion and reducing reliance on large onboard batteries; however, its high upfront cost makes the timing and location of deployment critical. Overcommitting to stationary charging stations (SCS) risks technological lock-in and forgoing the benefits of DWC, whereas premature DWC deployment can strand capital in underutilized corridors. Through a joint investment assessment framework coupling DWC, SCS, and supporting grid infrastructure across nearly 49,000 miles of the US Interstate freight network, we find that higher utilization and longer project lifetimes rapidly shift investment toward DWC, whose share rises sharply from 48% at a project lifetime of 30 years to 100% at 32 years. Contiguous DWC segments can share grid connections, enabling them to provide over six times the rated charging capacity of SCS while requiring 46% less investment in new distribution-grid infrastructure. We also find that a combined DWC and SCS portfolio reaches a maximum lifetime value of USD 60 billion, 63% above the case with only SCS. We further identify specific traffic demand, construction, and grid access conditions that shape where each technology becomes advantageous, yielding actionable thresholds for SCS and DWC deployment that directly inform long-term EV charging infrastructure investment and policy.

0.41

Optimal Control Strategies for a Network of Electric Vehicle Charging Energy Hubs with Smart Scheduling via Distributed Optimization

eess.SY ·2026-09-15 ·Diego Fernandez-Zapico, Finn Vehlhaber, Maedeh Izadi, Theo Hofman, Mauro Salazar
similarity 0.59
Abstract

This paper studies the cost-optimal operation of a network of charging energy hubs for electric vehicles, which provide onsite renewable energy sources and stationary battery storage and are connected with each other via DC-lines as well as with the distribution grid. Specifically, we first formulate a dynamic optimal control problem for the entire network as a convex quadratic program, whereby the charging power profiles of the individual vehicles and the energy flows between hubs and the grid are subject to optimization. Second, we propose a problem decomposition that allows for a distributed solution via ADMM algorithms that preserves global optimality guarantees and privacy of the individual stations. We showcase our framework on a case-study for the Netherlands considering a two-day ahead deterministic formulation with perfect foresight. Our results show that compared to the case where charging powers are fixed a priori, optimizing their profiles (V1G) can significantly reduce the operational costs and emissions by more than 25%. Moreover, we verify our distributed algorithm against a centralized solution, paving the way to the optimal operation of large networks and online implementations.

0.17

Co-optimizing Bidding and Power Allocation of an EV Aggregator Providing Real-time Frequency Regulation Service

eess.SY ·2026-08-25 ·Ruike Lyu, Hongye Guo, Kedi Zheng, Mingyang Sun, Qixin Chen
top venuehighly cited similarity 0.58
Abstract · Published in: IEEE Transactions on Smart Grid ( Volume: 14, Issue: 6, November 2023)

The rapidly expanding scale of electric vehicle (EV) fleets and continuously decreasing battery costs are making vehicle-to-grid services a reality. In this paper, we study the interaction between the problems of an EV aggregator's bidding in the regulation market and power allocation (i.e., determining the (dis)charging powers of the EVs in regulation deployment). Although the two problems are coupled, they are often regarded as decoupled and optimized separately for complexity issues. However, failing to consider the coupling of bidding and power allocation can lead to a decline in the profit of the EV aggregator (EVA). In this paper, we propose a framework for co-optimizing EVA bidding and power allocation in the regulation market. The bidding model is formulated as a stochastic programming problem with embedded power allocation in discretized regulation signal scenarios. To meet the solution time requirement for regulation deployment, we further propose a power allocation model that can be solved online. It utilizes the Lagrange multipliers from the bidding problem to ensure that the allocation results correspond to the optimal solution of the bidding problem. The effect of the proposed framework on improving EVA profits and reducing degradation costs is verified in the case study.

0.67

Bisect-Index-Choose: A Fast and Exact Algorithm for EV Charging under Minimum Charging Rates

eess.SY ·2026-11-07 ·Can Berk Saner
similarity 0.57
Abstract · 10 pages, 6 figures. This work has been submitted to the IEEE for possible publication. Copyright may be transferred without notice, after w…

Electric vehicle (EV) charging stations are increasingly operated with an aggregate power limit below the sum of their port ratings, and require scheduling algorithms to divide the available power among the connected EVs. Charging standards permit a current that is either zero or at least a minimum rate, typically 6 A, which makes this allocation problem non-convex. Existing methods either solve a mixed-integer program with a commercial solver, which can be computationally expensive, adds software dependencies, and incurs licensing costs, or apply heuristics without optimality guarantees. This paper proposes Bisect-Index-Choose (BIC), a fast and solver-free scheduling algorithm that computes a globally optimal allocation among EVs under mild assumptions on their utilities. For $n$ EVs, BIC runs in $O(n \log n)$ time when all EVs share one maximum rate and in $O(n^2)$ time for two, times a logarithmic factor in the numerical precision. In tests with up to 1000 EVs, BIC attains global optimality and is up to three orders of magnitude faster than the solver. On real-world charging data, it needs less capacity and delivers more energy than existing heuristics. We implement BIC on a low-cost microcontroller and show that it solves instances with 1000 EVs in less than 90 ms.

0.30

L2R-EV: Learning What to Repair in Electric Ride-Pooling with Finite Charger Queues

cs.GT ·2026-09-30 ·Mai Pham, Vikrant S. Vaze, Peter Chin
similarity 0.56
Abstract

Electric ride-pooling must jointly manage passenger service, routes, batteries, and finite chargers; a locally useful relocation can reduce later service. We introduce a discrete-event ride-pooling simulator with ordered passenger stops, pickup and ride-time constraints, battery reserves, charger travel, and finite first-come, first-served (FCFS) charging queues. On top of a common dispatcher, we add a learned repair layer that moves uncollected passengers between vehicles, uses a supervised score to estimate later effects, and uses a two-stage proximal-policy-optimization (PPO) policy to focus computation on promising moves. Every executed move must satisfy route, battery, and time constraints and provide an immediate route-cost improvement. For larger instances, we limit the number of candidate moves and apply several non-conflicting repairs at once. On 12 held-out Manhattan episodes with 100 requests, 30 EVs, and one plug per station, supervised repair reduces operational cost by 6.57\% versus no repair (12/12 wins) and serves 74.92 rather than 72.75 requests. Two-stage PPO stays within 1.43\% of supervised repair with 95.4\% fewer exact trials, while our experiments scale to 8,000 requests and 2,400 EVs with cost reductions across all three larger development settings. Queue-aware charging reduces waiting by 41.0\%; under a declared 1.5-kW queue-idle load, operational electricity per served request falls 1.73\%.

0.19

Online Bin Packing with Dispatch Deadlines

cs.DS ·2026-11-05 ·Pei-Lin Chiang, Wing-Kai Hon, Kazuo Iwama, Li-Tzu Yang
published similarity 0.56
Abstract · 16 pages, 1 figure. Full version of a paper to appear in the 37th International Symposium on Algorithms and Computation (ISAAC 2026)

We study a generalization of online bin packing by introducing dispatch deadlines. Items arrive over time in an online fashion. Each item has an arrival time, a size in $(0,1]$, and a deadline, all of which are revealed only when the item arrives. The algorithm must immediately and irrevocably assign the item to a unit-capacity bin that has not yet been dispatched. Each bin must be dispatched no later than the earliest deadline of the items assigned to it, and once it is dispatched, it cannot be used for future items. The goal is to minimize the number of bins used. Applications arise naturally in logistics. Additionally, the offline version of this problem has appeared under several names, including the clique partition problem in weighted interval graphs and the BinSchedule problem. This problem is also a special case of online bin packing with conflicts and is closely related to online bin packing models with delay costs. We study the competitive ratios of several classical online bin packing algorithms when applied to this problem, and show that a similar hierarchy of competitive ratios carries over. Our main technical results are that the competitive ratio of First-Fit is exactly $16/7 \approx 2.28571$, and that no deterministic online algorithm has a competitive ratio less than $11/5 = 2.2$, showing that First-Fit is quite close to best possible. In addition, Next-Fit and Worst-Fit have competitive ratio exactly $3$, and every algorithm in the Any-Fit class has competitive ratio between $16/7$ and $3$.

0.36