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

• Task Delay and Energy Consumption Minimization for Low-altitude MEC via Evolutionary Multi-objective Deep Reinforcement Learning [52.64813150003228]
  The low-altitude economy (LAE), driven by unmanned aerial vehicles (UAVs) and other aircraft, has revolutionized fields such as transportation, agriculture, and environmental monitoring. In the upcoming six-generation (6G) era, UAV-assisted mobile edge computing (MEC) is particularly crucial in challenging environments such as mountainous or disaster-stricken areas. The task offloading problem is one of the key issues in UAV-assisted MEC, primarily addressing the trade-off between minimizing the task delay and the energy consumption of the UAV.
  arXiv  Detail & Related papers  (2025-01-11T02:32:42Z)
• Optimization of Flight Routes: Quantum Approximate Optimization Algorithm for the Tail Assignment Problem [0.0]
  The Tail Assignment Problem (TAP) is a critical optimization challenge in airline operations. This work applies the Quantum Approximate Optimization Algorithm (QAOA) to the TAP. The analysis reveals the current limitations of quantum hardware but suggests potential advantages as technology advances.
  arXiv  Detail & Related papers  (2024-12-17T10:35:26Z)
• Non-Myopic Multi-Objective Bayesian Optimization [64.31753000439514]
  We consider the problem of finite-horizon sequential experimental design to solve multi-objective optimization problems. This problem arises in many real-world applications, including materials design. We propose the first set of non-myopic methods for MOO problems.
  arXiv  Detail & Related papers  (2024-12-11T04:05:29Z)
• 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)
• 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.