Hybrid Quantum-Classical Algorithm for Solving Capacitated Vehicle Routing Problems

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.