Optimization approaches for the traveling salesman problem with drone

Agatz, N., Bouman, P., & Schmidt, M. · 2018

full-text

This paper helped fix the name traveling salesman problem with drone and the route-first, cluster-second way of assigning drone customers. It is distinguished from a pure computational note because it also discusses worst-case approximation ratios. The card records the citation and the standard claim, and does not certify a fresh reading of the full PDF.

It models truck-drone collaboration as an integer program and proposes heuristics based on local search and dynamic programming. Small instances are compared with optimal solutions, and larger artificial instances are compared with truck-only delivery. Under those experimental settings, the authors argue that substantial savings are possible.

The size of any saving depends on assumptions about speed ratio, endurance, and customer layout. A result that savings are possible is not a promise of the same ratio in every city. Regulation and multi-drone operations sit outside this formulation.