The determination of vehicle routes fulfilling connectivity, time, and operational constraints is a well-studied combinatorial optimization problem. The NP-hard complexity of vehicle routing problems has fostered the adoption of tailored exact approaches, matheuristics, and metaheuristics on classical computing devices. The ongoing evolution of quantum computing hardware and the recent advances of quantum algorithms (i.e., VQE, QAOA, and ADMM) for mathematical programming make decision-making for routing problems an avenue of research worthwhile to be explored on quantum devices. In this article, we propose several mathematical formulations for inventory routing cast as vehicle routing with time windows and comment on their strengths and weaknesses. The optimization models are compared from a quantum computing perspective, specifically with metrics to evaluate the difficulty in solving the underlying quadratic unconstrained binary optimization problems. Finally, the solutions obtained on simulated quantum devices demonstrate the relative benefits of different algorithms and their robustness when put into practice.
The determination of vehicle routes fulfilling connectivity, time, and operational constraints is a well-studied combinatorial optimization problem. The NP-hard complexity of vehicle routing problems has fostered the adoption of tailored exact approaches, matheuristics, and metaheuristics on classical computing devices. The ongoing evolution of quantum computing hardware and the recent advances of quantum algorithms (i.e., VQE, QAOA, and ADMM) for mathematical programming make decision-making for routing problems an avenue of research worthwhile to be explored on quantum devices. In this article, we propose several mathematical formulations for inventory routing cast as vehicle routing with time windows and comment on their strengths and weaknesses. The optimization models are compared from a quantum computing perspective, specifically with metrics to evaluate the difficulty in solving the underlying quadratic unconstrained binary optimization problems. Finally, the solutions obtained on simulated quantum devices demonstrate the relative benefits of different algorithms and their robustness when put into practice.
Vehicle Routing Problem (VRP) is considered one of the most challenging problems with application in several domains, including transportation and logistics distribution. VRP is known to be NP-Hard problem. Several algorithms have been proposed to solve VRP in polynomial time. However, these algorithms are inefficient if the VRP instance increases. Recently, researchers investigated how quantum computing can be used to solve VRP. In particular, two promising variational quantum algorithms have been studied, i.e., Variational Quantum Eigensolver (VQE) and Quantum Approximate Optimization Algorithm (QAOA). In this paper, we implement both algorithms on IBM Qiskit and compare their evaluation in solving several instances of VRP. We observe that current Noisy-Intermediate Scale Quantum (NISQ) devices cannot solve VRP instances beyond 5 nodes and 2 vehicles. Furthermore, we observe that classical optimizers still provide better results. However, we believe that with the rapid advancement of quantum computing manufacturing, VQE and QAOA can provide better performance as compared to classical computing,
Vehicle Routing Problem is a well-known optimization issue, which has many extensions resulting from practical appliances. The problem is NP-hard, therefore it may be impossible to find an optimal solution for big instances, with traditional computation methods. Recent development of quantum technology, may be a response for this challenge, which however requires a different formulation of the model. The problem is then modeled using Quadratic Unconstrained Binary Optimization (QUBO) equations. Such model can be run using quantum annealers (QA), designed specifically for optimization purposes. This paper is a systematic survey of Vehicle Routing Problem models that are formulated using QUBO, to be solved on quantum computers. The main goal of the paper is to check research gaps in this subject, compare and explain different approaches of modeling various problem extensions with QUBO. The results obtained in reviewed papers will be presented and analyzed. Moreover, the theoretical basis for quantum computation will be presented, with focus on D-Wave company solutions.
The vehicle routing problem (VRP) is an NP-hard optimization problem that has been an interest of research for decades in science and industry. The objective is to plan routes of vehicles to deliver goods to a fixed number of customers with optimal efficiency. Classical tools and methods provide good approximations to reach the optimal global solution. Quantum computing and quantum machine learning provide a new approach to solving combinatorial optimization of problems faster due to inherent speedups of quantum effects. Many solutions of VRP are offered across different quantum computing platforms using hybrid algorithms such as quantum approximate optimization algorithm and quadratic unconstrained binary optimization. In this work, we build a basic VRP solver for 3 and 4 cities using the variational quantum eigensolver on a fixed ansatz. The work is further extended to evaluate the robustness of the solution in several examples of noisy quantum channels. We find that the performance of the quantum algorithm depends heavily on what noise model is used. In general, noise is detrimental, but not equally so among different noise sources.
Introduction. The hope of solving the problem of the avalanche-like growth of requirements for computing power, essential for solving complex routing problems and other problems of combinatorial optimization, relies on the latest quantum computers, in the development of which governments and corporations invest multi-billion investments. The article examines modern routing algorithms and performs their analysis and verification, if the authors of the algorithm provided appropriate test programs. The purpose of the article is to review the current state of development in the field of development of routing algorithms for hybrid quantum-classical clouds, analyze them and propose a classification of algorithms. Results. Modern quantum computers (QCs) make it possible to find approximate solutions to some of mathematical problems faster than classical computers. The inaccuracy of the solutions obtained by the QC is a consequence of physical and technological limitations: calculation errors are caused by thermal noise, a small number of computational elements - qubits and connections between them, which requires the decomposition of the problem and the use of heuristic algorithms. The analysis of approaches to the solution of optimization problems on QC allows us to single out: quantum response and variational search of eigenvalues based on quantum logic gates as the general directions of development of the vast majority of algorithms for solving routing problems. The considered algorithms reduce the vehicle routing problem to a quadratic unconstrained binary optimization problem, which is isomorphic to the Hamilton-Ising model. In this form, the problem is suitable for embedding in QC, which finds an approximate solution that has the best statistical reliability or corresponds to the quantum state with the lowest energy. As a separate class, vehicle routing algorithms for classical computers that use quantum computing to accelerate problem solving can be distinguished. For example, neural networks that calculate weighting factors using QC or an ant algorithm that calculates a pheromone trail in a hybrid cloud. It should be mentioned the quantum-inspired algorithms, which are based on software tools for the simulation of QC and the corresponding libraries and allow creating an effective class of algorithms for solving problems of vehicle routing. Conclusions. Combining hardware quantum annealing with a number of software tools for calculating optimization problems for classical computers in a hybrid quantum-classical cloud service allows to obtain advantages in speed and accuracy of some types of complex optimization problems of a commercial scale, in particular, routing vehicles, which is already bringing substantial profits to a number of corporations. Keywords: vehicle routing problem, quantum computer, annealing, combinatorial optimization, traveling salesman problem, clustering, qubit.
Many relevant problems in industrial settings result in NP-hard optimization problems, such as the Capacitated Vehicle Routing Problem (CVRP) or its reduced variant, the Travelling Salesperson Problem (TSP). Even with today's most powerful classical algorithms, the CVRP is challenging to solve classically. Quantum computing may offer a way to improve the time to solution, although the question remains open as to whether Noisy Intermediate-Scale Quantum (NISQ) devices can achieve a practical advantage compared to classical heuristics. The most prominent algorithms proposed to solve combinatorial optimization problems in the NISQ era are the Quantum Approximate Optimization Algorithm (QAOA) and the more general Variational Quantum Eigensolver (VQE). However, implementing them in a way that reliably provides high-quality solutions is challenging, even for toy examples. In this work, we discuss decomposition and formulation aspects of the CVRP and propose an application-driven way to measure solution quality. Considering current hardware constraints, we reduce the CVRP to a clustering phase and a set of TSPs. For the TSP, we extensively test both QAOA and VQE and investigate the influence of various hyperparameters, such as the classical optimizer choice and strength of constraint penalization. Results of QAOA are generally of limited quality because the algorithm does not reach the energy threshold for feasible TSP solutions, even when considering various extensions such as recursive and constraint-preserving mixer QAOA. On the other hand, the VQE reaches the energy threshold and shows a better performance. Our work outlines the obstacles to quantum-assisted solutions for real-world optimization problems and proposes perspectives on how to overcome them.
Quantum computing offers new heuristics for combinatorial problems. With small- and intermediate-scale quantum devices becoming available, it is possible to implement and test these heuristics on small-size problems. A candidate for such combinatorial problems is the heterogeneous vehicle routing problem (HVRP): the problem of finding the optimal set of routes, given a heterogeneous fleet of vehicles with varying loading capacities, to deliver goods to a given set of customers. In this work, we investigate the potential use of a quantum computer to find approximate solutions to the HVRP using the quantum approximate optimization algorithm (QAOA). For this purpose we formulate a mapping of the HVRP to an Ising Hamiltonian and simulate the algorithm on problem instances of up to 21 qubits. We show that the number of qubits needed for this mapping scales quadratically with the number of customers. We compare the performance of different classical optimizers in the QAOA for varying problem size of the HVRP, finding a trade-off between optimizer performance and runtime.