An Exact Approach for a Variant of the FS-TSP

In this work the authors focus on the flying sidekick traveling salesman problem (FS-TSP). The FS-TSP arises in the last-mile distribution context and it is a variant of the TSP aimed at determining the distribution plan of a driver-operated truck assisted by a drone (unmanned aerial vehicle, UAV), where the synchronization between the two vehicles allows to parallelize the delivery operations, so providing a reduction of the overall completion time. Several variants of the FS-TSP have been considered in literature, most of them sharing the assumption that launching and rendezvous position of a drone sortie must be different. In this work, the authors relax this assumption allowing the truck to wait for the drone at the launching position (FS-TSP*). This introduces an important flexibility element to deal with deliveries in rural or in urban areas with no-fly zones. The authors propose an original and compact integer linear programming formulation which allows to exactly solve the FS-TSP* and consequently also the FS-TSP. The results on several test instances show that the authors method can effectively solve to optimality instances with up to 20 customers and quantify the advantages of the FS-TSP* with respect to FS-TSP in terms of overall completion time.


  • English

Media Info

Subject/Index Terms

Filing Info

  • Accession Number: 01765076
  • Record Type: Publication
  • Files: TRIS
  • Created Date: Feb 4 2021 4:37PM