Fly Slower to Reduce Drone Delivery Times? (Updated Sept. 30, 2020) – New research with Ritwik Raj reveals that flying drones at slower speeds can actually lead to a significant reduction in overall delivery times. Check out the pre-publication accepted paper (free), or download directly from the publisher (paywalled), for an explanation, and to see how truck travel distances, waiting times, and drone energy consumption are affected. All test problems are available for download (and source code for the heuristic is also now available).
Flying Sidekick Research Updates (Dec. 23, 2019) –
Our latest paper on the “multiple flying sidekicks traveling salesman problem” has been published in Transportation Research Part C. You may download the pre-publication version (free) or download directly from the publisher (paywalled). We’re also excited to share all test problems and source code for solving these problems.
Information about the original “flying sidekick” problem is described below. Test problems from that paper are available by email request.
In a 2015 paper, The Flying Sidekick Traveling Salesman Problem: Optimization of Drone-assisted Parcel Delivery, co-author Amanda Chu and I proposed two new extensions to the traveling salesman problem (TSP). The resulting problems pair traditional delivery trucks with unmanned aerial vehicles (UAVs, also known as drones).
These problems were motivated by the growing interest in the notion of delivery-by-drone. Of course Amazon has grabbed most of the headlines in this arena, but Google and DHL (among others) are also working on this concept.
Amazon Prime Air UAV (Photo: amazon.com)
Google’s Project Wing (photo: google.com)
DHL Parcelcopter (photo: dhl.com)
While technological advances in obstacle detection and avoidance are bringing us closer to the reality of having packages delivered to our front door by a flying robot, our focus is on overcoming some of the operational challenges associated with UAV-based delivery.
Figure 1: The traditional approach, where a delivery truck visits all customers.
Traditionally, packages are delivered to customers via a delivery truck. The optimal truck route, or sequence of customer visits, is determined by the solution of a TSP. Such a route is shown in Figure 1, where nine geographically disbursed customers are to be served from a single depot (that is, a warehouse or distribution center). Of course the truck must travel along the underlying road network; the arcs here are just indicative of the order in which the customers are visited.
Figure 2: Customers whose parcels are light enough to be carried by a UAV are shown in green boxes; the red nodes indicate customers whose parcels are either too heavy or require a signature.
Now, suppose that a fleet of UAVs is available to deliver packages to customers directly from the distribution center (à la Amazon Prime Air). Which UAV should deliver to each customer, if our goal is to minimize the time at which the last customer receives her parcel? What if some customers’ parcels are too heavy to be carried by a drone, or if a signature is required? What if some customers are outside of the drone’s flight range? Our nine customers are now shown in Figure 2.
[Note: Although our paper addresses the case of a fleet of UAVs operating from the depot, we’ll assume for the purpose of this discussion that only a single UAV is available.]
Figure 3: One UAV serves each eligible customer (dashed arcs), while the remaining customers must be served by the delivery truck.
Since customers 1, 3-6, and 8 (green customers within the UAV flight range) are UAV-eligible, one approach is to use the UAV to deliver to each of these customers directly from the depot. Customers 2, 7, and 9 will need to be served by the delivery truck. This solution is shown in Figure 3.
Comparing the traditional approach with the UAV-facilitated approach, we see a noticeable time savings (Figure 4).
Figure 4: This combined Gantt chart shows the time to complete deliveries to each customer. The bottom chart shows the timing of the TSP solution (with only a truck). The top chart shows the schedule for a single UAV and a truck.
However, this is a rather naïve approach that assigns the UAV to all UAV-eligible customers. It turns out that it might not be optimal to operate the system in this manner. In particular, the optimization problem we wish to solve is a combination of a parallel identical machine scheduling problem and a traveling salesman problem. Both of these problems are well-studied in the academic literature, but we’re not aware of anyone who has combined them.
There are three parts to this problem, which we call the “parallel drone scheduling traveling salesman problem” (PDSTSP):
- A set partitioning problem to determine which customers should be served by the UAVs. The remaining customers will be served by the traditional delivery truck.
- A parallel identical machine scheduling problem to determine which customers are served by each particular UAV. The objective is to minimize the “makespan” (latest time of completion).
- A TSP to determine the sequence of customers to be visited by the truck.
Figure 5: An optimized assignment of customers to either the UAV or the delivery truck.
Returning to our example problem, the optimal solution to the PDSTSP is shown in Figure 5. Note that customers 6 and 8 are UAV-eligible, but are served by the truck instead. This balances the total service time for both the UAV and the delivery truck. Comparing the three approaches, we see that this optimized plan provides significant time savings (Figure 6).
Figure 6: The top chart shows the optimal schedule for a single UAV and a truck. Notice that this represents a significant reduction in delivery times.
Our paper provides a mathematical programming formulation for the PDSTSP. Unfortunately, due to the computational complexity of this problem (both the parallel machine scheduling problem and the TSP are NP-hard), it’s not practical to use integer programming software to solve this problem optimally.
Instead, we propose a relatively simple yet effective heuristic to find high-quality (near optimal) solutions within a reasonable time limit. Details on the heuristic are provided in the paper.
THE FLYING SIDEKICK TSP
The PDSTSP is appropriate when the distribution center is centrally located (i.e., if the DC were located in the middle of a large metropolitan area). However, operating a DC downtown would be expensive. Furthermore, in densely populated areas, most customers live in high-rise apartment complexes (where it would be really difficult for a UAV to find the front door to drop a package).
So, we turn our attention to the case where the distribution center is remotely located, as shown in Figure 7.
Figure 7: The depot is located too far away from the customers to allow direct UAV flights from the depot. The two red customers have packages that are too heavy to be carried by a UAV.
Suppose we pair a traditional delivery truck with a UAV. As the truck is making deliveries, it can launch a UAV to work in tandem. This extends the effective range of the UAV, allowing it to visit remote customers. We dub this problem the “flying sidekick TSP” (FSTSP). A solution to the FSTSP is shown in Figure 8.
Figure 8: The delivery truck departs from the depot carrying all customer parcels and a UAV. When the truck reaches customer 4, the delivery driver launches the UAV to serve customer 7. Meanwhile, the truck proceeds to customer 6, where it retrieves the UAV. Later, the UAV also visits customer 1.
The time savings associated with the FSTSP approach, versus a traditional TSP solution (where the truck must visit each customer) is highlighted below:
We’re already hard at work developing extensions to these models. Please shoot me an e-mail if you have any questions or comments.
Reference:
- C.C. Murray and A.G. Chu*, “The Flying Sidekick Traveling Salesman Problem: Optimization of Drone-assisted Parcel Delivery,” Transportation Research Part C: Emerging Technologies, 54, 86-109, 2015. download | doi