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.

• Record URL:
  • https://doi.org/10.1016/j.trpro.2021.01.008
• Record URL:
  • http://www.sciencedirect.com/science/article/pii/S2352146521000120
• Availability:
  • Find a library where document is available. Order URL: http://worldcat.org/issn/23521465
• Supplemental Notes:
  • © 2021 Maurizio Boccia et al. Published by Elsevier B.V. Abstract reprinted with permission of Elsevier.
• Authors:
  • Boccia, Maurizio
  • Masone, Adriano
  • Sforza, Antonio
  • Sterle, Claudio
• Conference:
  • 23rd EURO Working Group on Transportation Meeting (EWGT 2020)
  • Location: Paphos , Cyprus
  • Date: 2020-9-16 to 2020-9-18
• Publication Date: 2021

Language

• English

Media Info

• Media Type: Web
• Features: References;
• Pagination: pp 51-58
• Serial:
  • Transportation Research Procedia
  • Volume: 52
  • Issue Number: 0
  • Publisher: Elsevier
  • ISSN: 2352-1465
  • Serial URL: http://www.sciencedirect.com/science/journal/23521465/
• Publication flags:

  Open Access (libre)

Subject/Index Terms

• TRT Terms: Delivery service; Delivery vehicles; Drones; Integer programming; Linear programming; Rural areas; Testing; Traveling salesman problem; Trucks; Urban areas; Variance
• Subject Areas: Data and Information Technology; Freight Transportation; Operations and Traffic Management; Planning and Forecasting; Vehicles and Equipment;

Filing Info

• Accession Number: 01765076
• Record Type: Publication
• Files: TRIS
• Created Date: Feb 19 2021 10:31AM