Ti trovi qui: Home » Online Resources » Exact Models for the FSTSP

Exact models for the FSTSP

M. Dell'Amico, R. Montemanni, S. Novellani

This paper presents three enhanced formulations for the Flying Sidekick Traveling Salesman Problem, where a truck and a drone cooperate to deliver parcels to customers minimizing the completion time. The drone can leave and must return to the truck after visiting one customer, performing flights not exceeding its battery endurance while the truck can serve other customers.
The new formulations allow to decrease the number of `big-M' constraints with respect to literature models and improve previous results by solving to optimality several benchmark instances for which an optimal solution was previously unknown. This paper also shows how to modify the new models to include several variants of the problem from the literature.

Find the results here and here.

Find Murray and Chu [1] instances here. We have used all the FSTSP instances and the PDSTSP instances with 20 customers. 

Find Poikonen et al. [2] instances here. The 100 9-customer instances could be found in file Table1LocationFull.csv and the 52 14-customer instances in file Table2LocationFull.csv. In file Table4LocationFull.csv could be found all instances with 9, 19, 29, 39, 49, 59, 69, 79, 89, 99, and 199 defined by Poikonen et al. In our paper we have only used those of size 9 and 19.

Please find the detailes of all the instances on our paper.

 

[1] Murray, C.C., Chu, A.G., 2015. The flying sidekick traveling salesman problem: Optimization of
  drone-assisted parcel delivery. Transportation Research Part C: Emerging Technologies 54, 86--109.

[2] Poikonen, S., Golden, B., Wasil, E.A., 2019. A branch-and-bound approach to the traveling salesman problem with a
  drone. INFORMS Journal on Computing 31, 2, 335--346.Poikonen, S., Golden, B., Wasil, E.A., 2019. A branch-and-bound approach to the traveling salesman problem with a drone. INFORMS Journal on Computing 31, 2, 335–346.nen, S., Golden, B., Wasil, E.A., 2019. A branch-and-bound approach to the traveling salesman problem with a drone. INFORMS Journal on Computing 31, 2, 335–346.