Article: Monday, 30 April 2018
With next-day delivery and even same-day delivery becoming standard, companies like Amazon and Alibaba are experimenting with drone technology to quickly get packages into the hands of customers. Early testing focuses on the practical question of how this can be done, but we took a step back to ask whether it is worth doing at all. Using a combination of a traditional delivery truck and a companion drone, our model says yes.
Delivery trucks can cover a lot of ground and carry a lot of packages. Drones are light, unrestricted by traffic, and soon won’t need a dedicated human operator. Combine the two and the result is a complementary delivery unit that can reduce the total route time by an average of 30-38 per cent compared to using a truck alone.
We developed a scalable model, published in our paper Optimization Approaches for the Traveling Salesman Problem with Drone, that calculates the best possible route a delivery truck can take to allow both the truck and its drone to deliver packages to customer locations. The solution shows which customers are served by the drone and which ones by the truck. The wait times required by either the truck or the drone for their companion to rejoin them are factored in, and real-life information, like the limitations of a specific model of drone, can be included as it presents itself.
Amazon was my first inspiration on this question. They’ve been testing drones for years and even filed a patent related to using lamp posts as drone docking stations. But later I found a reference to research conducted by the University of Cincinnati, working with a company that builds electric trucks. They were specifically looking at the problem of combining the use of delivery drones with regular trucks, but from an aeronautical engineering point of view. These engineers mainly focussed on the “how” questions: ‘How do I get a drone to land on top of the truck; how do I load the package on the drone; how can a drone ring the doorbell?’
My co-authors and I became more interested in the “why” questions. Sure, using drones to deliver packages is an interesting idea – and it’s certainly fun to play with drones to test the theories – but what does it really mean for someone who has to perform these deliveries; what are the practical benefits (if any) for a provider who needs to coordinate the drone, truck, customer and delivery?
One of the biggest benefits to a delivery provider is saving time. In all of the computer experiments we ran, the truck/drone combination showed a significant time saving over using a truck alone. When our customers were randomly scattered the truck/drone pair was 30 per cent faster than a truck alone. And when our customers were grouped in one or two areas – particularly relevant in cities with high-density housing – with just a few customers scattered outside the main group, our drone was able to deliver to the outlying customers while the delivery driver worked through the main cluster. Here we reduced the total time taken by even more: 38 per cent faster than the same route using only a truck.
In short, across the board we could eliminate a third of the time normally spent delivering packages across the “last mile”.
The “last mile” is the distance between the final package depot and the customer. This small but significant distance has always been the most expensive part of any delivery. Planning the logistics of moving packages from the supplier to warehouses and delivery depots is relatively easy – there are many packages and reliable patterns that allow for predictions. But the delivery of a single package from the last transport hub to a customer’s hands can account for more than 25 per cent of the total cost of delivery. Other factors like road congestion, pollution, and the potential danger to a delivery driver constantly on the road add to the urgency of reducing the resource load of this last mile.
The travelling salesman problem is a classic problem in applied mathematics. Traditionally a travelling salesman has multiple cities or customers to visit. The main challenge is to find the optimal sequence of these visits to spend the least possible amount of time, or travel the smallest possible distance. The travelling salesman is a good starting point to study truck-and-drone routing, as it is a fundamental underlying problem in many real-life routing problems. Even if you have multiple vehicles to coordinate, the routing problem of each individual truck and drone pair can be represented by the travelling salesman problem.
We didn’t include real parameters as there simply aren’t any yet. This field is so new that no one is really using drones in delivery (with a couple of notable exceptions: DHL in Germany already uses a drone to deliver medical supplies to one of the islands in the North Sea, and China uses drones to deliver goods to isolated mountain villages).
Without real-life usage there is no data on how, for example, a drone will perform if you are delivering to a high-rise building. But the model we developed can take these factors into account. Equally, other details like the type of truck, the type of drone, the speed of the vehicles is simply input.
To all intents and purposes this model is not theoretical – you could incorporate it in practical route planning tools to begin using drones.Delivery companies have been using tools like route-planning software for years. In some cases this produces interesting results. For example, the delivery company UPS has used their software to develop and refine the “right turn only” method that, in countries that drive on the right, eliminates all but the most necessary left turns. This unusual approach has saved UPS between US$300-400 million each year in fuel, personnel and vehicle running costs, as well as the human cost of statistically more dangerous left-hand turns.
But there are so many practical limitations on the use of drones (safety, privacy, air space) that even Amazon’s tests sometimes seem to be designed more for publicity than practicality. While there a still many practical and legal hurdles to be overcome before drone delivery becomes a reality, the model we developed works equally well for other robotic delivery options that might be easier to deploy. Right now, for example, a company called Starship is testing the use of droids to deliver parcels in various cities in the United States. The droids move at human speeds and use the pavement rather than the road or the skies.
Obviously it makes no sense to send a walking-pace robot out from a distant depot to deliver goods; but combine a few of these droids with a delivery truck and our model shows a significant potential increase in the efficiency of the delivery route; an efficiency gain that could be implemented tomorrow.
Rotterdam School of Management (RSM)
This article is based on the paper: Optimization Approaches for the Traveling Salesman Problem with Drone: written by Niels Agatz, Paul Bouman, and Marie Schmidt. Forthcoming in Transportation Science (STAR).
RSM offers Executive Education and Master programmes in various business areas for any stage of your career. For instance:
Corporate Communications & PR Manager
Science Communication and Media Officer
Rotterdam School of Management, Erasmus University (RSM) is one of Europe’s top-ranked business schools. RSM provides ground-breaking research and education furthering excellence in all aspects of management and is based in the international port city of Rotterdam – a vital nexus of business, logistics and trade. RSM’s primary focus is on developing business leaders with international careers who can become a force for positive change by carrying their innovative mindset into a sustainable future. Our first-class range of bachelor, master, MBA, PhD and executive programmes encourage them to become to become critical, creative, caring and collaborative thinkers and doers. www.rsm.nl
For more information about RSM or this article, please contact Danielle Baan, Media Officer for RSM, via +31 10 408 2028 or baan@rsm.nl.