The development of drones and autonomous vehicles inspires a bright vision for the future. Companies promise to deliver goods to your feet at any time. While bright dreams are only human, scientists must remain critical to separate valuable innovations from impractical marketing pitches. For example, what is the advantage of a drone that can be launched from a truck? Using clever mathematical tricks, researchers compute the increase in delivery speed with this technology.
The ability of drones to deliver goods is increasingly important to many companies. In 2013, the first plans for Amazon Prime Air were unveiled. In 2022, Wing Aviation LLC, a subsidiary of Google’s parent company Alphabet Inc., made over 50,000 deliveries by drone. In 2023, Zipline International Inc. made more than 800,000 commercial deliveries, including important medical supplies in Rwanda.
Small drones can carry limited weight and often perform a single delivery per flight. Compared to traditional trucks, this limited capacity is a disadvantage when many deliveries must be made. As drones fly back and forth between the warehouse and their delivery point, the total distance travelled exceeds an efficient route driven by a single truck. Furthermore, only deliveries within the flight range of a warehouse are possible.
'The ability of drones to deliver goods is increasingly important to many companies'
Since 2016, companies such as the US-based Workhorse have considered another idea: drones that can be launched from the roof of a truck. This combines the flexibility of drones with the capacity of a truck. Together with Prof. Niels Agatz and Prof. Marie Schmidt, I studied how efficient delivery routes for a truck and drone pair can be made. This allows them to compute the benefits of this emerging technology.
A challenging puzzle
The search for the best route among multiple deliveries is famously known as the travelling salesman problem and is a challenging puzzle. It is hard to show that no alternative route is better. One idea is to enumerate and check all routes. Unfortunately, even with 50 delivery locations, the number of routes is an astronomical number with more than 60 digits. Theoretically, even the fastest computers we can hope to build would need far longer than a human lifespan to check them all.
Decades of research related to the travelling salesman problem resulted in clever mathematical tricks to compute the gap-percentage of a route. This percentage indicates room for improvement. A gap of 0% indicates the best possible solution was found, whereas a small gap of for example 1% still indicates the efficiency of a route without the need for full enumeration. Even though the best solution is difficult to find in practice, the gap allows researchers to analyse the quality of delivery routes they do find.
We adapted these ideas for truck-and-drone routes. A key issue that we address is that the truck and drone must wait for each other; a complication that does not occur with single vehicles. In our research, we introduced building blocks for a rigorous way to construct and analyse routes. Using this idea, we developed software that computes the best possible or at least high-quality routes.
'On average, a set of deliveries can be serviced 30% faster by truck and drone compared to a single truck’
Faster service routes
With our software, we discovered that, on average, a set of deliveries can be serviced 30% faster by truck and drone compared to a single truck. We assume that the drone travels twice as fast as the truck and delivery locations are spread out uniformly. In case deliveries are concentrated around one or two centers with a few deliveries on the outskirts, the speed-up in service time becomes 38% on average. Our pioneering work is followed by various international researchers studying many aspects of drone transportation.
About Paul Bouman
Paul Bouman is an associate professor in the Department of Econometrics at Erasmus School of Economics. He has a background in Computer Science and enjoys working on algorithm design and the implementation of algorithms, in particular in the context of logistics and the allocation of scarce resources. He teaches courses on programming and computer skills.
- More information
This item is part of Backbone Magazine 2024. The magazine can be found in E-building or Theil-building for free. Additionally, a digital copy is available here. Backbone is the corporate magazine of Erasmus School of Economics. Since 2014, it is published once a year. The magazine highlights successful and interesting alumni, covers the latest economic trends and research, and reports on news, events, student and alumni accomplishments.
