Testing Quantum and Simulated Annealers on the Drone Delivery Packing Problem

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.

arXiv comment16 pages, 6 figures, 7 tables

References in corpus (15)

• Supplementary information for "Quantum supremacy using a programmable superconducting processor"
• Ising formulations of many NP problems
• Quantum Annealing in the Transverse Ising Model
• Adiabatic Quantum Computing
• Characterizing Quantum Supremacy in Near-Term Devices
• Quantum Computing based Hybrid Solution Strategies for Large-scale Discrete-Continuous Optimization Problems
• Quantum versus Classical Annealing of Ising Spin Glasses
• Prospects for Quantum Enhancement with Diabatic Quantum Annealing
• Flight Gate Assignment with a Quantum Annealer
• Penalty Weights in QUBO Formulations: Permutation Problems
• Hybrid quantum annealing for larger-than-QPU lattice-structured problems
• Analytical solution for nonadiabatic quantum annealing to arbitrary Ising spin Hamiltonian
• Quantum-Assisted Solution Paths for the Capacitated Vehicle Routing Problem
• Viewing Vanilla Quantum Annealing Through Spin Glasses
• Adiabatic theorem for finite dimensional quantum mechanical systems