A variable neighborhood search for flying sidekick traveling salesman problem

de Freitas, J. C., & Penna, P. H. V. · 2020

citation-level

This paper applies a general variable-neighborhood search to the flying sidekick TSP, starting from an optimal TSP tour. The journal issue is 2020; the article was published online in 2019. It is a reference for heuristic comparison, not a re-run done here.

After a solver produces a truck TSP tour, variable-neighborhood search turns it into truck and drone routes. Computational experiments are described as showing that delivery time can be improved substantially. A new instance set based on the TSP library is also provided.

The size of the improvement depends on the initial solution and the instances. The first stage is limited to sizes a TSP solver can finish in practical time. Operating approval and detailed energy are out of scope.