A Variable Neighborhood Search for Flying Sidekick Traveling Salesman Problem
This addresses delivery efficiency for logistics companies, but it is incremental as it builds on existing FSTSP methods.
The paper tackles the Flying Sidekick Traveling Salesman Problem (FSTSP) for drone-assisted parcel delivery by proposing a hybrid heuristic that uses an optimal TSP solution and General Variable Neighborhood Search to generate delivery routes, resulting in significant improvements in delivery time.
The efficiency and dynamism of Unmanned Aerial Vehicles (UAVs), or drones, present substantial application opportunities in several industries in the last years. Notably, the logistic companies gave close attention to these vehicles envisioning reduce delivery time and operational cost. A variant of the Traveling Salesman Problem (TSP) called Flying Sidekick Traveling Salesman Problem (FSTSP) was introduced involving drone-assisted parcel delivery. The drone is launched from the truck, proceeds to deliver parcels to a customer and then is recovered by the truck in a third location. While the drone travels through a trip, the truck delivers parcels to other customers as long as the drone has enough battery to hover waiting for the truck. This work proposes a hybrid heuristic that the initial solution is created from the optimal TSP solution reached by a TSP solver. Next, an implementation of the General Variable Neighborhood Search is used to obtain the delivery routes of truck and drone. Computational experiments show the potential of the algorithm to improve the delivery time significantly. Furthermore, we provide a new set of instances based on well-known TSPLIB instances.