Optimization Approaches for the Traveling Salesman Problem with Drone

Niels Agatz, Paul Bouman, Marie Schmidt

Research output: Contribution to journalArticleAcademicpeer-review

530 Citations (Scopus)


The fast and cost-ecient home delivery of goods ordered online is logistically chal- lenging. Many companies are looking for new ways to cross the last-mile to their customers. One technology-enabled opportunity that recently has received much at- tention is the use of a drone 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 IP and develop several fast route rst-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 articial instances with dierent characteristics and sizes. Our experiments show that substantial savings are possible with this concept in comparison to truck-only delivery.
Original languageEnglish
Pages (from-to)965-981
Number of pages17
JournalTransportation Science
Issue number4
Publication statusPublished - 2018

Research programs



Dive into the research topics of 'Optimization Approaches for the Traveling Salesman Problem with Drone'. Together they form a unique fingerprint.

Cite this