Solving the Flying Sidekick Traveling Salesman Problem by a Simulated Annealing Heuristic

Vincent F. Yu, Shih-Wei Lin (), Panca Jodiawan and Yu-Chi Lai
Additional contact information
Vincent F. Yu: Department of Industrial Management, National Taiwan University of Science and Technology, Taipei 106335, Taiwan
Shih-Wei Lin: Department of Information Management, Chang Gung University, Taoyuan 33302, Taiwan
Panca Jodiawan: Department of Industrial Management, National Taiwan University of Science and Technology, Taipei 106335, Taiwan
Yu-Chi Lai: Department of Computer Science and Information Engineering, National Taiwan University of Science and Technology, Taipei 106335, Taiwan

Mathematics, 2023, vol. 11, issue 20, 1-21

Abstract: This study investigates the flying sidekick traveling salesman problem (FSTSP), in which a truck and an unmanned aerial vehicle work together to make deliveries. This study develops a revised mixed-integer linear programming (MILP) model for the FSTSP. The revised MILP model performs better than the existing model. Due to the FSTSP’s high complexity, we propose an effective heuristic based on simulated annealing (SA) to solve the problem. The novelty of the proposed SA heuristic lies in the new solution representation, which not only determines the visiting sequence of customers but also the service type of customers and rendezvous positions. Another feature of the proposed SA is a new operator specifically designed for the FSTSP. To evaluate the performance of the proposed SA heuristic, we conduct a comprehensive computational study where we fine-tune the parameters of the SA heuristic and compare the performance of the SA heuristic with several state-of-the-art algorithms including hybrid genetic algorithm (HGA) and iterated local search (ILS) in solving existing FSTSP benchmark instances. The results indicate that the proposed SA heuristic outperforms ILS and is statistically competitive with HGA. It obtains best-known solutions for all small FSTSP instances and 29 best-known solutions for the 60 large FSTSP instances, including 20 new best-known solutions.

Keywords: simulated annealing; traveling salesman problem; unmanned aerial vehicle; flying sidekick traveling salesman problem (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2023
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/2227-7390/11/20/4305/pdf (application/pdf)
https://www.mdpi.com/2227-7390/11/20/4305/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jmathe:v:11:y:2023:i:20:p:4305-:d:1260645

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().