Analysis of Vehicle Routing Problem in Presence of Noisy Channels
- URL: http://arxiv.org/abs/2112.15408v2
- Date: Thu, 13 Jan 2022 14:43:48 GMT
- Title: Analysis of Vehicle Routing Problem in Presence of Noisy Channels
- Authors: Nishikanta Mohanty, and Bikash K. Behera
- Abstract summary: 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.
- Score: 0.0
- License: http://creativecommons.org/licenses/by-nc-nd/4.0/
- Abstract: 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 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. Quantum computers such as IBM-Q experience
along with Qiskit framework offer tools to solve combinatorial optimization
problems. This work proposed here builds a basic VRP solution for 3 and 4
cities using variational quantum eigensolver on a variable ANSATZ. The work is
further extended to evaluate the robustness of the solution in noisy channels
available within the ambit of Qiskit framework.
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) - Multi-Objective Optimization and Network Routing with Near-Term Quantum
Computers [0.2150989251218736]
We develop a scheme with which near-term quantum computers can be applied to solve multi-objective optimization problems.
We focus on an implementation based on the quantum approximate optimization algorithm (QAOA)
arXiv Detail & Related papers (2023-08-16T09:22:01Z) - Solving The Vehicle Routing Problem via Quantum Support Vector Machines [0.0]
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.
arXiv Detail & Related papers (2023-08-09T10:24:59Z) - 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) - 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) - Quantum-inspired optimization for wavelength assignment [51.55491037321065]
We propose and develop a quantum-inspired algorithm for solving the wavelength assignment problem.
Our results pave the way to the use of quantum-inspired algorithms for practical problems in telecommunications.
arXiv Detail & Related papers (2022-11-01T07:52:47Z) - 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) - 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.