Solving a Real-World Package Delivery Routing Problem Using Quantum Annealers

• URL: http://arxiv.org/abs/2403.15114v3
• Date: Fri, 28 Jun 2024 11:49:51 GMT
• Title: Solving a Real-World Package Delivery Routing Problem Using Quantum Annealers
• Authors: Eneko Osaba, Esther Villar-Rodriguez, Antón Asla,
• Abstract summary: This research focuses on the conjunction between quantum computing and routing problems. The main objective of this research is to present a solving scheme for dealing with realistic instances.
• Score: 0.44241702149260353
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Research focused on the conjunction between quantum computing and routing problems has been very prolific in recent years. Most of the works revolve around classical problems such as the Traveling Salesman Problem or the Vehicle Routing Problem. The real-world applicability of these problems is dependent on the objectives and constraints considered. Anyway, it is undeniable that it is often difficult to translate complex requirements into these classical formulations.The main objective of this research is to present a solving scheme for dealing with realistic instances while maintaining all the characteristics and restrictions of the original real-world problem. Thus, a quantum-classical strategy has been developed, coined Q4RPD, that considers a set of real constraints such as a heterogeneous fleet of vehicles, priority deliveries, and capacities characterized by two values: weight and dimensions of the packages. Q4RPD resorts to the Leap Constrained Quadratic Model Hybrid Solver of D-Wave. To demonstrate the application of Q4RPD, an experimentation composed of six different instances has been conducted, aiming to serve as illustrative examples.

Related papers

• Solving rescheduling problems in heterogeneous urban railway networks using hybrid quantum-classical approach [0.157286095422595]
  We build an integer linear model for the given problem and solve it with D-Wave's quantum-classical hybrid solver. The proposed approach is demonstrated on a real-life heterogeneous urban network in Poland.
  arXiv  Detail & Related papers  (2023-09-13T07:19:32Z)
• Solving Logistic-Oriented Bin Packing Problems Through a Hybrid Quantum-Classical Approach [0.44241702149260353]
  Bin Packing Problem is a classic problem with wide industrial applicability. We resort to our previously published quantum-classical framework known as Q4RealBPP.
  arXiv  Detail & Related papers  (2023-08-05T04:36:33Z)
• Optimization of Image Acquisition for Earth Observation Satellites via Quantum Computing [0.786197460675312]
  Satellite image acquisition scheduling is a problem that is omnipresent in the earth observation field. We present two QUBO formulations for the problem, using different approaches to handle the non-trivial constraints. We also provide practical guidelines on the size limits of problem instances that can be realistically solved on current quantum computers.
  arXiv  Detail & Related papers  (2023-07-26T18:00:02Z)
• 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)
• Semantic-aware Modular Capsule Routing for Visual Question Answering [55.03883681191765]
  We propose a Semantic-aware modUlar caPsulE framework, termed as SUPER, to better capture the instance-specific vision-semantic characteristics. We comparatively justify the effectiveness and generalization ability of our proposed SUPER scheme over five benchmark datasets.
  arXiv  Detail & Related papers  (2022-07-21T10:48:37Z)
• Supply Chain Logistics with Quantum and Classical Annealing Algorithms [0.0]
  Noisy intermediate-scale quantum (NISQ) hardware is almost universally incompatible with full-scale optimization problems of practical importance. We investigate a problem of substantial commercial value, multi-truck vehicle routing for supply chain logistics, at the scale used by a corporation in their operations. Our work gives a set of techniques that can be adopted in contexts beyond vehicle routing to apply NISQ devices in a hybrid fashion to large-scale problems of commercial interest.
  arXiv  Detail & Related papers  (2022-05-09T17:36:21Z)
• 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)
• Q-Match: Iterative Shape Matching via Quantum Annealing [64.74942589569596]
  Finding shape correspondences can be formulated as an NP-hard quadratic assignment problem (QAP) This paper proposes Q-Match, a new iterative quantum method for QAPs inspired by the alpha-expansion algorithm. Q-Match can be applied for shape matching problems iteratively, on a subset of well-chosen correspondences, allowing us to scale to real-world problems.
  arXiv  Detail & Related papers  (2021-05-06T17:59:38Z)
• Error mitigation and quantum-assisted simulation in the error corrected regime [77.34726150561087]
  A standard approach to quantum computing is based on the idea of promoting a classically simulable and fault-tolerant set of operations. We show how the addition of noisy magic resources allows one to boost classical quasiprobability simulations of a quantum circuit.
  arXiv  Detail & Related papers  (2021-03-12T20:58:41Z)
• First Steps: Latent-Space Control with Semantic Constraints for Quadruped Locomotion [73.37945453998134]
  Traditional approaches to quadruped control employ simplified, hand-derived models. This significantly reduces the capability of the robot since its effective kinematic range is curtailed. In this work, these challenges are addressed by framing quadruped control as optimisation in a structured latent space. A deep generative model captures a statistical representation of feasible joint configurations, whilst complex dynamic and terminal constraints are expressed via high-level, semantic indicators. We validate the feasibility of locomotion trajectories optimised using our approach both in simulation and on a real-worldmal quadruped.
  arXiv  Detail & Related papers  (2020-07-03T07:04:18Z)
• A Quantum Annealing Approach for Dynamic Multi-Depot Capacitated Vehicle Routing Problem [5.057312718525522]
  This paper presents a quantum computing algorithm that works on the principle of Adiabatic Quantum Computation (AQC) It has shown significant computational advantages in solving optimization problems such as vehicle routing problems (VRP) when compared to classical algorithms. This is an NP-hard optimization problem with real-world applications in the fields of transportation, logistics, and supply chain management.
  arXiv  Detail & Related papers  (2020-05-26T01:47:39Z)

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.