Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2611.15343

Hybrid Classical-Quantum Optimization for CVRPTW: A Systems Framework with Provable Feasibility and Empirical Hardware Limits

Syamasundar Gopasana, Swatantra Singh, Rohan Joydhar, Shubhashis Sengupta

Published Nov 11, 2026• 0 citations
arXivHTMLPDF

Abstract

Solving large-scale Capacitated Vehicle Routing Problems with Time Windows (CVRPTW) remains challenging because strict operational constraints and scale limit both exact and heuristic methods. We present a hybrid classical-quantum architecture combining Mixed Integer Linear Programming (MILP) with vehicle-level Quadratic Unconstrained Binary Optimization (QUBO), solved using Toshiba SQBM+ and QAOA on Rigetti Ankaa-3 and IQM Emerald quantum processors. The decomposition avoids the variable growth and constraint-enforcement difficulties of monolithic CVRPTW QUBO formulations. We evaluate the framework on five realistic benchmarks derived from London traffic and location data, spanning 10--70 customers, using a validation pipeline enforcing feasibility and monotone improvement over classical baselines. SQBM+ achieves verified fleet-distance reductions of 2.80% (7,927 m) for the 25-customer instance and 0.22% (1,186 m) for the 55-customer instance. QAOA experiments establish a current hardware boundary for reliable constraint satisfaction at subproblems of up to 4 customers (16 qubits). Diagnostic results identify assignment-level time-window tightness, rather than local route optimization, as the dominant scalability bottleneck. The results demonstrate a practical near-term role for hybrid classical-quantum optimization while establishing empirical limits for current quantum hardware.

DOI
10.48550/arxiv.2611.15343

Related papers

Quantum-Classical Hybrid Cloud Workflows for Combinatorial Supply-Chain and Fleet Optimization

Sonu Kumar Singh

Abstract: Global logistics networks, intercontinental air-freight consolidators, and maritime energy fleets continuously solve large-scale Mixed-Integer Linear Programs (MILPs) such as the Capacitated Vehicle Routing Problem with Time Windows (CVRPTW) and multi-vessel Maritime Inventory Routing Problems (MIRP). When weather disruptions, port congestion, or geopolitical airspace closures invalidate baseline schedules, classical branch-and-cut solvers (Gurobi, CPLEX) experience exponential worst-case tree growth on subproblems exceeding 2,000 binary decision variables, often failing to converge within strict 5-to-15-minute operational re-dispatch windows. Conversely, current Noisy Intermediate-Scale Quantum (NISQ) processors remain limited to 100-to-1,000 physical qubits with finite two-qubit gate fidelity ($99.2\%-99.8\%$), preventing direct encoding of full enterprise logistics instances. This paper presents a production-grade Quantum-Classical Hybrid Cloud Architecture that bridges enterprise Kubernetes clusters with co-located quantum processing units (QPUs) via AWS Braket Hybrid Jobs and IBM Quantum Qiskit Runtime primitives. Our framework applies Benders and Dantzig-Wolfe column generation on classical cloud HPC nodes to decompose a 25,000-variable global fleet MILP into a continuous master problem and hard combinatorial pricing/routing subproblems of 60 to 140 binary variables. These subproblems are transformed into Quadratic Unconstrained Binary Optimization (QUBO) and Ising Hamiltonians, warm-started from classical linear programming (LP) relaxations (WS-QAOA), compiled with dynamical decoupling and Zero-Noise Extrapolation (ZNE), and executed inside co-located QPU-CPU sessions while a GPU-accelerated Simulated Bifurcation (SB) digital annealer runs in parallel as a deterministic SLA fallback. Evaluated on disruption recovery workloads modeled on ExxonMobil maritime LNG routing and DHL Global Forwarding air-cargo container loading, our hybrid WS-QAOA + Column Generation workflow improves optimality gap closure at a 10-minute SLA cutoff from 6.84% (classical branch-and-bound alone) to 1.42%, reduces emergency re-routing compute wall-clock time by 61.5%, and cuts fleet fuel and charter penalty costs by 4.7%. Research Domain & Specialization Track Master of Science in Information Technology (MSIT) — Quantum Cloud Computing, Hybrid Orchestration, and Operations Research. Core Technical Highlights Empirical Production Case Studies: Rigorous architectural blueprints and telemetry evaluation across enterprise cloud deployments. Four-Tier Reference Architecture: Formal specification from edge ingress to distributed hardware execution pools. Mathematical Formulation: Formally derived algorithmic and optimization models with closed-loop verification. Multi-Modal Benchmarking: Comparative empirical baselines under fault-injection and synthetic workload scaling. Author Information Author: Sonu Kumar SinghRole: Senior Consultant Affiliation: Independent Researcher Publication Status: Preprint / Working Paper (MSIT AI & Cloud Systems Research Series) Reproducibility & Open Science All included architecture diagrams, telemetry schemas, and benchmark curves are open-access under the Creative Commons Attribution 4.0 International (CC BY 4.0) license.

