Hybrid Quantum–Classical Optimization with Applications to Routing Problems

Dapeng Wang

Ninad Hirani

Quantum Optimization Pipeline for the Capacitated Vehicle Routing Problem (CVRP) This repository presents a research-oriented implementation of classical and quantum optimization techniques for solving the Capacitated Vehicle Routing Problem (CVRP). The project serves as an educational and experimental framework for studying hybrid quantum-classical optimization methods and benchmarking their performance on combinatorial optimization problems. The implementation includes: Classical CVRP optimization using Google OR-Tools Mathematical formulation of the routing problem Transformation of the optimization problem into a Quadratic Unconstrained Binary Optimization (QUBO) model Conversion of the QUBO formulation into an Ising Hamiltonian Implementation of the Quantum Approximate Optimization Algorithm (QAOA) using Qiskit Classical versus quantum performance comparison Route visualization and benchmarking Modular Python code designed for experimentation and future extensions The project is intended as a foundation for exploring applications of Quantum Computing, Operations Research, and Hybrid Quantum-Classical Optimization in real-world routing and logistics problems. It provides a reproducible environment for understanding optimization workflows, evaluating quantum algorithms, and extending the framework toward more complex scenarios such as dynamic vehicle routing and emergency ambulance dispatch. Keywords: Quantum Computing, Quantum Optimization, QAOA, QUBO, Ising Model, Capacitated Vehicle Routing Problem (CVRP), Operations Research, OR-Tools, Qiskit, Combinatorial Optimization, Hybrid Quantum-Classical Algorithms. This software was developed as part of a research internship focused on quantum optimization and serves as a learning and experimentation platform for future research.

Dilnoz Muhamediyeva, Rustam Raximov, Shavkat Urokov

James B. Holliday, Braeden Morgan, Hugh Churchill +1 more

There has never been a more exciting time for the future of quantum computing than now. Real-world quantum computing usage is now the next XPRIZE. With that challenge in mind we have explored a new approach as a hybrid quantum-classical algorithm for solving NP-Hard optimization problems. We have focused on the classic problem of the Capacitated Vehicle Routing Problem (CVRP) because of its real-world industry applications. Heuristics are often employed to solve this problem because it is difficult. In addition, meta-heuristic algorithms have proven to be capable of finding reasonable solutions to optimization problems like the CVRP. Recent research has shown that quantum-only and hybrid quantum/classical approaches to solving the CVRP are possible. Where quantum approaches are usually limited to minimal optimization problems, hybrid approaches have been able to solve more significant issues. Still, the hybrid approaches often need help finding solutions as good as their classical counterparts. In our proposed approach, we created a hybrid quantum/classical meta-heuristic algorithm capable of finding the best-known solution to a classic CVRP problem. Our experimental results show that our proposed algorithm often outperforms other hybrid approaches.

Wei‐Hao Huang, Hiromichi Matsuyama, Yu Yamashiro

This study introduces a hybrid quantum-classical approach to solving the Capacitated Vehicle Routing Problems (CVRP), combining the Column Generation method and the Quantum Alternating Operator Ansatz (QAOAnsatz). The column generation method divides the problem into a master problem and subproblems to effectively solve the problem. We solved the subproblem by using QAOAnsatz to enhance the optimal solution search. Moreover, we generated the problem Hamiltonian using an Augmented Lagrangian-inspired Method to reduce the number of required qubits to handle the inequality. As a result, our experiments obtained an optimal solution for a CVRP problem with 6 customers. This study demonstrates a practical quantum application in logistics and sets a new technique for hybrid quantum-classical optimization frameworks.

Tomoyuki Yamakami