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.