A feasibility-preserved quantum approximate solver for the capacitated vehicle routing problem

Author

Ningyi XIE
Xinwei LEE
Dongsheng CAI
Yoshiyuki SAITO
Nobuyoshi ASAI
Hoong Chuin LAU, Singapore Management UniversityFollow

Publication Type

Journal Article

Version

acceptedVersion

Publication Date

7-2024

Abstract

The Capacitated Vehicle Routing Problem (CVRP) is an NP-optimization problem (NPO) that arises in various fields including transportation and logistics. The CVRP extends from the Vehicle Routing Problem (VRP), aiming to determine the most efficient plan for a fleet of vehicles to deliver goods to a set of customers, subject to the limited carrying capacity of each vehicle. As the number of possible solutions increases exponentially with the number of customers, finding high-quality solutions remains a significant challenge. Recently, the Quantum Approximate Optimization Algorithm (QAOA), a quantum–classical hybrid algorithm, has exhibited enhanced performance in certain combinatorial optimization problems, such as the Max-Cut problem, compared to classical heuristics. However, its ability diminishes notably in solving constrained optimization problems including the CVRP. This limitation primarily arises from the typical approach of encoding the given problems as unconstrained binary optimization problems with penalty terms. In this case, the QAOA faces challenges in sampling solutions satisfying all constraints. Addressing this, our work presents a new binary encoding for the CVRP, with an alternative objective function of minimizing the shortest path that bypasses the vehicle capacity constraint of the CVRP. The search space is further restricted by the constraint-preserving mixing operation. We examine and discuss the effectiveness of the proposed encoding under the framework of the variant of the QAOA, Quantum Alternating Operator Ansatz (AOA), through its application to several illustrative examples. Compared to the typical QAOA approach, our proposed method not only preserves the feasibility but also achieves a significant enhancement in the probability of measuring optimal solutions.

Keywords

CVRP, Problem encoding, QAOAAOA, Feasibility, Algorithms

Discipline

Numerical Analysis and Scientific Computing | Operations Research, Systems Engineering and Industrial Engineering | Theory and Algorithms

Research Areas

Intelligent Systems and Optimization

Publication

Quantum Information Processing

Volume

23

Issue

8

First Page

1

Last Page

10

ISSN

1570-0755

Identifier

10.1007/s11128-024-04497-5

Publisher

Springer

Citation

XIE, Ningyi; LEE, Xinwei; CAI, Dongsheng; SAITO, Yoshiyuki; ASAI, Nobuyoshi; and LAU, Hoong Chuin. A feasibility-preserved quantum approximate solver for the capacitated vehicle routing problem. (2024). Quantum Information Processing. 23, (8), 1-10.
Available at: https://ink.library.smu.edu.sg/sis_research/9892

Copyright Owner and License

Author-CC-BY

Creative Commons License

This work is licensed under a Creative Commons Attribution-NonCommercial-No Derivative Works 4.0 International License.

Additional URL

https://doi.org/10.1007/s11128-024-04497-5