•Oct 20, 2026•0 citations

Solving Real-World Optimization Problems using Near-Term Quantum Computing with Applications in Vehicle Routing and Drone Delivery

Holliday, James Bradley

Quantum computing (QC) stands at the cusp of revolutionizing computation, yet its near-term potential, constrained by Noisy Intermediate-Scale Quantum (NISQ) devices, remains underexplored. This dissertation investigates how hybrid quantum-classical algorithms can address combinatorial optimization challenges in logistics, focusing on vehicle routing and drone delivery—NP-hard problems with exponential solution spaces that defy classical exhaustive methods. Amidst NISQ limitations like limited qubits and high noise, we confront key challenges: encoding complex constraints, e.g., time windows, battery capacity, into quantum models, balancing quantum and classical components for scalability, and accessing scarce quantum resources. By integrating quantum annealing (QA) and the Quantum Approximate Optimization Algorithm (QAOA) with classical heuristics, this work demonstrates QC’s practical utility, advancing both optimization theory and real-world logistics applications. The dissertation unfolds across four core contributions. First, the Hybrid Quantum Tabu Search (HQTS) optimally solves the 50-location Capacitated Vehicle Routing Problem (CVRP), achieving a 4.72% optimality gap. Secondly, we refine HQTS to reach a 2.15% gap with enhanced QA utilization, outperforming prior hybrids on standard datasets. Third, adapting HQTS for the CVRPTWwith D-Wave’s Constrained Quadratic Model solver yields a 3.85% gap on 100-location instances, leveraging a novel heuristic to ensure time-window feasibility where quantum outputs falter. Lastly, QUADRO, a pioneering framework for drone delivery, employs QAOA-driven routing and hybrid scheduling, minimizing transit time and makespan for fleets of 2–11 drones needing fewer than 100 qubits, rivaling classical benchmarks on adapted Augerat datasets. These advances, tested via D-Wave’s Advantage system and Qiskit simulations, showcase hybrid strategies that mitigate NISQ constraints, delivering scalable, feasible solutions to logistics challenges. This work establishes near-term QC’s viability for combinatorial optimization, bridging theoretical promise with practical impact. Synthesizing quantum exploration with classical refinement achieves competitive performance, e.g., matching or surpassing Google ORTools in select CVRPTW cases, while illuminating NISQ limits, such as feasibility degradation beyond small scales. These hybrid strategies deliver scalable, feasible solutions, from a 2.15% optimality gap for CVRP to effective drone fleet management with fewer than 100 qubits, illuminating quantum computing’s potential despite its current constraints. Ultimately, this dissertation positions hybrid QC as a transformative tool for optimization challenges, offering a robust foundation for scaling quantum optimization into operational reality.

Journal of the Arkansas Academy of Science•May 1, 2025•0 citations

Solving the Capacitated Vehicle Routing Problem Using the Quantum Approximate Optimization Algorithm: A Benchmark Against Classical Guided Local Search

Ninad Hirani

