Quantum Approaches to Vehicle Routing Problems: A Review of Recent Advances and Future Directions
DISCLAIMER
Abstract
The application of quantum computing to vehicle routing problems (VRP) has gained traction as researchers seek novel approaches to tackle combinatorially complex, real-world logistics challenges. This paper surveys recent advancements since 2021, focusing on quantum annealing, gate-based quantum algorithms, and hybrid quantum-classical models. We compare their capabilities in solving different VRP variants, such as those with time windows, heterogeneous fleets, and multi-dimensional constraints. Emphasis is placed on the integration of quantum techniques within practical logistics contexts. We also discuss key challenges, performance metrics, and open problems in current quantum routing research.
1. Introduction
Vehicle Routing Problems (VRPs) represent a central challenge in operations research, with implications for logistics, urban mobility, and supply chains. Traditional algorithms struggle with large, constraint-laden instances due to the NP-hard nature of VRPs. Quantum computing, particularly quantum annealing and hybrid methods, offers a promising alternative. This review synthesizes research since 2021, reflecting the rapid growth and practical experimentation in this domain.
2. Methodologies
2.1 Quantum Annealing
Quantum annealing (QA) relies on minimizing a cost function encoded into a Hamiltonian, enabling optimization over large discrete spaces. D-Wave's Leap Constrained Quadratic Model (CQM) hybrid solver has become a focal point in recent studies. For example, Osaba et al. (2024) developed Q4RPD, a hybrid solver targeting real-world logistics with priority deliveries and multi-dimensional constraints.
Tambunan et al. (2022) extended this by integrating weighted road segments, modeling traffic congestion in the routing process. Weinberg et al. (2022) tackled multi-truck logistics with hybrid methods, demonstrating applicability to supply chain problems.
2.2 Gate-Based Algorithms
Gate-based quantum computing offers alternatives like Quantum Walk Optimization Algorithms (QWOA) and Quantum Approximate Optimization Algorithms (QAOA). A 2021 study introduced QWOA for solving capacitated VRPs with encouraging results on small-scale instances.
Palmieri (2022) proposed a hybrid QAOA-based model with clustering for the Capacitated VRP, showing improved convergence on pre-processed clusters solved with quantum subroutines.
2.3 Hybrid Learning-Quantum Models
Recent works explore integrating classical machine learning with quantum techniques. Abualigah et al. (2024) applied quantum support vector machines (QSVM) to classify optimal routes in small VRPs. While not scalable yet, these methods hint at future AI-quantum synergies.
2.4 Quantum Metaheuristics
A 2024 review introduced hybrid quantum tabu search methods for VRP, showcasing improved solution quality over classical heuristics by leveraging quantum-enhanced diversification.
3. Applications and Benchmarks
3.1 Real-World Scenarios
Q4RPD (Osaba et al., 2024) stands out for its industrial relevance. Applied to real Spanish logistics data, it respects time windows, prioritizes vehicle ownership, and models multi-dimensional truck capacities. It achieves near-parity with Google OR-Tools, validating the model’s practical utility.
Holliday et al. (2025) addressed VRPs with time windows, introducing feasibility-repair heuristics within quantum pipelines, achieving <4% optimality gaps on Solomon benchmarks.
3.2 Toy vs. Scalable Benchmarks
Most quantum studies still use toy-size datasets. Q4RPD and Holliday et al. are notable exceptions, solving 20+ node problems. Scalability remains limited by hardware (qubit count, noise) and model encoding complexity.
4. Challenges and Open Problems
Scalability: Encoding and solving larger instances remains impractical for pure quantum solutions.
Constraint handling: Time windows and multi-attribute constraints require flexible encoding strategies.
Benchmarking: Lack of standard datasets impedes fair performance comparisons.
Black-box solvers: Proprietary tools (e.g., LeapCQMHybrid) limit transparency and reproducibility.
5. Future Directions
Heuristic–Quantum Integration: Embedding business preferences as soft constraints or sub-objectives.
3D constraints: Extending current models to include bin-packing and volumetric truck capacities.
Multi-modal logistics: Incorporating air, sea, or rail into routing scenarios.
Adaptive solvers: Creating systems that auto-tune heuristics and constraint weights based on instance profiles.
Open frameworks: Developing reproducible, open-source benchmarks and solvers for quantum VRP research.
6. Conclusion
Quantum computing holds considerable promise for solving VRPs, especially via hybrid approaches. As hardware improves and methods mature, quantum-enhanced solvers may become viable for industrial-scale logistics. Current research, while still in early stages, has laid important groundwork—particularly in integrating constraints, business logic, and real-world data into quantum models.
References
Osaba, E. et al. (2024). Solving a real-world package delivery routing problem using quantum annealers. Scientific Reports, 14, 24791.
Weinberg, S. J. et al. (2022). Supply Chain Logistics with Quantum and Classical Annealing Algorithms. Scientific Reports, 13, 4770.
Palmieri, A. (2022). Quantum Integer Programming for the Capacitated Vehicle Routing Problem. Ph.D. Thesis.
Abualigah, L. et al. (2024). Solving the Vehicle Routing Problem via Quantum Support Vector Machines. Quantum Machine Learning, 3(1).
Hybrid Quantum Tabu Search for VRP (2024). Review Summary, TheMoonlight.io.
Quantum Computing in Logistics and SCM (2024). Comprehensive Review, TheMoonlight.io.
APENDIX A
Summary generated by ChatGPT of the paper “Solving a real-world package delivery routing problem using quantum annealers” by Osaba et al., including key achievements, identified drawbacks, and suggested improvements:
🔍 Summary
✅ Key Achievements
-
Real-World Relevance:
-
The paper introduces Q4RPD, a hybrid quantum-classical algorithm to solve a realistic last-mile delivery routing problem.
-
Unlike traditional Vehicle Routing Problems (VRP), this includes:
-
A heterogeneous fleet (owned and rented trucks),
-
Multi-dimensional capacities (weight and volume),
-
Priority deliveries (time-constrained),
-
Real business preferences (e.g., prioritize owned vehicles, reduce the number of trucks used).
-
-
-
Hybrid Quantum-Classical Approach:
-
The algorithm offloads route computation to D-Wave’s Leap Constrained Quadratic Model (CQM) Hybrid Solver, while classical routines manage problem decomposition and business logic.
-
-
Iterative Sub-Problem Solving:
-
Uses sub-route decomposition (Depot–TP, TP–TP, TP–Depot, full regular routes), enabling scalability and constraint compliance.
-
-
Benchmark with Six Scenarios:
-
Evaluated with six synthetic instances designed with the logistics partner Ertransit.
-
Q4RPD respected all constraints (capacity, priority, workday length) across the cases.
-
Performance was comparable or superior to Google OR-Tools, especially when priority constraints (TP) were included.
-
-
Scalability in NISQ Era:
-
Demonstrated capability to solve instances with up to 29 deliveries, which is larger than typical quantum routing benchmarks in current literature.
-
⚠️ Drawbacks and Limitations
-
Suboptimality due to Heuristics:
-
The pre-routing heuristics (e.g., preference for owned trucks) can limit global optimization potential, sometimes preventing the best solution.
-
-
Limited Constraint Flexibility:
-
Some preferences (notably P3: minimize number of trucks used) are not consistently enforced, despite being modeled as high-priority preferences.
-
-
No True End-to-End Quantum Formulation:
-
The actual quantum computation only addresses single-route subproblems, not the full 2DH-PDP optimization.
-
Full end-to-end quantum optimization remains out of reach, reflecting current hardware limitations.
-
-
Lack of Comparative Full-Classical Baseline:
-
While comparisons are made to classical TSP via Google OR-Tools, a full classical solver that handles all constraints (priority, heterogeneous fleet, 2D capacities) was not implemented as a baseline.
-
-
Synthetic Data Only:
-
All test instances are synthetic, limiting external generalizability. There's no validation against open, standard logistics datasets.
-
-
Proprietary Solver Black Box:
-
D-Wave’s LeapCQMHybrid is a proprietary black-box solver, limiting reproducibility and deeper understanding of quantum contributions.
-
🛠️ Suggested Improvements
-
Transform Preferences into Soft Constraints:
-
Rather than rigid heuristics, preferences like P1–P3 could be integrated into the objective function with penalty weights, allowing optimization flexibility.
-
-
Implement a Full Classical Baseline:
-
Design a comparable metaheuristic or MILP-based solver that handles the same constraints to better assess quantum advantage.
-
-
Generalize Dataset and Validation:
-
Incorporate real-world or standardized benchmarks, or release the synthetic generator to ensure better benchmarking by others.
-
-
Improve Constraint Fulfillment Mechanism:
-
Develop mechanisms to guarantee enforcement of business preferences like minimizing vehicle use (P3), possibly via dynamic preference weighting.
-
-
Quantum Efficiency Analysis:
-
Include runtime breakdown and a more detailed analysis of quantum vs classical contribution in solving times and quality.
-
-
Enable Truck Reuse and 3D Capacities:
-
Extend the model to allow multi-route assignments per truck and 3D volume constraints, increasing applicability.
-
-
Open Solver Source (if possible):
-
Open-source the classical components of Q4RPD for broader adoption and independent benchmarking.
-
🧠 Conclusion
The Q4RPD framework represents a significant step forward in real-world quantum logistics applications, pushing past toy problems into more practical constraints and objectives. However, to fully realize its potential, the authors (or future researchers) should prioritize:
-
More flexible modeling of constraints and preferences,
-
A stronger comparative baseline against classical solvers,
-
Greater transparency in solver behavior, and
-
Expansion of the framework’s generalizability and realism.
APENDIX B
Notable papers since 2021 found using ChatGPT that build on or relate closely to the topic of quantum-based vehicle routing and package-delivery:
\🛰️ Frontiers, 2021
"Quantum Walk‑Based Vehicle Routing Optimisation" demonstrates a gate-based quantum algorithm (QWOA) applied to the Capacitated Vehicle Routing Problem (CVRP). Through simulation on an 8-location instance, it achieves near-optimal results—showing the potential of quantum walks in routing contexts.
🧠 Weinberg et al., 2022
"Supply Chain Logistics with Quantum and Classical Annealing Algorithms" explores a hybrid workflow where multi-truck routing is broken down per truck. Using D-Wave Hybrid and simulated annealing on ~2500-variable QUBO subproblems, the routes feed into a classical simulation showing excellent supply-chain performance .
🚗 Tambunan et al., 2022
"Quantum Annealing for Vehicle Routing Problem with weighted Segment" offers a pure QUBO formulation targeting road congestion by incorporating weighted road segments. Tested on D-Wave hardware, it optimizes multi-vehicle route selection to ease congestion .
📦 Palmieri, 2022–2023 (Ph.D. thesis)
"Quantum Integer Programming for the Capacitated Vehicle Routing Problem" presents a two-phase hybrid: clustering via modularity maximization, then solving TSP subproblems using VQE/QAOA. Benchmarked against Gurobi for small instances .
🕒 Holliday et al., 2025 (arXiv)
"Advanced Quantum Annealing Approach to Vehicle Routing Problems with Time Windows" (Mar 2025) builds directly on the Q4RPD lineage. It uses D-Wave’s CQM hybrid solver and adds a feasibility-repair heuristic to handle time window violations. Achieves ~3.86% optimality gap on Solomon benchmarks .
🧪 Abualigah et al., 2024
"Solving the vehicle routing problem via quantum support vector machines" (June 2024) investigates a hybrid QSVM‑based encoding for small VRP instances (3–4 cities), using VQE-trained classifiers to predict optimal routes.
🔄 Hybrid Quantum Tabu Search, 2024
A promising hybrid metaheuristic combining tabu search with quantum annealing. Though I only found Lit‑Review coverage (April 2024), it specifically targets VRP and shows higher-quality solutions via intelligent search.
📈 2021–2023 Survey: "Quantum Computing in Logistics and SCM"
A comprehensive review published in February 2024 catalogs multiple hybrid and gate-based quantum approaches to VRP, CVRP, and VRP with time windows since 2021.
📊 Summary Table
| Year | Approach / Platform | Highlights |
|---|---|---|
| 2021 | QWOA (gate-based) | CVRP on 8 locations (frontiersin.org) |
| 2022 | Hybrid D-Wave + classic | Multi-truck routing, 2500-variable models |
| 2022 | QUBO with road congestion | Weighted-segment VRP |
| 2022/23 | Quantum integer programming (thesis) | Clustering + TSP via VQE/QAOA |
| 2024 | QSVM-based for small VRPs | Hybrid ML + quantum classification |
| 2024 | Hybrid Quantum Tabu Search | VRP-focused metaheuristic |
| 2025 | Advanced CQM hybrid + fix heuristic | VRPTW, ~3.9% gap on benchmarks |
| 2024 | Broad logistics/SCM quantum survey | Catalog of recent VRP quantum research |
🧭 Takeaways & Potential Gaps
-
Techniques range widely: gate-based (QWOA, QSVM), annealing + hybrid splits, heuristic repair methods, and metaheuristics (tabu).
-
Most scale only to small/routed subproblems, with few studies addressing real-world-sized, time-windowed, heterogeneous fleet problems.
-
Time-window feasibility remains a bottleneck—recent repair heuristics (Holliday et al.) begin to bridge that gap.
-
There’s a growing trend of hybridizing quantum with classical algorithms, plus early forays into machine learning enhancements.
No hay comentarios.:
Publicar un comentario