Quantum Annealing for Vehicle Routing Problem with weighted Segment

• URL: http://arxiv.org/abs/2203.13469v1
• Date: Fri, 25 Mar 2022 06:38:18 GMT
• Title: Quantum Annealing for Vehicle Routing Problem with weighted Segment
• Authors: Toufan D. Tambunan, Andriyan B. Suksmono, Ian J.M. Edward, Rahmat Mulyawan
• Abstract summary: The study presents a QUBO formulation to solve traffic congestion problems on certain roads. The resulting route selection by optimizing the distribution of the flow of alternative road vehicles based on the weighting of road segments. The simulations on the D-Wave quantum annealer show optimal results on the route deployment of several vehicles.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Quantum annealing technologies aim to solve computational optimization and sampling problems. QPU (Quantum Processing Unit) machines such as the D-Wave system use the QUBO (Quadratic Unconstrained Binary Optimization) formula to define model optimization problems for quantum annealing. This machine uses quantum effects to speed up computing time better than classical computers. We propose a vehicle routing problem that can be formulated in the QUBO model as a combinatorial problem, which gives the possible route solutions increases exponentially. The solution aims to optimize the vehicle's journey to reach a destination. The study presents a QUBO formulation to solve traffic congestion problems on certain roads. The resulting route selection by optimizing the distribution of the flow of alternative road vehicles based on the weighting of road segments. Constraints formulated as a condition for the level of road density. The road weight parameter influences the cost function for each road choice. The simulations on the D-Wave quantum annealer show optimal results on the route deployment of several vehicles. So that each vehicle will be able to go through different road options and reduce road congestion accurately. This solution provides an opportunity to develop QUBO modeling for more complex vehicle routing problems for road congestion.

Related papers

• Convex Physics Informed Neural Networks for the Monge-Ampère Optimal Transport Problem [49.1574468325115]
  Optimal transportation of raw material from suppliers to customers is an issue arising in logistics. A physics informed neuralnetwork method is advocated here for the solution of the corresponding generalized Monge-Ampere equation. A particular focus is set on the enforcement of transport boundary conditions in the loss function.
  arXiv  Detail & Related papers  (2025-01-17T12:51:25Z)
• Quantum Annealing Approaches to Solving the Shipment Rerouting Problems [7.888128236684232]
  We study a shipment rerouting problem (SRP) which generalizes many NP-hard sequencing and packing problems. The objective is to select a set of trucks and to schedule these trucks' routes so that the total cost is minimized. We use novel mathematical programming formulations and new insights into solving sequencing and packing problems simultaneously.
  arXiv  Detail & Related papers  (2025-01-09T23:47:23Z)
• 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)
• Quadratic Unconstrained Binary Formulation for Traffic Signal Optimization on Real-World Maps [0.4915744683251151]
  The D-Wave quantum annealing machine can quickly find the optimal solution for quadratic unconstrained binary optimization (QUBO) We propose a different formulation of QUBO that can also deal with T-junctions and multi-forked roads. Our results show that the D-Wave machine could not find the optimal solution and was slower than the Gurobi in time.
  arXiv  Detail & Related papers  (2023-08-28T10:00:50Z)
• 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)
• 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)
• Road Network Guided Fine-Grained Urban Traffic Flow Inference [108.64631590347352]
  Accurate inference of fine-grained traffic flow from coarse-grained one is an emerging yet crucial problem. We propose a novel Road-Aware Traffic Flow Magnifier (RATFM) that exploits the prior knowledge of road networks. Our method can generate high-quality fine-grained traffic flow maps.
  arXiv  Detail & Related papers  (2021-09-29T07:51:49Z)
• Quadratic and Higher-Order Unconstrained Binary Optimization of Railway Rescheduling for Quantum Computing [0.5161531917413706]
  This paper introduces QUBO and HOBO representations for rescheduling problems of railway traffic management. We consider the conditions of minimal headway between trains, minimal stay on stations, track occupation, and rolling stock circulation.
  arXiv  Detail & Related papers  (2021-07-07T14:07:07Z)
• Reinforcement Learning Based Vehicle-cell Association Algorithm for Highly Mobile Millimeter Wave Communication [53.47785498477648]
  This paper investigates the problem of vehicle-cell association in millimeter wave (mmWave) communication networks. We first formulate the user state (VU) problem as a discrete non-vehicle association optimization problem. The proposed solution achieves up to 15% gains in terms sum of user complexity and 20% reduction in VUE compared to several baseline designs.
  arXiv  Detail & Related papers  (2020-01-22T08:51:05Z)

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.