Hybrid Quantum-Classical Branch-and-Price for Intra-Day Electric Vehicle Charging Scheduling via Partition Coloring
Peng Sun, Liang Zhong, Qing-Guo Zeng, Li Wang · 2026
Read Hybrid Quantum-Classical Branch-and-Price for Intra-Day Electric Vehicle Charging Scheduling via Partition Coloring by Peng Sun, Liang Zhong, Qing-Guo Zeng, Li Wang (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2603-21374.txt.
Introduction
Sun and co-authors build a hybrid quantum-classical branch-and-price method for intra-day electric vehicle charging schedules. Tight charger capacity and short dwell times make the scheduling hard. They model it as a partition coloring problem, with conflict graphs for time and resource clashes. The pricing subproblem is a maximum independent set, recast as a QUBO and solved by quantum-annealing-inspired algorithms. On large, hard instances, the hybrid closes optimality gaps that the pure Gurobi baseline leaves open.
Catalog record
| CREATOR | Peng Sun, Liang Zhong, Qing-Guo Zeng, Li Wang |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 46770 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2603.21374
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Hybrid Quantum-Classical Branch-and-Price for Intra-Day Electric Vehicle Charging Scheduling via Partition Coloring Peng Sun, Liang Zhong, Qing-Guo Zeng, Li Wang Abstract 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 is a promising direction for large-scale EV charging scheduling and related PCP applications. 1 Introduction In recent years, the widespread adoption of electric vehicles (EVs) in public parking facilities, workplace charging stations, and large fleet operations has made intra-day charging scheduling an important operational optimization problem. Unlike conventional refueling, EV charging is time-consuming and highly flexible; it is influenced by users’ departure deadlines, power-capacity limitations, and fluctuations in instantaneous charging load. In typical intra-day scenarios, vehicles arrive and depart within the same day and expect to obtain sufficient energy during a limited dwell period to support subsequent trips. Consequently, operators must assign feasible charging intervals to each vehicle under restricted resources while balancing demand satisfaction, charger utilization, and overall system stability. The literature has examined the EV charging scheduling problem from multiple perspectives. For instance, Dolgui et al. [ 9 ] formulated a scheduling model for conventional charging tasks with parallel chargers and explicitly characterized task–resource conflicts, while Wang et al. [ 31 ] developed an integrated framework that jointly models daily mobility patterns and charging activities. In addition, Shen et al. [ 28 ] proposed a two-stage method that coordinates vehicle–charger matching and bidirectional charging strategies under photovoltaic uncertainty. Data-driven and heuristic approaches, including deep learning [ 6 ] , reinforcement learning [ 33 , 15 ] , and genetic algorithms [ 32 ] , have also been widely applied to derive near-optimal charging policies in complex environments. Most existing studies rely on time-indexed integer programming models. By discretizing vehicles’ dwell windows, scheduling decisions are mapped to binary assignments between vehicles and time slots. Although effective for small and medium instances, this modeling approach has inherent limitations. The model size grows rapidly as the temporal resolution increases; conflict relationships among candidate charging intervals, such as temporal overlap, sharing of physical chargers, or local load interactions, are only implicitly represented; and the number of constraints and variables escalates quickly with the number of vehicles and candidate intervals. As a result, conventional MILP formulations face substantial challenges in large-scale, continuous-time, or multi-resource coupled settings. Graph-based formulations offer a natural way to represent conflicts, particularly for capturing the mutual exclusivity of candidate charging intervals. Recent work has shown that the scheduling problem can be reformulated as a vertex coloring problem and solved using the Quantum Approximate Optimization Algorithm (QAOA) [ 12 ] . However, EV scheduling exhibits a specific structural characteristic: each vehicle may have several candidate intervals, but only one can be selected. This “vehicle as partition, interval as vertex, exactly one vertex selected per partition” structure corresponds more closely to the Partition Coloring Problem (PCP). Although the PCP has been studied in combinatorial optimization [ 11 , 39 , 27 ] , it has not been systematically applied to EV charging scheduling. To address this gap, we model the intra-day EV charging scheduling problem as a variant of PCP. Each vehicle is treated as a partition, and its candidate charging intervals constitute the vertices within that partition. For example, if a vehicle has three candidate intervals A1, A2, and A3, they form one partition in the graph. Edges connect vertices whose intervals overlap or share conflicting physical or electrical resources. Given a limited number of chargers C , the goal is to select a maximum independent set that minimizes the latest completion time while selecting exactly one interval per vehicle and satisfying resource constraints. Based on this modeling framework, our main contributions are as follows: 1. We provide the first systematic formulation of the intra-day EV charging scheduling problem as a PCP, enabling explicit representation of vehicle-level and interval-level conflicts while naturally supporting multiple resource constraints. 2. We develop a Branch-and-Price algorithm in which the master problem handles partition selection and resource allocation, and the pricing subproblem generates new columns via a maximum independent set structure, thereby improving computational efficiency. 3. We integrate a quantum annealing-inspired algorithm (QAIA) solver implemented in the MindSpore Quantum framework to accelerate the pricing subproblem and enhance scalability for large problem instances. Finally, we conduct extensive numerical experiments comparing the proposed QAIA-enhanced branch-and-price algorithms with a pure Gurobi-based baseline on synthetic EV charging instances of varying sizes, demonstrating that the QAIA-based methods significantly improve performance on large and hard cases while preserving optimal solution quality. The remainder of this paper is organized as follows. Section 2 reviews the literature on EV charging scheduling and related optimization approaches. Section 3 describes the problem. Section 4 presents the formal mathematical formulation. Section 5 reports the computational experiments and compares a pure Gurobi-based branch-and-price baseline with two QAIA-based pricing variants (BSB and SimCIM) on a family of PCP instances derived from EV charging scenarios. Finally, Section 6 concludes the paper and outlines potential directions for future research. 2 Related Works 2.1 Electric Vehicle Charging Scheduling EVs have been increasingly adopted in logistics and urban delivery systems. Their limited driving range and charging requirements make joint fleet scheduling and charging optimization a critical research topic in transportation and operations research. Existing studies mainly focus on routing and charging modeling, solution algorithms, and intelligent scheduling frameworks. Routing problems with partial charging and realistic operational constraints have been extensively studied. Extensions of the electric vehicle routing problem incorporate parcel lockers, heterogeneous fleets, multiple depots, repeated customer visits, and partial recharging strategies, and are typically addressed using advanced metaheuristics such as ALNS, VNS, and VND [ 36 , 2 ] . The impact of different charging models on battery degradation, travel time, and fleet size has also been analyzed, together with a systematic discussion of algorithmic applicability and modeling trade-offs [ 5 , 34 ] . To cope with large-scale and dynamic environments, various intelligent and approximate solution methods have been proposed. Hybrid heuristic frameworks combine swarm intelligence with dynamic programming for personalized charging route planning [ 29 ]