In a recent paper, The Flying Sidekick Traveling Salesman Problem: Optimization of Drone-assisted Parcel Delivery, co-author Amanda Chu and I propose 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.
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.
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.
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.]
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).
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.
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).
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.
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.
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.
- 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