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.
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.
We suggest a hybrid quantum-classical routine for the NP-hard Electric Vehicle Fleet Charging and Allocation Problem. The original formulation is a Mixed Integer Linear Program with continuous variables and inequality constraints. To separate inequality constraints that are difficult for quantum routines we use a decomposition in master and pricing problems: the former targets the assignment of vehicles to reservations and the latter suggests vehicle exploitation plans that respect the battery state-of-charge constraints. The master problem is equivalent to the search for an optimal set partition. In our hybrid scheme, the master problem is reformulated in a quadratic unconstrained binary optimization problem which can be solved with quantum annealing on the DWave Advantage system. On large instances, we benchmark the performance of the decomposition technique with classical and quantum-inspired metaheuristics: simulated annealing, tabu search, and vector annealing by NEC. The numerical results with purely classical solvers are comparable to the solutions from the traditional mixed integer linear programming approaches in terms of solution quality while being faster. In addition, it scales better to larger instances. The major advantage of the proposed approach is that it enables quantum-based methods for this realistic problem with many inequality constraints. We show this by initial studies on DWave hardware where optimal solutions can be found for small instances.
Motivated by recent progress in quantum hardware and algorithms, researchers have developed quantum heuristics for optimization problems, aiming for advantages over classical methods. To date, quantum hardware is still error-prone and limited in size such that quantum heuristics cannot be scaled to relevant problem sizes and are often outperformed by their classical counterparts. Moreover, if provably optimal solutions are desired, one has to resort to classical exact methods. As, however, quantum technologies may improve considerably in future, we demonstrate in this work how quantum heuristics with limited resources can be integrated in large-scale exact optimization algorithms for NP-hard problems. To this end, we consider vehicle routing as a prototypical NP-hard problem. We model the pricing and separation subproblems arising in a branch-price-and-cut algorithm as quadratic unconstrained binary optimization problems. This allows to use established quantum heuristics like quantum annealing or the quantum approximate optimization algorithm for their solution. A key feature of our algorithm is that it profits not only from the best solution returned by the quantum heuristic but from all solutions below a certain cost threshold, thereby exploiting the inherent randomness is quantum algorithms. Moreover, we reduce the requirements on quantum hardware since the subproblems, which are solved via quantum heuristics, are smaller than the original problem. We provide a proof-of-concept experimental study comparing quantum annealing to simulated annealing and to established classical algorithms in our framework. While our hybrid quantum-classical approach is still outperformed by purely classical methods, our results reveal that both pricing and separation may be well suited for quantum heuristics if quantum hardware improves.
• We propose a new hybrid quantum-classical algorithm for solving the UC problem. • The hybrid model successfully optimizes 24-hour UC systems from 10 to 1000 units. • The model outperforms classical metaheuristics (GA and SA) and classical MINLP. • This represents an improvement over previous QCUC methods, a step to real-world use. Resource scheduling is critical in many industries, especially in power systems where the Unit Commitment (UC) problem determines the on/off status and output levels of generators under physical and economic constraints. Traditional exact methods, such as Branch‑and‑Bound, Branch‑and‑Cut, dynamic programming and mixed‑integer linear programming (MILP), remain the backbone of UC solution techniques, but they often rely on linear approximations or exhaustive search, leading to high computational burdens as system size grows. Metaheuristic approaches, such as genetic algorithms, particle swarm optimization, and other evolutionary methods, have been explored to mitigate this complexity; however, they typically lack optimality guarantees, exhibit sensitivity to initial conditions, and can become prohibitively time‑consuming for large‑scale systems. In this paper, we introduce a quantum‑classical hybrid algorithm for UC, and other resource scheduling problems by extension, that leverages Benders decomposition to decouple binary commitment decisions from continuous economic dispatch. The binary “master problem” is formulated as a quadratic unconstrained binary optimization (QUBO) model and solved on a quantum annealer. The continuous “subproblem,” which minimizes generation costs, with Lagrangian cuts feeding back to the master until convergence. We evaluate our hybrid framework on systems scaled from 10 to 1,000 generation units. Compared against a classical mixed‑integer nonlinear programming (MINLP) baseline, the hybrid algorithm achieves a consistently lower computation‑time growth rate and maintains an absolute optimality gap below 1.63%. These results demonstrate that integrating quantum annealing within a hybrid quantum-classical Benders decomposition loop can significantly accelerate large‑scale resource scheduling without sacrificing solution quality, pointing toward a viable path for addressing the escalating complexity of modern power grids.
Quantum algorithms have shown promise in solving Quadratic Unconstrained Binary Optimization (QUBO) problems, benefiting from their connection to the transverse field Ising model.Various Ising solvers, both classical and quantum, have emerged to tackle such problems efficiently but lack global optimality guarantees and oftentimes sufer from hardware limitations such as limited qubit availability.In this work, we propose a hybrid branch-andbound (B&B) framework that integrates Ising solvers as heuristics within a classical B&B algorithm.Unlike prior theoretical studies, our work presents a practical implementation, available as open-source at GitHub.We explore when and where to apply Ising solvers in the search tree, and introduce a custom branching rule optimized QUBO embedding.Our method is evaluated on hundreds of QUBO instances from QUBOLib.jl using Gurobi and the D-Wave quantum annealer.Our Results show up to 11% less solution time and 17% fewer nodes compared to default Gurobi, an off-the-shelf commercial optimization solver.These findings demonstrate the value of hybrid quantum-classical strategies for enhancing exact optimization.
Optimal routing problems of electric vehicles (EVs) have attracted much attention in recent years, and installation of charging stations is an important issue for EVs. Hence, we focus on the joint optimization of the location of charging stations and the routing of EVs. When routing problems are formulated in the form of quadratic unconstrained binary optimization (QUBO), specialized solvers such as quantum annealers are expected to provide optimal solutions with high speed and accuracy. However, battery capacity constraints make it hard to formulate into QUBO form without a large number of auxiliary qubits. Here, we propose a sequential optimization method utilizing the Bayesian inference and QUBO solvers, in which the battery capacity constraints are automatically learned. This method enables us to optimize the number and location of charging stations and the routing of EVs with a small number of searches. Applying this method to a routing problem of 20 locations, we observed consistent convergence toward battery-feasible solutions across independent runs, demonstrating stable learning behavior of the proposed framework. Small-scale validation experiments using exhaustive enumeration show that the framework reliably discovers feasible configurations close to the global optimum, while runtime and QUBO-size analyses clarify its computational characteristics.
Variational quantum algorithms have attracted attention for their potential to solve combinatorial optimization problems. We study how the choice of encoding affects the resource requirements and optimization behavior of a variational quantum optimization algorithm. In order to quantify these effects, realistically inspired constrained electric vehicle (EV) fleet management problems were considered. These problems couple determining the optimal EV battery charging schedule with assigning EVs to trips requested by customers. We compare a conventional binary (qubit) trip encoding with an integer (qudit) encoding that represents assignments more directly. Both encodings guarantee the same feasible solution set, while the qudit encoding exponentially reduces the required Hilbert-space dimension. We solve many random instances of highly constrained uni- and bi-directional charging problems using qudit-based quantum approximate optimization algorithm (QAOA) and thoroughly evaluate the performance results. We find that the qudit encoding of customer trips achieves similar or better optimization performance at much reduced resource requirements and shorter simulation runtime. These results highlight qudit-native encodings as a practical route for integer and multi-valued scheduling problems in variational quantum optimization.