The skies are becoming increasingly busy, not just with traditional aircraft, but with a new fleet of silent, electric couriers: delivery drones. Companies like Amazon Prime Air and DHL Parcel-copter are already exploring or deploying unmanned aerial vehicles (UAVs) to transport packages directly to customers. They offer a practical solution to real-world problems like traffic congestion and carbon emissions, offering a low per-mile cost and requiring no human intervention for the actual delivery. However, the dream of widespread drone delivery faces significant hurdles, primarily the limited battery life of drones and their capacity to carry only lightweight parcels.
How can we assign parcels to different drones to get everything delivered as quickly as possible? This is what a team of researchers from the Indian Institute of Science (IISc), Bengaluru, and the University of Birmingham, UK, set out to solve.
Did You Know? Drones were used effectively in the fight against COVID-19, delivering millions of vaccines and medical supplies across the globe. Given their life-saving potential, use cases for medical supplies in particular have become the most widely tested type of drone delivery, with trials and pilot projects in dozens of countries. |
The researchers tackled what is called the Drone Warehouse Problem (DWP). It is a challenge so complex that it belongs to a class of problems known as NP (nondeterministic polynomial)-hard. In simple terms, for an NP-hard problem, finding the absolute best solution becomes incredibly difficult and time-consuming as the number of items or variables grows. Instead of seeking a perfect solution that might take an impossibly long time, researchers focus on developing a fast approximation algorithm, one that finds a good solution in a reasonable amount of time.
Their breakthrough is an algorithm that guarantees parcel delivery in the least amount of time. Surprisingly, the delivery time of the algorithm can be expressed in terms of the golden ratio or ϕ (phi), where ϕ is approximately 1.62. The golden ratio is a mathematical constant found throughout nature, art, and even the human body, often associated with aesthetic beauty and efficiency. Their algorithm achieves this impressive performance in near-linear time, which means it can handle very large numbers of parcels and drones much more efficiently than previous methods.
The core of their solution lies in adapting a classic scheduling strategy called the Longest Processing Time First (LPT) heuristic. If there are several tasks to do and several people to do them, LTP is a way to give the longest tasks to the people who finish earliest. The researchers modified this approach to account for the unique constraints of drones, such as their battery life and varying speeds. The parcels are first sorted by their distance from the warehouse (longest distance first), and the drones are sorted by their battery life. Then, parcels are assigned one by one to the drone that can deliver them and will finish its current tasks earliest.
The team also used a concept from computational geometry called the dynamic maintenance of lower envelope lines to speed up the LPT algorithm, while maintaining its performance. This means that as the number of drones and parcels increases, their algorithm's performance degrades much, much slower than previous methods, making it scalable for real-world applications with massive datasets.
While many general vehicle routing solutions or simpler heuristics exist for parcel delivery, they often don’t fully account for the unique characteristics of drones, like limited battery life and varying capabilities. While some use complex mathematical programming (MIP) formulations, these are often too slow for large-scale problems. The new algorithm optimises for both these factors and provides strong theoretical guarantees on its performance. The team, however, acknowledge that the sophisticated data structures used for this near-linear time might be complex for immediate practical implementation. They also pose open questions for future research, such as whether the algorithm's speed can be further optimised or if the approximation ratio can be improved.
The study nevertheless offers a powerful new tool for optimising drone-based parcel delivery, a field that is rapidly expanding. By developing a highly efficient and provably effective algorithm, the scientists are helping to pave the way for a future of seamless logistics. As drone technology continues to advance and regulations evolve, algorithms like this will be crucial in making widespread, sustainable, and rapid parcel delivery a reality, transforming how goods move from warehouses to our doorsteps.
This article was written with the help of generative AI and edited by an editor at Research Matters.