Hybrid Quantum-Classical Branch-and-Price for Intra-Day Electric Vehicle Charging Scheduling via Partition Coloring
This addresses the problem of efficient EV charging scheduling for fleet operators and parking facilities, representing an incremental improvement by integrating quantum-inspired methods into classical optimization frameworks.
The paper tackles intra-day electric vehicle charging scheduling by modeling it as a Partition Coloring Problem and developing a branch-and-price algorithm where the pricing subproblem is solved using quantum-annealing-inspired algorithms (QAIA). The results show that QAIA-enhanced algorithms match or outperform a pure Gurobi baseline, particularly on large instances where they close optimality gaps and prove optimality within time limits.
The rapid deployment of electric vehicles (EVs) in public parking facilities and fleet operations raises challenging intra-day charging scheduling problems under tight charger capacity and limited dwell times. We model this problem as a variant of the Partition Coloring Problem (PCP), where each vehicle defines a partition, its candidate charging intervals are vertices, and temporal and resource conflicts are represented as edges in a conflict graph. On this basis, we design a branch-and-price algorithm in which the restricted master problem selects feasible combinations of intervals, and the pricing subproblem is a maximum independent set problem. The latter is reformulated as a quadratic unconstrained binary optimization (QUBO) model and solved by quantum-annealing-inspired algorithms (QAIA) implemented in the MindQuantum framework, specifically the ballistic simulated branching (BSB) and simulated coherent Ising machine (SimCIM) methods, while the master problem is solved by Gurobi. Computational experiments on a family of synthetic EV charging instances show that the QAIA-enhanced algorithms match the pure Gurobi-based branch-and-price baseline on small and medium instances, and clearly outperform it on large and hard instances. In several cases where the baseline reaches the time limit with non-zero optimality gaps, the QAIA-based variants close the gap and prove optimality within the same time budget. These results indicate that integrating QAIA into classical decomposition schemes are a promising direction for large-scale EV charging scheduling and related PCP applications.