A Variable Neighborhood Search for Flying Sidekick Traveling Salesman Problem

  • 2018-10-18 16:31:52
  • Julia C. Freitas, Puca Huachi V. Penna
  • 0

Abstract

The efficiency and dynamism of Unmanned Aerial Vehicles (UAVs), or drones,present substantial application opportunities in several industries in the lastyears. Notably, the logistic companies gave close attention to these vehiclesenvisioning reduce delivery time and operational cost. A variant of theTraveling Salesman Problem (TSP) called Flying Sidekick Traveling SalesmanProblem (FSTSP) was introduced involving drone-assisted parcel delivery. Thedrone is launched from the truck, proceeds to deliver parcels to a customer andthen is recovered by the truck in a third location. While the drone travelsthrough a trip, the truck delivers parcels to other customers as long as thedrone has enough battery to hover waiting for the truck. This work proposes ahybrid heuristic that the initial solution is created from the optimal TSPsolution reached by a TSP solver. Next, an implementation of the GeneralVariable Neighborhood Search is used to obtain the delivery routes of truck anddrone. Computational experiments show the potential of the algorithm to improvethe delivery time significantly. Furthermore, we provide a new set of instancesbased on well-known TSPLIB instances.

 

Quick Read (beta)

loading the full paper ...