Optimization Approaches for the Traveling Salesman Problem with Drone

By Niels A. H. Agatz, P. Bouman, M. Schmidt. Transportation Science, 2016

959 citations recorded by the source corpus.

The fast and cost-efficient home delivery of goods ordered online is logistically challenging. Many companies are looking for new ways to cross the last mile to their customers. One technology-enabled opportunity that recently has received much attention is the use of drones to support deliveries. An innovative last-mile delivery concept in which a truck collaborates with a drone to make deliveries gives rise to a new variant of the traveling salesman problem TSP that we call the TSP with drone. In this paper, we model this problem as an integer program and develop several fast route-first, cluster-second heuristics based on local search and dynamic programming. We prove worst-case approximation ratios for the heuristics and test their performance by comparing the solutions to the optimal solutions for small instances. In addition, we apply our heuristics to several artificial instances with different characteristics and sizes. Our experiments show that substantial savings are possible with this concept compared to truck-only delivery. The online appendix is available at https://doi.org/10.1287/trsc.2017.0791 .

Subfields: Automotive Engineering, Management of Technology and Innovation

View Paper: https://www.semanticscholar.org/paper/1112cb5d327e4cd50b07e353298ca5c0aa094bb5

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Automotive Engineering

In Management of Technology and Innovation

Citations in the corpus

A Comparative Analysis of the Environmental Benefits of Drone-Based Delivery Services in Urban and Rural Areas (2018, background): “[21] proposed a model to solve the travelling salesman problem in the context of drone delivery.”
Coordinated Logistics with a Truck and a Drone (2018, background): “The recent papers [5, 22, 35] all describe mixed integer programming formulations and heuristic algorithms for solving several optimization problems in 3”
Supply, demand, operations, and management of crowd-shipping services: A review and empirical evidence (2019, background): “Advanced technology development may introduce unmanned aerial vehicles (UAVs) or drones (Bouman et al., 2017; Poikonen et al., 2017; Wang et al., 2017; Agatz et al., 2018; Otto et al., 2018), robots, and automated vehicles (Chung et al.”
Applications and Research avenues for drone-based models in logistics: A classification and review (2021, methodology): “The model and algorithm are used to solve several problem instances from (Murray and Chu, 2015; Agatz et al., 2018; Ha et al., 2018).”
The multiple flying sidekicks traveling salesman problem: Parcel delivery with multiple drones (2020, methodology): “For example, Agatz et al. (2018) provided a new MILP model for the TSP-D, as well as several route first-cluster second heuristics. Ponza (2016), Ha et al. (2018), Freitas and Penna (2018), Daknama and Kraus (2017), and Schermer et al. (2018) explored neighborhood search based heuristics, while Boum”
A concise guide to existing and emerging vehicle routing problem variants (2019, background): “(2017), and Agatz et al. (2018) consider a delivery configuration in which a drone, mounted on a vehicle, detaches itself to perform deliveries while the vehicle keeps moving.”
An adaptive large neighborhood search metaheuristic for the vehicle routing problem with drones (2019, background): “Within the last-mile delivery concept, in which a truck collaborates with a drone to make deliveries, there are more problems that are worth noting, such as the TSP-D (Agatz et al., 2015).”
The vehicle routing problem with drones: Extended models and connections (2017, background): “, see [1, 10]) propose computational approaches to address special cases of the VRPD.”