🔢 mathematics

Hybrid Quantum-Classical Branch-and-Price for Intra-Day Electric Vehicle Charging Scheduling via Partition Coloring

This paper proposes a hybrid quantum-classical branch-and-price algorithm that integrates quantum-annealing-inspired solvers for the pricing subproblem to efficiently address large-scale intra-day electric vehicle charging scheduling modeled as a Partition Coloring Problem, demonstrating superior performance over classical baselines on difficult instances.

Original authors: Peng Sun, Liang Zhong, Qing-Guo Zeng, Li Wang

Published 2026-03-24

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Peng Sun, Liang Zhong, Qing-Guo Zeng, Li Wang

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are the manager of a busy electric vehicle (EV) charging station. You have a fleet of cars arriving and leaving throughout the day, but you only have a limited number of charging plugs (let's say 10). Each car needs to charge for a specific amount of time, but they can't all plug in at once because there aren't enough sockets.

Your goal is simple: Get every car charged and ready to go as quickly as possible without anyone fighting over the same plug.

This sounds easy, but it's actually a massive mathematical puzzle. If you have 100 cars and each car has 10 different possible times it could charge, the number of ways you could arrange the schedule is astronomical. Trying to find the perfect schedule using a standard computer is like trying to find a specific needle in a haystack that keeps growing bigger every second.

Here is how the authors of this paper solved that puzzle, explained in everyday terms.

1. The Problem: The "Traffic Jam" of Time

Think of every car as a person trying to get into a party, but the party has a strict rule: Only one person from each family can enter at a time.

The Families: These are the cars.
The Entry Times: Each car has a list of possible times it could arrive (e.g., 9:00 AM, 10:00 AM, or 11:00 AM).
The Conflict: If Car A arrives at 9:00 AM and Car B arrives at 9:00 AM, they can't both use the same plug. Also, Car A can't be in two places at once (it can't charge at 9:00 AM and 10:00 AM).

The computer's job is to pick exactly one "entry time" for every car so that no two cars clash, and the whole party finishes as early as possible.

2. The Old Way: The "Super-Brain" Computer

Traditionally, researchers used powerful computers (like the one made by Gurobi) to solve this. They would try to calculate every possible combination.

Small Parties: If there are only 10 cars, the computer solves it in a blink.
Huge Parties: If there are 100 cars, the computer gets overwhelmed. It starts calculating, calculating, and calculating, but after an hour (the time limit), it still hasn't found the perfect answer. It gives up with a "good enough" answer that might leave some cars waiting too long.

3. The New Idea: The "Hybrid Team"

The authors realized that instead of asking the computer to do everything, they should split the work. They created a Hybrid Quantum-Classical Team.

Think of it like a construction site:

The General Manager (The Classical Computer/Gurobi): This is the boss. It looks at the big picture, decides which cars are currently scheduled, and checks if the rules are being followed. It's very good at organization but slow at finding new, creative ideas.
The Creative Scout (The Quantum-Inspired Algorithm): This is the new helper. Its only job is to look for a better schedule for a small group of cars. It uses "Quantum Annealing" techniques (specifically BSB and SimCIM).

What is Quantum Annealing?
Imagine you are in a dark, foggy valley with a ball. You want to get the ball to the very bottom of the valley (the best solution).

A normal computer rolls the ball down slowly, step-by-step. It might get stuck in a small dip (a local trap) and think it's at the bottom.
A Quantum-inspired algorithm is like giving the ball a little "quantum jump." It can tunnel through small hills or shake the ground to help the ball escape those small dips and find the true bottom of the valley much faster.

4. How They Work Together (The "Branch-and-Price" Dance)

The paper describes a specific dance called Branch-and-Price:

The Manager (Gurobi) sets up a tentative schedule.
The Scout (Quantum Algorithm) is asked: "Hey, can you find a better way to schedule just these specific cars?"
The Scout uses its "quantum jumps" to quickly find a better arrangement that the Manager missed.
The Manager takes this new idea, updates the schedule, and checks if it's valid.
They repeat this until the schedule is perfect.

5. The Results: Why It Matters

The researchers tested this on fake scenarios ranging from small groups to massive fleets of 100 cars.

Small Groups: The new team worked just as fast as the old computer. No magic needed yet.
Big Groups (The Real Test): This is where the magic happened.
- The Old Computer got stuck. It ran for an hour, gave up, and said, "I'm 40% sure this is the best I can do."
- The Hybrid Team found the perfect solution in half the time. They didn't get stuck in the "dips" of the valley.

The Takeaway

This paper proves that we don't need to wait for perfect, futuristic quantum computers to solve hard problems. By mixing a little bit of "quantum thinking" (simulated on regular computers) with traditional math, we can solve massive scheduling problems—like getting hundreds of electric cars charged efficiently—that were previously too difficult for standard computers to handle.

It's like upgrading a bicycle with a small electric motor: you don't need a rocket ship to go faster; you just need a smart boost at the right moments.

1. Problem Definition

The paper addresses the Intra-Day Electric Vehicle (EV) Charging Scheduling Problem. This operational challenge involves assigning charging intervals to a fleet of EVs within a single day under strict constraints:

Limited Resources: A fixed number of physical chargers ( $C$ ) are available.
Time Windows: Each vehicle has a specific arrival time, departure deadline, and energy requirement.
Flexibility: Vehicles can be charged during multiple candidate intervals within their dwell time, but exactly one interval must be selected per vehicle.
Conflicts: Conflicts arise from two sources:
1. Temporal/Resource Overlap: Two intervals cannot be scheduled simultaneously if they exceed the charger capacity.
2. Vehicle Exclusivity: Only one interval can be chosen for a specific vehicle.

The authors model this as a variant of the Partition Coloring Problem (PCP). In this graph formulation:

Partitions: Each vehicle represents a partition.
Vertices: Candidate charging intervals for a vehicle are vertices within that partition.
Edges: Edges connect vertices that conflict (either because they belong to the same vehicle or because their time windows overlap).
Objective: Select exactly one vertex per partition such that the selected vertices form an independent set (no conflicts) and the number of chargers used (or makespan) is minimized.

2. Methodology

The authors propose a Hybrid Quantum-Classical Branch-and-Price (B&P) algorithm. The framework decomposes the problem into a Master Problem and a Pricing Subproblem, leveraging classical solvers for the former and quantum-inspired algorithms for the latter.

A. Branch-and-Price Framework

Restricted Master Problem (RMP):
- Formulated as a Linear Programming (LP) relaxation.
- Selects feasible combinations of intervals (columns) to minimize the objective (e.g., makespan).
- Solved using the classical commercial solver Gurobi.
- Generates dual variables to guide the search for new columns.
Pricing Subproblem:
- The goal is to find a column (a feasible independent set of intervals) with a negative reduced cost to add to the RMP.
- Mathematically, this is a Maximum Weight Independent Set (MWIS) problem with partition constraints.
- Classical Approach: Solved directly by Gurobi (used as the baseline).
- Hybrid Approach: Reformulated as a Quadratic Unconstrained Binary Optimization (QUBO) model.
  - The objective function maximizes the weight of selected vertices.
  - Constraints (partition selection and conflict avoidance) are encoded as quadratic penalty terms in the Hamiltonian.
  - Solver: The QUBO is solved using Quantum-Annealing-Inspired Algorithms (QAIA) implemented in the MindQuantum framework. Specifically, two algorithms are tested:
    - Ballistic Simulated Branching (BSB): Uses inelastic boundary constraints to suppress analog errors.
    - Simulated Coherent Ising Machine (SimCIM): Emulates the dynamics of a coherent Ising machine on continuous spin variables.
Branching Scheme:
- To ensure integrality, a custom branching strategy is applied when the RMP solution is fractional.
- Subset-based Branching: Forces a specific interval for a vehicle or forbids it.
- Pairwise Branching: Enforces that two conflicting intervals from different vehicles are either selected together (merged into a super-vertex) or separated (edge added to conflict graph).

3. Key Contributions

Novel Formulation: This is the first systematic formulation of intra-day EV charging scheduling as a Partition Coloring Problem (PCP). This approach explicitly handles the "one-interval-per-vehicle" constraint and complex resource conflicts more naturally than traditional time-indexed Mixed-Integer Linear Programming (MILP) models.
Hybrid Algorithm Design: The paper introduces a Branch-and-Price algorithm where the computationally expensive pricing subproblem is offloaded to quantum-inspired solvers (BSB and SimCIM), while the master problem remains on a classical solver.
Scalability via QAIA: By integrating MindQuantum's QAIA solvers, the framework demonstrates the ability to solve large-scale, hard combinatorial instances that are intractable for pure classical decomposition methods within reasonable time limits.

4. Computational Results

The authors conducted extensive experiments on synthetic instances ranging from small ( $V=10$ ) to large ( $V=100$ ) numbers of vehicles, with varying charger capacities.

Small and Medium Instances ( $V \le 40$ ):
- The QAIA-enhanced methods (BSB and SimCIM) performed comparably to the pure Gurobi baseline.
- All methods achieved zero optimality gaps and solved instances in sub-second to tens-of-seconds ranges.
Large and Hard Instances ( $V \ge 80$ ):
- Pure Gurobi Baseline: Struggled significantly. For the largest instances ( $V=100$ ), it frequently hit the 3600-second time limit with non-zero optimality gaps (up to 40%), failing to prove optimality.
- QAIA Variants (BSB/SimCIM): Consistently outperformed the baseline.
  - They closed the optimality gaps to 0% within the same time budget.
  - They achieved significantly lower total runtimes (e.g., solving a $V=100$ instance in ~900s vs. 3600s for Gurobi).
  - They generated high-quality columns more efficiently, allowing the branch-and-price tree to be explored with fewer nodes.
Comparison of QAIA: Both BSB and SimCIM showed robust performance, with BSB often slightly faster on the largest instances, though both were effective.

5. Significance and Conclusion

The paper demonstrates that integrating Quantum-Annealing-Inspired Algorithms (QAIA) into classical decomposition schemes is a highly promising direction for solving large-scale combinatorial optimization problems.

Practical Impact: The proposed method offers a viable solution for real-world, large-scale EV fleet management where charging capacity is tight and scheduling complexity is high.
Theoretical Insight: It validates the PCP formulation for EV scheduling and proves that hybrid quantum-classical approaches can overcome the scalability limitations of pure classical solvers (like Gurobi) in the context of column generation.
Future Work: The authors suggest extending the framework to include richer network constraints, data-driven instance generation, and the integration of other variational quantum algorithms.

In summary, the study successfully bridges the gap between theoretical quantum-inspired optimization and practical industrial scheduling, showing that hybrid solvers can deliver provably optimal solutions for problems that are currently intractable for state-of-the-art classical solvers.