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

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.

The paper studies joint trip assignment and bidirectional charging/discharging for electric-vehicle fleets, formulated as a mixed-integer linear program with battery, scheduling, and grid constraints. It proposes Benders decomposition in which a binary trip-assignment master problem is encoded for QAOA, while classical linear programs determine dispatch feasibility and cost. Two formulation changes are developed. Explicit recursive state-of-charge variables replace cumulative constraints, reducing the state-of-charge block’s nonzero count from an expected $N_{\mathrm{EV}}(T+R)(T+2)$ to $N_{\mathrm{EV}}(3T+R+1)$, approximately a factor $T/3$ when $T\gg R$. Logic-based feasibility cuts are obtained by deleting trips until a minimal infeasible assignment subset remains. Reportedly, 70–85% of conflicts contain at most two trips and require no auxiliary qubits. This procedure assumes nonbinding grid limits so dispatch feasibility separates by vehicle. On five instances with $T=192$, five vehicles, and 20 trips, decomposition terminates with certified Benders gaps below 1% and a mean objective difference of 0.05% from direct MILP solutions. Mean runtime is 181.9 seconds versus 156.6 seconds for direct MILP; conflict-cut encoding uses 1–14 auxiliary qubits. A separate IBM-hardware demonstration with three timesteps, two vehicles, and two trips reaches the classical optimum in one Benders iteration. The recursive formulation also permits solving a larger instance whose cumulative formulation exhausts memory. The stated remaining encoding bottleneck is the auxiliary-qubit cost of optimality cuts. The hardware demonstration is explicitly a minimal proof of concept; the larger benchmarks do not establish a quantum runtime advantage.