Quantum-Classical Framework for the Joint Optimization of Bidirectional EV Charging and Trip Assignment

AI summary

Overview

Research area: Hybrid quantum–classical optimization, specifically Benders decomposition combined with QAOA for electric-vehicle fleet scheduling and bidirectional (V2G) charging.

Technical level: Advanced. The paper assumes familiarity with mixed-integer linear programming, Benders decomposition, QUBO encodings, and the Quantum Approximate Optimization Algorithm.

Scope (one sentence): The paper proposes and benchmarks a hybrid framework that splits an NP-hard joint EV trip-assignment and bidirectional charging problem into a quantum-solved master problem and a classically solved linear dispatch subproblem, using a sparse recursive state-of-charge formulation and logic-based conflict cuts to keep qubit requirements low.

What This Paper Is About

Fleet operators must decide which electric vehicles serve which customer trips while simultaneously scheduling when each vehicle charges from or discharges to the grid. Solving both decisions jointly is NP-hard, and bidirectional power flows make the battery state-of-charge non-monotonic, which weakens the standard dual-based feasibility cuts used in Benders decomposition. The authors build a hybrid quantum–classical decomposition that assigns the discrete assignment decisions to a QAOA-solved master problem and the continuous power dispatch to a classical linear program, with the goal of recovering MILP-optimal solutions at a qubit cost small enough for near-term hardware.

Key Contributions

1. Logic-based hybrid framework: A hybrid architecture for bidirectional EV charging plus trip assignment that uses logic-based conflict cuts instead of dual-derived feasibility cuts, admitting a near-zero-qubit QUBO encoding for the dominant cut sizes.

2. Recursive SoC formulation: An explicit state-of-charge variable with recursive dynamics that replaces dense cumulative SoC inequalities with simple variable bounds, reducing the SoC block from O(T²) to O(T) nonzeros per vehicle and cutting constraint-matrix density by a factor of approximately T/3 for horizon length T when T ≫ R.

3. Empirical validation against MILP: Demonstration that the framework recovers MILP-optimal objectives on medium benchmark instances with a small auxiliary-qubit budget (mean 5.4 auxiliary qubits across the five reported instances).

4. Hardware proof of concept: End-to-end execution of a small instance (T = 3, N_EV = 2, R = 2) on IBM quantum hardware, converging in a single Benders iteration to the same optimum as Gurobi.

The authors state this is, to their knowledge, the first hybrid quantum–classical framework applied to the joint optimization of bidirectional EV charging and fleet scheduling.

Main Findings

• Density reduction is substantial and measurable: The cumulative formulation's nonzero count is N_EV(T+R)(T+2); the recursive formulation's is N_EV(3T+R+1), giving a ratio approaching T/3. On the large instance (T=768, N_EV=20, R=80), the cumulative model reached 14M nonzeros and Gurobi ran out of memory during model build, while the recursive model used 725K nonzeros and solved in 20.0 minutes (19.1× fewer nonzeros).

• Speedups hold across instance sizes: On (32, 1, 4) the recursive model used 236 nonzeros versus roughly 1K (5.8×), with equal 0.01s time. On (192, 5, 20) it used 15K versus 220K nonzeros (14.4×), solving in 15.1s versus 2.4 minutes (9.6× faster).

• Conflict cuts are overwhelmingly small: Across 50 medium instances, 70–85% of extracted conflicts had size |C_n| ≤ 2, which encode as single-variable fixings or slack-free pairwise quadratic penalties. Cuts with |C_n| ≥ 5 were rare and clustered near zero.

• Size-2 cuts cost zero auxiliary qubits: The dominant conflict-cut case requires no auxiliary qubits for its QUBO encoding; only larger cuts need integer slack variables.

• Near-optimal recovery on medium instances: On five instances with T=192, N_EV=5, R=20, the hybrid Benders approach terminated within a Benders convergence gap ≤ 1% on all instances. Mean objective was −8,706.88 versus −8,711.49 for direct MILP, a mean relative gap of 0.05%. Mean runtime was 181.9 s versus 156.6 s for direct MILP, with a mean of 34 iterations and 36 conflict cuts.

• Runtime is not uniformly better: The authors note that for some instances the hybrid decomposition is slower than direct solution, which they attribute to Benders advantages emerging mainly at large scale (for instance, instance 03 took 600 s hybrid versus 324 s direct).

• Auxiliary-qubit counts are small: The largest auxiliary-qubit count across the reported instances was 14, needed to encode 64 total cuts; instances 01 and 04 required only 1 qubit each, implying only one cut of size > 2.

• Hardware run matches the classical solver: On the T=3, N_EV=2, R=2 instance, the QAOA-driven Benders loop started at a lower bound of −10000 and upper bound of 10000 (gap 20000) with 4 cuts added, then reached lower bound −350, upper bound −350, gap 0, matching Gurobi's −350/−350/0.

• Optimality cuts dominate the remaining qubit budget: Conflict cuts reduce encoding cost significantly, but the authors report that the total qubit budget remains dominated by Benders optimality cuts, which require slack variables and binary expansion.

Methodology in Plain English

