CS Paper Radar

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

Can Berk Saner

eess.SY ·submitted 2026-11-07 18:50 UTC · v1

Abstract

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.

Comment
10 pages, 6 figures. This work has been submitted to the IEEE for possible publication. Copyright may be transferred without notice, after which this version may no longer be accessible

Closest papers

Nearest neighbours by meaning across the whole index.

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.33

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.60
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

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

eess.SY ·2026-11-18 ·Joas Kahlert, Ruiting Wang, Gabrijela Obradović, Henrik Svärd, Jonas Mårtensson
similarity 0.57
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.

0.25

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.57
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

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.57
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

Robust Joint Planning of EV and eBus Charging Infrastructure with PV Self-Consumption under Demand Uncertainty

eess.SY ·2026-08-19 ·Biswarup Mukherjee
benchmark similarity 0.56
Abstract · This manuscript has been submitted for peer review

This paper presents a mixed-integer linear programming (MILP) framework for joint electric vehicle (EV) and electric bus (eBus) charging-infrastructure planning with photovoltaic (PV) self-consumption. The model co-optimizes charger siting, sizing, technology selection, eBus-to-depot assignment, and hourly charging schedules. A deterministic MILP is first formulated as a nominal benchmark and then extended to a scenario-based robust min--max formulation under vehicle energy-demand uncertainty. The robust model uses shared first-stage infrastructure decisions and scenario-specific operating decisions, and minimizes infrastructure cost plus the worst-case scenario operating cost through an epigraph reformulation. Soft-feasibility penalties quantify unmet charging energy, terminal state-of-charge (SOC) shortfall, and capacity violations under stressed scenarios. A 50-node case study shows that route-segment eBus demand and PV weighting alter charger deployment, technology mix, and grid import, while V2G enables hard-feasible robust operation at sufficiently large penalty weights. These results highlight that effective long-term infrastructure planning must simultaneously account for diverse vehicle fleets, operational strategies that adapt to different scenarios, and node-level constraints on charging capacity.

0.19

Adaptive Operator Selection in Bilevel Large Neighborhood Search for Electric Autonomous Dial-a-Ride Problem under Uncertainty

cs.NE cs.AI ·2026-10-03 ·Ishara Hewa Pathiranange, Aneta Neumann
similarity 0.56
Abstract

The electric autonomous dial-a-ride problem (EADARP) extends the classical dial-a-ride problem by incorporating battery and charging constraints for electric vehicles. In practice, travel-time uncertainty can cause violations of time-window constraints. Large neighborhood search is effective for solving the EADARP, but its performance can depend on the choice of insertion operator during the repair phase. This paper investigates insertion-operator selection within a bilevel large neighborhood search framework for deterministic and chance-constrained variants of the EADARP. In the chance-constrained variant, arc travel times are modeled as independent normally distributed random variables, and upper time-window constraints are enforced probabilistically. We consider six selection methods, namely fixed greedy insertion, fixed regret-based insertion, random selection, a deterministic state-based rule, performance-adaptive ALNS selection, and LLM-based state-aware selection. Experimental results show comparable performance on smaller instances, while differences become more evident on larger and more constrained instances. There is no single strategy that performs best across all instances, and the relative performance of the LLM-based, rule-based, and ALNS strategies varies with the problem instance and experimental setting.

0.25

Multi-objective Electric Vehicle Charging Strategies at Energy Hubs with Justice-informed Profit Distribution among Users

eess.SY ·2026-11-05 ·Twan Stolwijk, Diego Fernandez-Zapico, Alessandro Piazza, Mauro Salazar
similarity 0.55
Abstract

This paper studies potential energy cost savings in electric vehicle (EV) charging hubs when users allow cooperative vehicle-to-grid (V2G), and how such savings should be redistributed. To this end, we present multi-objective operational strategies and justice-informed profit sharing methods for a charging energy hub equipped with a battery storage system and solar panels. Specifically, we first frame the dynamic energy hub operational problem aiming to minimize a combination of grid costs and emissions, accounting for time-varying prices and energy mix as well as storage system and EV battery degradation, which is especially relevant when considering V2G operations. We parse the problem as a second-order conic program that can be efficiently solved to global optimality. Our real-world case-study shows the importance of flexibility for hub operation: Equipping a charging station with a stationary battery and leveraging dynamic V2G can significantly reduce the total costs and emissions compared to conventional settings without a battery or dynamic charging by more than 10%. To redistribute these cost benefits to users, we compare standard Nash bargaining with a justice-informed sufficientarian version which caps charging prices to safeguard adequate access to affordable charging. Our results show that the sufficientarian approach better accounts for inequalities in flexibility capital without significantly affecting aggregate costs, highlighting how justice-informed pricing only marginally affects total revenues.

0.24