Testing Quantum and Simulated Annealers on the Drone Delivery Packing Problem

• URL: http://arxiv.org/abs/2406.08430v1
• Date: Wed, 12 Jun 2024 17:16:02 GMT
• Title: Testing Quantum and Simulated Annealers on the Drone Delivery Packing Problem
• Authors: Sara Tarquini, Daniele Dragoni, Matteo Vandelli, Francesco Tudisco,
• Abstract summary: Drone delivery packing problem (DDPP) arises in the context of logistics in response to an increasing demand in the delivery process along with the necessity of lowering human intervention. We propose two alternative formulations of the DDPP as a quadratic unconstrained binary optimization (QUBO) problem. We perform extensive experiments showing the advantages as well as the limitations of quantum annealers for this optimization problem.
• Score: 6.246837813122577
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Using drones to perform human-related tasks can play a key role in various fields, such as defense, disaster response, agriculture, healthcare, and many others. The drone delivery packing problem (DDPP) arises in the context of logistics in response to an increasing demand in the delivery process along with the necessity of lowering human intervention. The DDPP is usually formulated as a combinatorial optimization problem, aiming to minimize drone usage with specific battery constraints while ensuring timely consistent deliveries with fixed locations and energy budget. In this work, we propose two alternative formulations of the DDPP as a quadratic unconstrained binary optimization (QUBO) problem, in order to test the performance of classical and quantum annealing (QA) approaches. We perform extensive experiments showing the advantages as well as the limitations of quantum annealers for this optimization problem, as compared to simulated annealing (SA) and classical state-of-the-art commercial tools for global optimization.

Related papers

• Covert Multicast in UAV-Enabled Wireless Communication Systems With One-hop and Two-hop Strategies [8.702721247072429]
  We study the time of covert multicast in a wireless communication system facilitated by Unmanned Aerial Vehicle (UAV) We propose one (OH) particle swarm (PSO) based algorithm and an exhaustive framework for performance modeling for the transmission scheme and TH scheme, respectively. The efficiency of the proposed PSO-based algorithm is substantiated through extensive numerical results.
  arXiv  Detail & Related papers  (2024-10-16T06:46:30Z)
• UAV-enabled Collaborative Beamforming via Multi-Agent Deep Reinforcement Learning [79.16150966434299]
  We formulate a UAV-enabled collaborative beamforming multi-objective optimization problem (UCBMOP) to maximize the transmission rate of the UVAA and minimize the energy consumption of all UAVs. We use the heterogeneous-agent trust region policy optimization (HATRPO) as the basic framework, and then propose an improved HATRPO algorithm, namely HATRPO-UCB.
  arXiv  Detail & Related papers  (2024-04-11T03:19:22Z)
• A Feasibility-Preserved Quantum Approximate Solver for the Capacitated Vehicle Routing Problem [3.0567007573383678]
  The Capacitated Vehicle Routing Problem (CVRP) is an NP-optimization problem (NPO) that arises in various fields including transportation and logistics. We present a new binary encoding for the CVRP, with an objective function of minimizing the shortest path that bypasses the vehicle capacity constraint of the CVRP. We discuss the effectiveness of the proposed encoding under the framework of the variant of the Quantum Alternating Operator Ansatz.
  arXiv  Detail & Related papers  (2023-08-17T05:14:43Z)
• Multi-Objective Optimization for UAV Swarm-Assisted IoT with Virtual Antenna Arrays [55.736718475856726]
  Unmanned aerial vehicle (UAV) network is a promising technology for assisting Internet-of-Things (IoT) Existing UAV-assisted data harvesting and dissemination schemes require UAVs to frequently fly between the IoTs and access points. We introduce collaborative beamforming into IoTs and UAVs simultaneously to achieve energy and time-efficient data harvesting and dissemination.
  arXiv  Detail & Related papers  (2023-08-03T02:49:50Z)
• Hybrid Genetic Algorithm and Mixed Integer Linear Programming for Flying Sidekick TSP [0.39373541926236766]
  This work presents a hybrid Genetic Algorithm (HGenFS) for optimizing a variation of the Traveling Salesman Problem (TSP) called Flying Sidekick TSP (FSTSP) The results obtained confirmed that the adopted formulation for the exact solution is suitable for solving problems up to ten customers. The HGenFS proved to be capable of finding optimal solutions for the FSTSP in a few seconds by incorporating specifics and a local search phase.
  arXiv  Detail & Related papers  (2023-04-26T21:19:36Z)
• Light Unbalanced Optimal Transport [69.18220206873772]
  Existing solvers are either based on principles or heavy-weighted with complex optimization objectives involving several neural networks. We show that our solver provides a universal approximation of UEOT solutions and obtains its generalization bounds.
  arXiv  Detail & Related papers  (2023-03-14T15:44:40Z)
• Low-rank Optimal Transport: Approximation, Statistics and Debiasing [51.50788603386766]
  Low-rank optimal transport (LOT) approach advocated in citescetbon 2021lowrank LOT is seen as a legitimate contender to entropic regularization when compared on properties of interest. We target each of these areas in this paper in order to cement the impact of low-rank approaches in computational OT.
  arXiv  Detail & Related papers  (2022-05-24T20:51:37Z)
• Drone Flocking Optimization using NSGA-II and Principal Component Analysis [0.8495139954994114]
  Individual agents in natural systems like flocks of birds or schools of fish display a remarkable ability to coordinate and communicate in local groups. Emulating such natural systems into drone swarms to solve problems in defence, agriculture, industry automation and humanitarian relief is an emerging technology. optimized flocking of drones in a confined environment with multiple conflicting objectives is proposed.
  arXiv  Detail & Related papers  (2022-05-01T09:24:01Z)
• Tuning Particle Accelerators with Safety Constraints using Bayesian Optimization [73.94660141019764]
  tuning machine parameters of particle accelerators is a repetitive and time-consuming task. We propose and evaluate a step size-limited variant of safe Bayesian optimization.
  arXiv  Detail & Related papers  (2022-03-26T02:21:03Z)
• 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)
• Dynamic Resource Management for Providing QoS in Drone Delivery Systems [2.578242050187029]
  We study the dynamic UAV assignment problem for a drone delivery system with the goal of providing measurable Quality of Service (QoS) guarantees. We take a deep reinforcement learning approach to obtain a dynamic policy for the re-allocation of the UAVs. We evaluate the performance of our proposed algorithm by considering three broad arrival classes, including Bernoulli, Time-Varying Bernoulli, and Markov-Modulated Bernoulli arrivals.
  arXiv  Detail & Related papers  (2021-03-06T03:11:07Z)

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.