The problem is split in two. A master problem decides only the yes/no question of which vehicle serves which trip. A subproblem then takes that assignment as fixed and checks whether a feasible charging and discharging schedule exists, and at what cost, using a standard linear program. If the subproblem is feasible, its dual values produce an optimality cut that tells the master problem how to price future assignments. If it is infeasible, the master problem needs to be told which combination of trips to avoid.

Standard Benders handles infeasibility by extracting a Farkas certificate from the dual, but the authors found these cuts structurally weak under bidirectional power flows, because discharging lets the state of charge move both up and down and breaks the monotonicity that makes dual cuts informative. Instead, they isolate which vehicle's assigned trips cannot be served, then run a deletion filter: remove trips one at a time and re-solve the per-vehicle linear program. Trips whose removal restores feasibility are essential; the rest are dropped. What remains is a minimal inconsistent subset, which becomes a combinatorial cut saying "not all of these trips together."

That cut is what makes the quantum part cheap. Most conflicts involve only two trips, and a pairwise exclusion can be written directly as a quadratic penalty term with no slack variable and no binary expansion, so no extra qubits are needed. The master problem is then mapped to a QUBO, with trip rewards, assignment constraints, optimality cuts and conflict cuts all folded in as penalty terms, and solved with QAOA.

On the modeling side, the authors rewrite the battery state of charge as an explicit variable updated step by step from the previous step, rather than as a cumulative sum over the whole history in every constraint. The dense upper and lower SoC inequalities collapse into simple bounds on that variable, which is where the sparsity gain comes from.

Experiments use the 810-instance dataset of Varga et al., adapted to the bidirectional case by replacing the non-negativity bound on charging power with a symmetric range. Parameters include a trip reward of twice the maximum price times trip energy, a final SoC requirement of 10% of capacity, and fuse limits set to ±N_EV · l_max. Classical runs were done on a Dell laptop with an Intel Core i7-1185G7 (4 cores, 8 logical threads) and 16 GB RAM; the hardware demonstration used an IBM backend.

Why This Matters

Research impact. The paper attacks a specific weakness in applying Benders decomposition to energy problems with bidirectional flows: dual-based feasibility cuts degrade when state-of-charge dynamics are non-monotonic. The deletion-filter conflict cut is a general remedy for that, and the observation that most conflicts are pairwise means the quantum encoding cost of feasibility information is close to zero. The recursive SoC reformulation is a purely classical contribution that independently changes what instance sizes are tractable — the 14M-nonzero model that exhausted Gurobi's memory versus the 725K-nonzero model solved in 20 minutes is a concrete illustration.

Real-world applications.

• Fleet operators (delivery, ride-hailing, car-sharing) deciding which vehicles serve which requests while managing charging windows and electricity prices.
• V2G and V2H energy services, where parked fleets discharge to the grid or a building during peak prices.
• Charge-scheduling under time-of-use tariffs, where the objective trades trip rewards against charging cost.
• Fleet electrification planning, where the question is how many vehicles and how much grid capacity are needed to serve a given request set.

Industry relevance. The framework is aimed at realistic scale rather than toy problems, and it explicitly tracks a qubit budget per instance, which is the metric that determines whether a near-term device can run the master problem at all. The hybrid structure means a operator could deploy it today with a classical MILP master and swap in quantum hardware as qubit counts and cut encodings improve, without changing the decomposition.

Future Directions

• Strengthen or reformulate optimality cuts. The authors identify optimality cuts as the dominant remaining qubit cost and name this as their next target.
• Cut-strengthening techniques. Explicitly listed as planned future work, aimed at reducing the number and size of cuts the master problem must carry.
• Scale the hardware demonstration. The validated instance is T=3, N_EV=2, R=2; extending to instances where the hybrid decomposition's runtime advantage over direct MILP actually materializes remains open, since the medium instances tested were sometimes slower than direct solution.
• Handle larger conflict sets. Cuts with |C_n| ≥ 5 still require integer slack variables and binary expansion; how to encode these without qubit blow-up is unresolved.

Target Audience

Researchers and practitioners working at the intersection of quantum optimization and energy systems — particularly those applying QAOA or quantum annealing to scheduling problems and looking for decompositions that keep qubit counts within near-term budgets. It is also relevant to power systems and fleet-operations researchers interested in the recursive SoC formulation and in why dual-based Benders cuts struggle with bidirectional charging, independent of the quantum component. Readers without background in MILP decomposition or QUBO encoding will find the methodology section demanding.

Authors’ abstract

The integration of bidirectional (V2G) charging allows electric vehicle (EV) fleets to operate as distributed energy assets. However, the joint optimization of charging schedules and trip assignments is NP-hard. Moreover, bidirectional power flows create non-monotonic state-of-charge (SoC) dynamics that weaken standard dual-based Benders cuts. We propose a hybrid quantum-classical Benders decomposition framework. To overcome the qubit overhead associated with encoding feasibility cuts, we introduce logic-based conflict cuts, which require near-zero auxiliary qubits. Furthermore, we develop a sparse recursive SoC formulation that reduces the constraint-matrix density by a factor of T/3 in the horizon length T. We demonstrate that our framework recovers MILP-optimal solutions on benchmark instances with a low auxiliary-qubit budget, and, as a minimal proof of concept, we execute a small instance end-to-end on IBM quantum hardware.