Solving The Vehicle Routing Problem via Quantum Support Vector Machines

• URL: http://arxiv.org/abs/2308.04849v1
• Date: Wed, 9 Aug 2023 10:24:59 GMT
• Title: Solving The Vehicle Routing Problem via Quantum Support Vector Machines
• Authors: Nishikanta Mohanty, Bikash K. Behera, and Christopher Ferrie
• Abstract summary: The Vehicle Routing Problem (VRP) is an example of a optimization problem that has attracted academic attention. Quantum machine learning offers a new way to obtain solutions by harnessing the natural speedups of quantum effects. We implement and test hybrid quantum machine learning methods for solving VRP of 3 and 4-city scenarios.
• Score: 0.0
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: The Vehicle Routing Problem (VRP) is an example of a combinatorial optimization problem that has attracted academic attention due to its potential use in various contexts. VRP aims to arrange vehicle deliveries to several sites in the most efficient and economical manner possible. Quantum machine learning offers a new way to obtain solutions by harnessing the natural speedups of quantum effects, although many solutions and methodologies are modified using classical tools to provide excellent approximations of the VRP. In this paper, we implement and test hybrid quantum machine learning methods for solving VRP of 3 and 4-city scenarios, which use 6 and 12 qubit circuits, respectively. The proposed method is based on quantum support vector machines (QSVMs) with a variational quantum eigensolver on a fixed or variable ansatz. Different encoding strategies are used in the experiment to transform the VRP formulation into a QSVM and solve it. Multiple optimizers from the IBM Qiskit framework are also evaluated and compared.

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)
• Quantum Subroutine for Variance Estimation: Algorithmic Design and Applications [80.04533958880862]
  Quantum computing sets the foundation for new ways of designing algorithms. New challenges arise concerning which field quantum speedup can be achieved. Looking for the design of quantum subroutines that are more efficient than their classical counterpart poses solid pillars to new powerful quantum algorithms.
  arXiv  Detail & Related papers  (2024-02-26T09:32:07Z)
• 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)
• QNEAT: Natural Evolution of Variational Quantum Circuit Architecture [95.29334926638462]
  We focus on variational quantum circuits (VQC), which emerged as the most promising candidates for the quantum counterpart of neural networks. Although showing promising results, VQCs can be hard to train because of different issues, e.g., barren plateau, periodicity of the weights, or choice of architecture. We propose a gradient-free algorithm inspired by natural evolution to optimize both the weights and the architecture of the VQC.
  arXiv  Detail & Related papers  (2023-04-14T08:03:20Z)
• Analysis of The Vehicle Routing Problem Solved via Hybrid Quantum Algorithms in Presence of Noisy Channels [0.0]
  The objective is to plan routes of vehicles to deliver goods to a fixed number of customers with optimal efficiency. We build a basic VRP solver for 3 and 4 cities using the variational quantum eigensolver on a fixed ansatz. We find that the performance of the quantum algorithm depends heavily on what noise model is used.
  arXiv  Detail & Related papers  (2022-05-13T11:29:12Z)
• 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)
• 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)
• Machine Learning Framework for Quantum Sampling of Highly-Constrained, Continuous Optimization Problems [101.18253437732933]
  We develop a generic, machine learning-based framework for mapping continuous-space inverse design problems into surrogate unconstrained binary optimization problems. We showcase the framework's performance on two inverse design problems by optimizing thermal emitter topologies for thermophotovoltaic applications and (ii) diffractive meta-gratings for highly efficient beam steering.
  arXiv  Detail & Related papers  (2021-05-06T02:22:23Z)
• Solving Vehicle Routing Problem Using Quantum Approximate Optimization Algorithm [0.0]
  We describe the Quantum Approximate Optimization Algorithm (QAOA) to solve the integer programming task known as Vehicle Routing Problem (VRP) We outline the Ising formulation for VRP and present a detailed procedure to solve VRP by minimizing its simulated Ising Hamiltonian using the IBM Qiskit platform.
  arXiv  Detail & Related papers  (2020-02-02T18:12:19Z)

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.