Optimization Approaches for the Traveling Salesman Problem with Drone

Niels Agatz (), Paul Bouman () and Marie Schmidt ()
Additional contact information
Niels Agatz: Rotterdam School of Management, Erasmus University, 3062 PA Rotterdam, Netherlands
Paul Bouman: Econometric Institute, Erasmus University, 3062 PA Rotterdam, Netherlands
Marie Schmidt: Rotterdam School of Management, Erasmus University, 3062 PA Rotterdam, Netherlands

Transportation Science, 2018, vol. 52, issue 4, 965-981

Abstract: 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.

Keywords: traveling salesman problem; vehicle routing; drones; delivery (search for similar items in EconPapers)
Date: 2018
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (118)

Downloads: (external link)
https://doi.org/10.1287/trsc.2017.0791 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ortrsc:v:52:y:2018:i:4:p:965-981

Access Statistics for this article

More articles in Transportation Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().