A Random Restart Local Search Matheuristic for the Flying Sidekick Traveling Salesman Problem

Drones and unmanned vehicles in general are gaining more and more interest in the logistic sector, due to the potential economic advantages they can provide. In this paper we focus on optimizing the use of a drone in conjunction with a truck for urban deliveries, dealing with what is called the flying sidekick traveling salesman problem. There is a set of customers that it is possible to serve either by a truck or by a drone. The target is to minimize the total time required to complete deliveries to all the customers. In this paper we show how an effective and simple random restart local search heuristic algorithm can be derived from a known mixed integer programming model for the problem.