The Capacitated Vehicle Routing Problem (CVRP) is a combinatorial optimization problem that can be formulated as a Quadratic Unconstrained Binary Optimization (QUBO) problem, making it a potential application for near-term quantum optimization. This paper benchmarks the Quantum Approximate Optimization Algorithm (QAOA, p = 2) against Google OR-Tools Guided Local Search on a seeded instance with three customers and two vehicles. The study examines the QUBO formulation, energy spectrum, optimization behavior, penalty weights, Hamiltonian scaling, and circuit depths. The experiments show that the tested QAOA configurations do not reliably concentrate probability on optimal solutions. The classical solver identifies the optimal solution for the selected instance. The study provides a reproducible baseline and discusses limitations and future research directions. The findings are limited to the tested instance, formulation, and optimization configurations.

•Oct 15, 2026•0 citations

Hybrid quantum-classical end-to-end pipeline for solving MILPs: a vehicle routing case study

Camille de Valk, Koen Reerink, Siert Sebus +1 more

We demonstrate an end-to-end hybrid quantum-classical optimisation framework based on Benders decomposition, capable of solving mixed-integer linear programming (MILP) problems. The framework builds on a previously presented hybrid quantum-classical end-to-end pipeline based on Multiple Cuts via Multiple Solutions (MCMS) Benders decomposition where the cut selection step was performed on quantum annealing hardware. We extend this with gate-based QAOA implementations for both tensor network emulators and superconducting quantum hardware. The Vehicle Routing Problem (VRP) is used as a representative case study and we run the pipeline end-to-end on 10 permutations of a standardised benchmarking instance (20 customers and 4 vehicles from QOptLib) with a classical solver performing the cut selection step. We find that for our instances, only a small fraction of the compute in classical MCMS Benders decomposition is spent on the cut selection step. For a full hybrid end-to-end assessment, we run the pipeline for a toy problem with MPS-JuliQAOA, a powerful tensor network emulator, to execute QAOA. Here, the majority of the time is spent on the cut selection step, deeming quantum advantage of this framework unlikely at problems of this size. This highlights the need for more large-scale benchmarking research when more powerful (QPU) QUBO solvers are available.

quant-pharXiv:2607.26771•Jul 30, 2026•1 citation

Hybrid Optimization QAOA for Scalable Vehicle Scheduling Problems

Jakub Kołota

Optimization of vehicle-to-station assignments under capacity and distance constraints represents a challenging combinatorial problem relevant to automated planning, logistics, and autonomous mobility systems. Classical methods such as Mixed Integer Linear Programming (MILP) or metaheuristics often struggle to scale efficiently with problem dimensionality, motivating the exploration of hybrid quantum-classical paradigms. This paper presents a normalized Quantum Approximate Optimization Algorithm (QAOA) framework tailored for constrained assignment problems, where vehicle-station distances are encoded into a normalized cost Hamiltonian. Capacity violations and unused resources are incorporated through dynamically scaled penalty terms, producing a cost landscape that effectively guides the quantum search process. The proposed pipeline integrates parameter optimization using COBYLA to refine the QAOA angles, ensuring convergence toward low-cost feasible configurations. Experimental simulations in Cirq on a 10-qubit system demonstrate that the normalized QAOA pipeline consistently identifies near-optimal assignments while substantially reducing the combinatorial search space. These results provide empirical evidence for the viability of hybrid QAOA formulations in real-world planning and scheduling scenarios, establishing a foundation for future implementations on noisy intermediatescale quantum (NISQ) hardware.

International Conference on Smart Applications, Communications and Networking (SmartNets)•Jul 7, 2026•0 citations

Solving Capacitated Vehicle Routing Problem with Quantum Alternating Operator Ansatz and Column Generation

Wei‐Hao Huang, Hiromichi Matsuyama, Yu Yamashiro

