Solving Vehicle Routing Problem Using Grover Adaptive Search Algorithm

Intelligent Transportation Systems (ITS) occupy a pivotal position in the contemporary societal landscape, with one of their widespread applications being the vehicle routing problem, renowned for its classification as an NP-hard challenge. Traditional algorithms often require considerable time to address such problems or can only provide approximate solutions. Recent progress in quantum computation, however, offer a promising alternative by utilizing the parallelism inherent in quantum mechanics. In this study, we propose to solve the vehicle routing problem using the Grover adaptive algorithm. Compared to classical algorithms and existing quantum methods, our innovative algorithm achieves a quadratic speedup, with a time complexity of <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$O(K\sqrt{\frac{N}{M}})$</tex-math></inline-formula>. Additionally, it is applicable to a broader range of real-world scenarios, as it can directly handle linear inequality constraints without introducing slack variables. Notably, the algorithm operates independently of classical optimizers and gradient-based methods, thereby circumventing potential challenges such as the “barren plateaus” phenomenon. Experimental results from four instances demonstrate the feasibility and correctness of the proposed approach, highlighting its capability to handle inequality constraints easily.