On the Hardness of the Drone Delivery Problem

Simon Bartlmae, Andreas Hene, Kelin Luo · 2025

Read On the Hardness of the Drone Delivery Problem by Simon Bartlmae, Andreas Hene, Kelin Luo (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2502-15194.txt.

Introduction

Simon Bartlmae, Andreas Hene, and Kelin Luo study how hard drone delivery is in a 2025 paper. Fast shipping leans on smart routes, and fleets of drones, trucks, and ships can pass a parcel hand to hand. Each craft moves on its own part of the map and at its own speed, so the best chain is hard to find.

The team weighs the task's true cost in math terms, on special maps and with curbed craft kinds. They treat cases with set start posts and free ones alike. Their results sort which forms of the task can be solved fast, and which stay hard no matter the tool.

Catalog record

CREATORSimon Bartlmae, Andreas Hene, Kelin Luo
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE60 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2502-15194

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

On the Hardness of the Drone Delivery Problem Simon Bartlmae, Andreas Hene, Kelin Luo Abstract Fast shipping and efficient routing are key problems of modern logistics. Building on previous studies that address package delivery from a source node to a destination within a graph using multiple agents (such as vehicles, drones, and ships), we investigate the complexity of this problem in specialized graphs and with restricted agent types, both with and without predefined initial positions. Particularly, in this paper, we aim to minimize the delivery time for delivering a package. To achieve this, we utilize a set of collaborative agents, each capable of traversing a specific subset of the graph and operating at varying speeds. This challenge is encapsulated in the recently introduced Drone Delivery Problem with respect to delivery time (DDT). In this work, we show that the DDT with predefined initial positions on a line is NP-hard, even when considering only agents with two distinct speeds. This refines the results presented by Erlebach, et al. [ 10 ] , who demonstrated the NP-hardness of DDT on a line with agents of arbitrary speeds. Additionally, we examine DDT in grid graphs without predefined initial positions, where each drone can freely choose its starting position. We show that the problem is NP-hard to approximate within a factor of O ⁡ ( n 1 − ε CLOSE O(n^{1-\varepsilon} ), where n n is the size of the grid, even when all agents are restricted to two different speeds as well as rectangular movement areas. We conclude by providing an easy O ⁡ ( n ) O(n) approximation algorithm. 1 Introduction With the rapid growth in e-commerce it becomes increasingly more important for logistics companies to deliver packages to customers as fast as possible. The Prime Air project, launched by Amazon [ 16 ] , introduces a new approach to parcel delivery. The German logistics company DHL has tested the delivery of medical supplies, such as blood samples, using flying mobile agents. When it comes to areas which are not connected to a well-formed infrastructure or areas threatened by war, delivery of crucial goods as medicine and food can help people in need [ 1 , 12 ] . The collaborative delivery aspect of the drone delivery problem, which involves multiple agents on a single delivery path, primarily arises from variations in agent speed [ 4 ] , consumption rates [ 3 ] , or constraints such as battery power [ 2 ] and movement areas [ 10 ] . In this paper, we further refine the model introduced by Erlebach et al. [ 10 ] . When it comes to their model, each agent’s movement is confined to its designated area. Specifically, agents are allowed unrestricted movement within their respective subgraphs. This setting is motivated by realistic drone delivery scenarios where airspace is regulated by licenses, restricting certain drones to specific regions. Additionally, it is a natural observation that different types of agents, such as ships, drones, and trucks, are capable of traversing distinct parts of the graph. In addition, each drone operates at designated speeds and has its own consumption rate. Although both objectives – minimizing delivery time and reducing consumption – have been extensively studied, our research will exclusively focus on minimizing delivery time. We define this particular challenge as the Drone Delivery Problem with respect to time (DDT). In this work we will focus on paths and grid graphs. We refer to the fastest delivery on a line as DDT-Line (Drone Delivery on a Line) and the fastest delivery on a grid as DDT-Grid. Our work is primarily of theoretical interest and has the potential to lead to more generalized applications. Considering paths is theoretically significant, as they are the simplest form of graphs, and practically relevant, especially for fast last-mile delivery of critical goods, such as medical supplies. The grid graph setting is particularly applicable to densely populated areas such as large towns. Related Work. The delivery problem has been extensively studied through various models, including the Shortest Path Problem [ 13 ] , the Traveling Salesperson Problem (TSP) [ 14 ] , the Vehicle Routing Problem [ 15 ] , and Dial-a-Ride Problem [ 9 ] . All these models assume that each request, whether a single node or a pair of nodes, is served by a single vehicle. Our study focuses on the collaborative delivery problem, involving multiple agents (servers, drones, etc.) in a single delivery process. This topic is inspired by the need for efficiency, aiming for faster or energy-efficient deliveries, and accommodating constraints like battery limitations and movement restrictions. The primary motivation is to optimize delivery paths, reducing consumption. Bärtschi et al. [ 4 ] first explored the delivery of a package from a source node to a target node with the aim of minimizing delivery time. They demonstrated that the problem can be solved in time O(k^{2}m+kn^{2}+\text{APSP}) for a single package, where n is the number of vertices, m is the number of edges, k is the number of agents and APSP represents the time required to compute all-pairs shortest paths in a graph with n nodes and m edges. Carvalho et al. [ 6 ] improved the time complexity by developing an algorithm that runs in O(kn\log n+km) time. Interestingly, they demonstrated that the problem escalates to NP-hardness with the addition of a second package. To minimize energy consumption in package delivery, Bärtschi et al. [ 4 ] developed a polynomial-time algorithm for delivering a single package, but demonstrated NP-hardness for multiple packages. They also investigated optimizing delivery time and energy for a single package. Lexicographically minimizing (time, energy) is polynomially feasible [ 5 ] , but minimizing any combination of time and energy proves to be NP-hard [ 4 ] . Considering the realistic scenario where each agent has limited working time or energy, which restricts its total distance traveled, exploring a collaborative path utilizing multiple agents to deliver packages becomes particularly valuable [ 7 , 8 , 2 ] . Chalopin et al. [ 7 ] first demonstrated that the energy-constrained drone delivery problem is NP-hard in general graphs. Subsequently, Chalopin et al. [ 8 ] showed that this variant remains NP-hard even on a path graph. Bärtschi et al. [ 2 ] found that a variant requiring each agent to return to its initial location is solvable in polynomial time for tree networks. Our study, as well as the research in [ 10 ] , diverges fundamentally from studies constrained by energy budgets. In our case, each agent’s travel distance is not confined by a strict budget but is restricted to a specific subgraph where it can travel unlimited distances. As a result, the hardness results and algorithmic findings from studies with energy constraints do not directly translate to our problem. Erlebach et al. [ 10 ] first introduced this movement-restricted model. They demonstrate that for collaborative agents with restricted movement areas, it is NP-hard to approximate the Drone Delivery Time (DDT) within O(n^{1-\varepsilon}) or O(k^{1-\varepsilon}) on general graphs, even if agents have equal speeds. For the case without initial positioning, they show that no polynomial time approximation with a finite ratio exists unless P = NP. Additionally,

Read the complete text