Quantum-Assisted Solution Paths for the Capacitated Vehicle Routing Problem

• URL: http://arxiv.org/abs/2304.09629v2
• Date: Sun, 7 May 2023 16:09:22 GMT
• Title: Quantum-Assisted Solution Paths for the Capacitated Vehicle Routing Problem
• Authors: Lilly Palackal, Benedikt Poggel, Matthias Wulff, Hans Ehm, Jeanette Miriam Lorenz, Christian B. Mendl
• Abstract summary: We discuss the Capacitated Vehicle 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.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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, warm-start 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.

Related papers

• PO-QA: A Framework for Portfolio Optimization using Quantum Algorithms [4.2435928520499635]
  Portfolio Optimization (PO) is a financial problem aiming to maximize the net gains while minimizing the risks in a given investment portfolio. We propose a novel scalable framework, denoted PO-QA, to investigate the variation of quantum parameters. Our results provide effective insights into comprehending PO from the lens of Quantum Machine Learning.
  arXiv  Detail & Related papers  (2024-07-29T10:26:28Z)
• Variational Quantum Algorithms for Combinatorial Optimization [0.571097144710995]
  Variational Algorithms (VQA) have emerged as one of the strongest candidates towards reaching practical applicability of NISQ systems. This paper explores the current state and recent developments of VQAs, emphasizing their applicability to Approximate optimization. We implement QAOA circuits with varying depths to solve the MaxCut problem on graphs with 10 and 20 nodes.
  arXiv  Detail & Related papers  (2024-07-08T22:02:39Z)
• Bayesian Parameterized Quantum Circuit Optimization (BPQCO): A task and hardware-dependent approach [49.89480853499917]
  Variational quantum algorithms (VQA) have emerged as a promising quantum alternative for solving optimization and machine learning problems. In this paper, we experimentally demonstrate the influence of the circuit design on the performance obtained for two classification problems. We also study the degradation of the obtained circuits in the presence of noise when simulating real quantum computers.
  arXiv  Detail & Related papers  (2024-04-17T11:00:12Z)
• Multi-objective Quantum Annealing approach for solving flexible job shop scheduling in manufacturing [0.0]
  This paper introduces Quantum Annealing-based solving algorithm (QASA) to address Flexible Job Shop Scheduling problem. Experiments on benchmark problems show QASA, combining tabu search, simulated annealing, and Quantum Annealing, outperforms a classical solving algorithm (CSA) in solution quality.
  arXiv  Detail & Related papers  (2023-11-16T07:45:57Z)
• A Feasibility-Preserved Quantum Approximate Solver for the Capacitated Vehicle Routing Problem [3.0567007573383678]
  The Capacitated Vehicle Routing Problem (CVRP) is an NP-optimization problem (NPO) that arises in various fields including transportation and logistics. We present a new binary encoding for the CVRP, with an objective function of minimizing the shortest path that bypasses the vehicle capacity constraint of the CVRP. We discuss the effectiveness of the proposed encoding under the framework of the variant of the Quantum Alternating Operator Ansatz.
  arXiv  Detail & Related papers  (2023-08-17T05:14:43Z)
• Quantum Annealing for Single Image Super-Resolution [86.69338893753886]
  We propose a quantum computing-based algorithm to solve the single image super-resolution (SISR) problem. The proposed AQC-based algorithm is demonstrated to achieve improved speed-up over a classical analog while maintaining comparable SISR accuracy.
  arXiv  Detail & Related papers  (2023-04-18T11:57:15Z)
• Adiabatic Quantum Computing for Multi Object Tracking [170.8716555363907]
  Multi-Object Tracking (MOT) is most often approached in the tracking-by-detection paradigm, where object detections are associated through time. As these optimization problems are often NP-hard, they can only be solved exactly for small instances on current hardware. We show that our approach is competitive compared with state-of-the-art optimization-based approaches, even when using of-the-shelf integer programming solvers.
  arXiv  Detail & Related papers  (2022-02-17T18:59:20Z)
• Analysis of Vehicle Routing Problem in Presence of Noisy Channels [0.0]
  Vehicle routing problem (VRP) is an NP-hard optimization problem. This work builds a basic VRP solution for 3 and 4 cities using variational quantum eigensolver on a variable ANSATZ.
  arXiv  Detail & Related papers  (2021-12-28T10:20:42Z)
• Quantum circuit architecture search for variational quantum algorithms [88.71725630554758]
  We propose a resource and runtime efficient scheme termed quantum architecture search (QAS) QAS automatically seeks a near-optimal ansatz to balance benefits and side-effects brought by adding more noisy quantum gates. We implement QAS on both the numerical simulator and real quantum hardware, via the IBM cloud, to accomplish data classification and quantum chemistry tasks.
  arXiv  Detail & Related papers  (2020-10-20T12:06:27Z)
• Space-efficient binary optimization for variational computing [68.8204255655161]
  We show that it is possible to greatly reduce the number of qubits needed for the Traveling Salesman Problem. We also propose encoding schemes which smoothly interpolate between the qubit-efficient and the circuit depth-efficient models.
  arXiv  Detail & Related papers  (2020-09-15T18:17:27Z)
• Cross Entropy Hyperparameter Optimization for Constrained Problem Hamiltonians Applied to QAOA [68.11912614360878]
  Hybrid quantum-classical algorithms such as Quantum Approximate Optimization Algorithm (QAOA) are considered as one of the most encouraging approaches for taking advantage of near-term quantum computers in practical applications. Such algorithms are usually implemented in a variational form, combining a classical optimization method with a quantum machine to find good solutions to an optimization problem. In this study we apply a Cross-Entropy method to shape this landscape, which allows the classical parameter to find better parameters more easily and hence results in an improved performance.
  arXiv  Detail & Related papers  (2020-03-11T13:52:41Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.