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

• Main Authors: XIE, Ningyi, LEE, Xinwei, CAI, Dongsheng, SAITO, Yoshiyuki, ASAI, Nobuyoshi, LAU, Hoong Chuin
• Format: text
• Language: English
• Published: Institutional Knowledge at Singapore Management University 2024
• Subjects: CVRP; Problem encoding; QAOAAOA; Feasibility; Algorithms; Numerical Analysis and Scientific Computing; Operations Research, Systems Engineering and Industrial Engineering; Theory and Algorithms
• Online Access: https://ink.library.smu.edu.sg/sis_research/9892; https://ink.library.smu.edu.sg/context/sis_research/article/10892/viewcontent/Feasibility_preserved_Quantum_av.pdf
• Institution: Singapore Management University

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.