An Advanced Hybrid Quantum Tabu Search Approach to Vehicle Routing Problems

• URL: http://arxiv.org/abs/2501.12652v1
• Date: Wed, 22 Jan 2025 05:29:27 GMT
• Title: An Advanced Hybrid Quantum Tabu Search Approach to Vehicle Routing Problems
• Authors: James B. Holliday, Eneko Osaba, Khoa Luu,
• Abstract summary: Hybrid approaches where QC and classical computing work together have shown the most potential for solving real-world scale problems. We present a new hybrid quantum-classical tabu search (HQTS) algorithm to solve the capacitated vehicle routing problem (RPCV) HQTS achieved optimal or near-optimal solutions for several CVRP problems, outperforming other hybrid CVRP algorithms.
• Score: 8.542666941016572
• License:
• Abstract: Quantum computing (QC) is expected to solve incredibly difficult problems, including finding optimal solutions to combinatorial optimization problems. However, to date, QC alone is still far to demonstrate this capability except on small-sized problems. Hybrid approaches where QC and classical computing work together have shown the most potential for solving real-world scale problems. This work aims to show that we can enhance a classical optimization algorithm with QC so that it can overcome this limitation. We present a new hybrid quantum-classical tabu search (HQTS) algorithm to solve the capacitated vehicle routing problem (CVRP). Based on our prior work, HQTS leverages QC for routing within a classical tabu search framework. The quantum component formulates the traveling salesman problem (TSP) for each route as a QUBO, solved using D-Wave's Advantage system. Experiments investigate the impact of quantum routing frequency and starting solution methods. While different starting solution methods, including quantum-based and classical heuristics methods, it shows minimal overall impact. HQTS achieved optimal or near-optimal solutions for several CVRP problems, outperforming other hybrid CVRP algorithms and significantly reducing the optimality gap compared to preliminary research. The experimental results demonstrate that more frequent quantum routing improves solution quality and runtime. The findings highlight the potential of integrating QC within meta-heuristic frameworks for complex optimization in vehicle routing problems.

Related papers

• 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)
• Qubit efficient quantum algorithms for the vehicle routing problem on NISQ processors [48.68474702382697]
  Vehicle routing problem with time windows (VRPTW) is a common optimization problem faced within the logistics industry. In this work, we explore the use of a previously-introduced qubit encoding scheme to reduce the number of binary variables.
  arXiv  Detail & Related papers  (2023-06-14T13:44:35Z)
• Quantum-Assisted Solution Paths for the Capacitated Vehicle Routing Problem [0.0]
  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.
  arXiv  Detail & Related papers  (2023-04-19T13:03:50Z)
• 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)
• Recommending Solution Paths for Solving Optimization Problems with Quantum Computing [4.306566710489809]
  We propose a framework designed to identify and recommend the best-suited solution paths. State-of-the-art hybrid algorithms, encoding and decomposition techniques can be integrated in a modular manner. We demonstrate and validate our approach on a selected set of options and illustrate its application on the capacitated vehicle routing problem.
  arXiv  Detail & Related papers  (2022-12-21T15:55:43Z)
• Classically-Boosted Quantum Optimization Algorithm [0.0]
  We explore a natural approach to leveraging existing classical techniques to enhance quantum optimization. Specifically, we run a classical algorithm to find an approximate solution and then use a quantum circuit to search its "neighborhood" for higher-quality solutions. We demonstrate the applications of CBQOA to Max 3SAT and Max Bisection, and provide empirical evidence that it outperforms previous approaches on these problems.
  arXiv  Detail & Related papers  (2022-03-25T23:36:14Z)
• 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)
• A Hybrid Quantum-Classical Algorithm for Robust Fitting [47.42391857319388]
  We propose a hybrid quantum-classical algorithm for robust fitting. Our core contribution is a novel robust fitting formulation that solves a sequence of integer programs. We present results obtained using an actual quantum computer.
  arXiv  Detail & Related papers  (2022-01-25T05:59:24Z)
• 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)
• Applying quantum approximate optimization to the heterogeneous vehicle routing problem [0.7503129292751939]
  We investigate the potential use of a quantum computer to find approximate solutions to the heterogeneous vehicle routing problem. We find that the number of qubits needed for this mapping scales quadratically with the number of customers.
  arXiv  Detail & Related papers  (2021-10-13T15:38:25Z)
• 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.