Drone routing algorithm for package delivery

Introduction

Drone’s and drone delivery has been a hot topic over the last years. The number of startups related to Drone’s has significantly increased. The two big players Amazon and Google have been working for some time on drone delivery products. They have made a lot of progress with their two projects Amazon Prime Air and Google Wing.

Amazon made it’s first drone delivery in UK in December 7, 2016: https://www.amazon.com/Amazon-Prime-Air/b?ie=UTF8&node=8037720011

Google has been testing drone delivery in Australia since 2014 and now has lunched the first home delivery drone service in Australia: https://www.bbc.com/news/technology-47880288

The idea that now you can get orders delivered by drones is exciting for me, but for such thing to be possible there are a lot of technical problems to be solved. One of the problems that captured my attention was the routing algorithm for package delivery.

I first encountered this problem in the Qualification Round of Google Hash Code competition, we did our best to solve this problem but somehow was not enough and we did not qualify for the next round.
https://storage.googleapis.com/coding-competitions.appspot.com/HC/2016/hashcode2016_qualification_task.pdf

But this problem stick in my mind for some time, back then I was in my last year of my master’s degree and I needed to choose something to do for my master’s final project. Since I was challenged by the idea of drone delivery, I choose to design a drone delivery system. Since such kind of project is huge and requires lot of resources, I decided to focus only on the software part and mainly in the routing algorithm.

Today I would like to share with you, my solution to the problem from an algorithmic point of view.

You can see a demo of the final software project here: https://www.youtube.com/watch?v=lOUT-q7pIIE&t=5s

Also you can find the algorithm implemented in java here: https://github.com/kristo-godari/drone-delivery-routing-algorithm

Problem Statement

Given a fleet of drones, a list of customer orders, and availability of the individual products in warehouses schedule the drone operations so that the orders are completed as soon as possible. Orders can have multiple products, and products can be found in one or more warehouses. Drones are independent and given a specific order, which has a list of products, the warehouses coordinates where the products are stored and the client coordinates, they can do the delivery autonomous.

My approach for solving this problem is:

• All new customers orders that arrive will stay in a queue, we will call it orders_queue
• Each drone will have it’s own queue ex: drone_1_queue, drone_2_queue …
• A worker will process the orders_queue and will distribute orders to each drone individual queue
• Each drone takes the next order from their queue, pick up the products from the warehouses and deliver the order.
• We also will need to take in consideration that Drones will need to recharge from time to time.

The challenging part is that the worker that will process the orders_queue in order to distribute orders effectively and optimize the distribution, must know which drone offers the fastest delivery time for each order that it’s processing.

I chose to solve this problem with the help of graphs and shortest path algorithms. I started with Dijkstra's shortest path algorithm, and after some time realized that my graph will have always a specific pattern so I modified Dijkstra's algorithm to be more optimized for my use case.

Let’s see an example:
For the sake of the argument let’s presume that we have:
- Three drones(D1, D2, D3)
- Three warehouses(W1, W2, W3)
- Three clients(C1, C2, C3)

We would like to take a complicated scenario and try to solve it, in our case a complicated scenario is when all three drones are in the process of delivering parcels to their clients.
Drone D1 is delivering to C1, D2 to C2 and D3 to C3.
Now a new order shows for client 4 (C4), this order has tree products and these products can be found: Product 1 in W1, Product 2 in W2 and Product 3 in W3.
The drone that will deliver this order must pass through all three warehouses to pick the products and then go for delivery. With this data we can build the an example graph represented below:

This is a directed graph with edge weights. I have selected the edge weights randomly for the sake of the argument. Each edge between two nodes represents the time in minutes that a drone needs to fly from the first node to the second node.

In order to deliver this new order to client C4, each drone must finish first the current delivery than should go and pick up the products from all three warehouses and then go to C4 address for delivery.
We use the same logic for building the graph, we first start by connecting each drone to the clients that they are currently delivering, then we connect the clients to the warehouses, and connect warehouses to each other and at the end we connect the warehouses to C4.

The question is: Which drone D1, D2, D3 offers best time for delivering the new order arrived for C4?

To answer this question we start from the node C4 and try all routes combinations to find the drone that offers the fastest time for delivering this order. Why start from C4? the logical way would be start from each drone, and calculate the shortest path to C4, but this mean that we need to run the algorithm N times, where N is the no. of drones. Since we want to optimize, we want to go through the graph the least amount of times possible, in our case if we start from the C4 and go down the graph to the drones nodes, we have achieved our goal.

For the given example the Drone D2 is the winner with the route: D2->C2->W2->W3->W1->C4 with a distance of 14 minutes.

How we handle the case when the drone needs to be recharged or when it has N orders already in the queue?

After the drone will deliver the current order it needs to take the products for the new order from the warehouses, we know the time needed for the drone to arrive from the current client and each of the warehouses, and we add to this time: time for recharge, time needed to deliver all order that the drone may have in the queue, etc…

Let’s take the above example: D2->C2->W2->W3->W1->C4, the weight between C2 and W2 is 3 min. Let’s presume that this drone also has two orders in queue that we have estimated previously that will take 5 min and 8 min to deliver them, also the drone will need to stop for a recharge that will take 12 min. We can than add all this: 3+5+8+12=28 min. When we build the graph we must set the weight between C2 and W2 to 28. Maybe this time the Drone 2 doesn’t offer the best route, maybe another drone offers a faster time.
The point is that we have flexibility when building the graph to calculate the weights based on multiple factors not only the distance.

Performance

The number of warehouses and the no. of clients is important because it grows the number of combinations. The number of drones doesn’t impact the algorithm’s performance, because it doesn’t grow the no. of combinations.

Find below the results of my tests, for the scenario presented above, when you have N clients and all the drones are busy delivering to these clients, when a new order comes in, how much time does it take to find the drone that offers the fasted time :

• 100 clients and 10 mandatory warehouses = 77 sec
• 100 clients and 9 mandatory warehouses = 8 sec
• 100 clients and 8 mandatory warehouses = 951 ms
• 100 clients and 7 mandatory warehouses = 265 ms
• 100 clients and 6 mandatory warehouses = 68 ms
• 100 clients and 5 mandatory warehouses = 29 ms
• 100 clients and 1 mandatory warehouses = 1 ms

To calculate the number of combination that the algorithm tries we use the formula: W! * C (number of warehouses factorial multiplied by the number of clients). In our example that’s is: 3!*4 = 24 combinations. For a graph with 10 warehouses and 100 clients = (10!*100) that’s about 362,880,000 combinations.

If you have more than 10 warehouses (where is mandatory to pass throw all warehouses in order to complete a specific order) this algorithm becomes very slow and is not practical to use because the number of combinations to test is huge. Ex: for 11 warehouses there are 3,991,680,000 combinations.

By the no. of warehouses I mean the number of mandatory warehouses that a drone need to stop by to pick products for a specific order. In a real life case scenario this number should not be higher than 5 so the algorithms performs quite good.

Tests are done using an: Notebook / Laptop ASUS Gaming 17.3" ROG GL752VW, FHD, Intel® Core™ i7–6700HQ (6M Cache, up to 3.50 GHz), 16GB DDR4, 1TB 7200RPM + 128GB SSD, GeForce GTX 960M 4GB

Source: https://kristogodari.com/