This study proposes a hybrid quantum-classical approach to solving the Capacitated Vehicle Routing Problem (CVRP) by integrating the Column Generation (CG) method with the Quantum Alternating Operator Ansatz (QAOAnsatz). The CG method divides the CVRP into the reduced master problem, which finds the best combination of the routes under the route set, and one or more subproblems, which generate the routes that would be beneficial to add to the route set. This method is iteratively refined by adding new routes identified via subproblems and continues until no improving route can be found. We leverage the QAOAnsatz to solve the subproblems. Our algorithm restricts the search space by designing the QAOAnsatz mixer Hamiltonian to enforce one-hot constraints. Moreover, to handle capacity constraints in QAOAnsatz, we employ an Augmented Lagrangian-inspired method that obviates the need for additional slack variables, reducing the required number of qubits. Experimental results on small-scale CVRP instances (up to 6 customers) show that QAOAnsatz converges more quickly to optimal routes than the standard QAOA approach, demonstrating the potential of this hybrid framework in tackling realworld logistical optimization problems on near-term quantum hardware.

arXiv:2503.17051•International Conference on Quantum Communications, Networking, and Computing (QCNC)•Apr 6, 2026•7 citations
Solving large-scale Capacitated Vehicle Routing Problems with Time Windows (CVRPTW) remains challenging because strict operational constraints and scale limit both exact and heuristic methods. We present a hybrid classical-quantum architecture combining Mixed Integer Linear Programming (MILP) with vehicle-level Quadratic Unconstrained Binary Optimization (QUBO), solved using Toshiba SQBM+ and QAOA on Rigetti Ankaa-3 and IQM Emerald quantum processors. The decomposition avoids the variable growth and constraint-enforcement difficulties of monolithic CVRPTW QUBO formulations. We evaluate the framework on five realistic benchmarks derived from London traffic and location data, spanning 10--70 customers, using a validation pipeline enforcing feasibility and monotone improvement over classical baselines. SQBM+ achieves verified fleet-distance reductions of 2.80% (7,927 m) for the 25-customer instance and 0.22% (1,186 m) for the 55-customer instance. QAOA experiments establish a current hardware boundary for reliable constraint satisfaction at subproblems of up to 4 customers (16 qubits). Diagnostic results identify assignment-level time-window tightness, rather than local route optimization, as the dominant scalability bottleneck. The results demonstrate a practical near-term role for hybrid classical-quantum optimization while establishing empirical limits for current quantum hardware.
Abstract: Global logistics networks, intercontinental air-freight consolidators, and maritime energy fleets continuously solve large-scale Mixed-Integer Linear Programs (MILPs) such as the Capacitated Vehicle Routing Problem with Time Windows (CVRPTW) and multi-vessel Maritime Inventory Routing Problems (MIRP). When weather disruptions, port congestion, or geopolitical airspace closures invalidate baseline schedules, classical branch-and-cut solvers (Gurobi, CPLEX) experience exponential worst-case tree growth on subproblems exceeding 2,000 binary decision variables, often failing to converge within strict 5-to-15-minute operational re-dispatch windows. Conversely, current Noisy Intermediate-Scale Quantum (NISQ) processors remain limited to 100-to-1,000 physical qubits with finite two-qubit gate fidelity (99.2%−99.8%99.2\%-99.8\%99.2%−99.8%), preventing direct encoding of full enterprise logistics instances. This paper presents a production-grade Quantum-Classical Hybrid Cloud Architecture that bridges enterprise Kubernetes clusters with co-located quantum processing units (QPUs) via AWS Braket Hybrid Jobs and IBM Quantum Qiskit Runtime primitives. Our framework applies Benders and Dantzig-Wolfe column generation on classical cloud HPC nodes to decompose a 25,000-variable global fleet MILP into a continuous master problem and hard combinatorial pricing/routing subproblems of 60 to 140 binary variables. These subproblems are transformed into Quadratic Unconstrained Binary Optimization (QUBO) and Ising Hamiltonians, warm-started from classical linear programming (LP) relaxations (WS-QAOA), compiled with dynamical decoupling and Zero-Noise Extrapolation (ZNE), and executed inside co-located QPU-CPU sessions while a GPU-accelerated Simulated Bifurcation (SB) digital annealer runs in parallel as a deterministic SLA fallback. Evaluated on disruption recovery workloads modeled on ExxonMobil maritime LNG routing and DHL Global Forwarding air-cargo container loading, our hybrid WS-QAOA + Column Generation workflow improves optimality gap closure at a 10-minute SLA cutoff from 6.84% (classical branch-and-bound alone) to 1.42%, reduces emergency re-routing compute wall-clock time by 61.5%, and cuts fleet fuel and charter penalty costs by 4.7%. Research Domain & Specialization Track Master of Science in Information Technology (MSIT) — Quantum Cloud Computing, Hybrid Orchestration, and Operations Research. Core Technical Highlights Empirical Production Case Studies: Rigorous architectural blueprints and telemetry evaluation across enterprise cloud deployments. Four-Tier Reference Architecture: Formal specification from edge ingress to distributed hardware execution pools. Mathematical Formulation: Formally derived algorithmic and optimization models with closed-loop verification. Multi-Modal Benchmarking: Comparative empirical baselines under fault-injection and synthetic workload scaling. Author Information Author: Sonu Kumar SinghRole: Senior Consultant Affiliation: Independent Researcher Publication Status: Preprint / Working Paper (MSIT AI & Cloud Systems Research Series) Reproducibility & Open Science All included architecture diagrams, telemetry schemas, and benchmark curves are open-access under the Creative Commons Attribution 4.0 International (CC BY 4.0) license.
Quantum computing (QC) stands at the cusp of revolutionizing computation, yet its near-term potential, constrained by Noisy Intermediate-Scale Quantum (NISQ) devices, remains underexplored. This dissertation investigates how hybrid quantum-classical algorithms can address combinatorial optimization challenges in logistics, focusing on vehicle routing and drone delivery—NP-hard problems with exponential solution spaces that defy classical exhaustive methods. Amidst NISQ limitations like limited qubits and high noise, we confront key challenges: encoding complex constraints, e.g., time windows, battery capacity, into quantum models, balancing quantum and classical components for scalability, and accessing scarce quantum resources. By integrating quantum annealing (QA) and the Quantum Approximate Optimization Algorithm (QAOA) with classical heuristics, this work demonstrates QC’s practical utility, advancing both optimization theory and real-world logistics applications. The dissertation unfolds across four core contributions. First, the Hybrid Quantum Tabu Search (HQTS) optimally solves the 50-location Capacitated Vehicle Routing Problem (CVRP), achieving a 4.72% optimality gap. Secondly, we refine HQTS to reach a 2.15% gap with enhanced QA utilization, outperforming prior hybrids on standard datasets. Third, adapting HQTS for the CVRPTWwith D-Wave’s Constrained Quadratic Model solver yields a 3.85% gap on 100-location instances, leveraging a novel heuristic to ensure time-window feasibility where quantum outputs falter. Lastly, QUADRO, a pioneering framework for drone delivery, employs QAOA-driven routing and hybrid scheduling, minimizing transit time and makespan for fleets of 2–11 drones needing fewer than 100 qubits, rivaling classical benchmarks on adapted Augerat datasets. These advances, tested via D-Wave’s Advantage system and Qiskit simulations, showcase hybrid strategies that mitigate NISQ constraints, delivering scalable, feasible solutions to logistics challenges. This work establishes near-term QC’s viability for combinatorial optimization, bridging theoretical promise with practical impact. Synthesizing quantum exploration with classical refinement achieves competitive performance, e.g., matching or surpassing Google ORTools in select CVRPTW cases, while illuminating NISQ limits, such as feasibility degradation beyond small scales. These hybrid strategies deliver scalable, feasible solutions, from a 2.15% optimality gap for CVRP to effective drone fleet management with fewer than 100 qubits, illuminating quantum computing’s potential despite its current constraints. Ultimately, this dissertation positions hybrid QC as a transformative tool for optimization challenges, offering a robust foundation for scaling quantum optimization into operational reality.
The Capacitated Vehicle Routing Problem (CVRP) is a combinatorial optimization problem that can be formulated as a Quadratic Unconstrained Binary Optimization (QUBO) problem, making it a potential application for near-term quantum optimization. This paper benchmarks the Quantum Approximate Optimization Algorithm (QAOA, p = 2) against Google OR-Tools Guided Local Search on a seeded instance with three customers and two vehicles. The study examines the QUBO formulation, energy spectrum, optimization behavior, penalty weights, Hamiltonian scaling, and circuit depths. The experiments show that the tested QAOA configurations do not reliably concentrate probability on optimal solutions. The classical solver identifies the optimal solution for the selected instance. The study provides a reproducible baseline and discusses limitations and future research directions. The findings are limited to the tested instance, formulation, and optimization configurations.
We demonstrate an end-to-end hybrid quantum-classical optimisation framework based on Benders decomposition, capable of solving mixed-integer linear programming (MILP) problems. The framework builds on a previously presented hybrid quantum-classical end-to-end pipeline based on Multiple Cuts via Multiple Solutions (MCMS) Benders decomposition where the cut selection step was performed on quantum annealing hardware. We extend this with gate-based QAOA implementations for both tensor network emulators and superconducting quantum hardware. The Vehicle Routing Problem (VRP) is used as a representative case study and we run the pipeline end-to-end on 10 permutations of a standardised benchmarking instance (20 customers and 4 vehicles from QOptLib) with a classical solver performing the cut selection step. We find that for our instances, only a small fraction of the compute in classical MCMS Benders decomposition is spent on the cut selection step. For a full hybrid end-to-end assessment, we run the pipeline for a toy problem with MPS-JuliQAOA, a powerful tensor network emulator, to execute QAOA. Here, the majority of the time is spent on the cut selection step, deeming quantum advantage of this framework unlikely at problems of this size. This highlights the need for more large-scale benchmarking research when more powerful (QPU) QUBO solvers are available.
Optimization of vehicle-to-station assignments under capacity and distance constraints represents a challenging combinatorial problem relevant to automated planning, logistics, and autonomous mobility systems. Classical methods such as Mixed Integer Linear Programming (MILP) or metaheuristics often struggle to scale efficiently with problem dimensionality, motivating the exploration of hybrid quantum-classical paradigms. This paper presents a normalized Quantum Approximate Optimization Algorithm (QAOA) framework tailored for constrained assignment problems, where vehicle-station distances are encoded into a normalized cost Hamiltonian. Capacity violations and unused resources are incorporated through dynamically scaled penalty terms, producing a cost landscape that effectively guides the quantum search process. The proposed pipeline integrates parameter optimization using COBYLA to refine the QAOA angles, ensuring convergence toward low-cost feasible configurations. Experimental simulations in Cirq on a 10-qubit system demonstrate that the normalized QAOA pipeline consistently identifies near-optimal assignments while substantially reducing the combinatorial search space. These results provide empirical evidence for the viability of hybrid QAOA formulations in real-world planning and scheduling scenarios, establishing a foundation for future implementations on noisy intermediatescale quantum (NISQ) hardware.
This study proposes a hybrid quantum-classical approach to solving the Capacitated Vehicle Routing Problem (CVRP) by integrating the Column Generation (CG) method with the Quantum Alternating Operator Ansatz (QAOAnsatz). The CG method divides the CVRP into the reduced master problem, which finds the best combination of the routes under the route set, and one or more subproblems, which generate the routes that would be beneficial to add to the route set. This method is iteratively refined by adding new routes identified via subproblems and continues until no improving route can be found. We leverage the QAOAnsatz to solve the subproblems. Our algorithm restricts the search space by designing the QAOAnsatz mixer Hamiltonian to enforce one-hot constraints. Moreover, to handle capacity constraints in QAOAnsatz, we employ an Augmented Lagrangian-inspired method that obviates the need for additional slack variables, reducing the required number of qubits. Experimental results on small-scale CVRP instances (up to 6 customers) show that QAOAnsatz converges more quickly to optimal routes than the standard QAOA approach, demonstrating the potential of this hybrid framework in tackling realworld logistical optimization problems on near-term quantum hardware.