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

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...

Full description

Bibliographic Details
Main Authors: Vincent F. Yu, Shih-Wei Lin, Panca Jodiawan, Yu-Chi Lai
Format: Article
Language:English
Published: MDPI AG 2023-10-01
Series:Mathematics
Subjects:
Online Access:https://www.mdpi.com/2227-7390/11/20/4305
_version_ 1827720508049719296
author Vincent F. Yu
Shih-Wei Lin
Panca Jodiawan
Yu-Chi Lai
author_facet Vincent F. Yu
Shih-Wei Lin
Panca Jodiawan
Yu-Chi Lai
author_sort Vincent F. Yu
collection DOAJ
description 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.
first_indexed 2024-03-10T21:04:28Z
format Article
id doaj.art-217b91258e874b1aa6172f6d1ef556f6
institution Directory Open Access Journal
issn 2227-7390
language English
last_indexed 2024-03-10T21:04:28Z
publishDate 2023-10-01
publisher MDPI AG
record_format Article
series Mathematics
spelling doaj.art-217b91258e874b1aa6172f6d1ef556f62023-11-19T17:14:07ZengMDPI AGMathematics2227-73902023-10-011120430510.3390/math11204305Solving the Flying Sidekick Traveling Salesman Problem by a Simulated Annealing HeuristicVincent F. Yu0Shih-Wei Lin1Panca Jodiawan2Yu-Chi Lai3Department of Industrial Management, National Taiwan University of Science and Technology, Taipei 106335, TaiwanDepartment of Information Management, Chang Gung University, Taoyuan 33302, TaiwanDepartment of Industrial Management, National Taiwan University of Science and Technology, Taipei 106335, TaiwanDepartment of Computer Science and Information Engineering, National Taiwan University of Science and Technology, Taipei 106335, TaiwanThis 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.https://www.mdpi.com/2227-7390/11/20/4305simulated annealingtraveling salesman problemunmanned aerial vehicleflying sidekick traveling salesman problem
spellingShingle Vincent F. Yu
Shih-Wei Lin
Panca Jodiawan
Yu-Chi Lai
Solving the Flying Sidekick Traveling Salesman Problem by a Simulated Annealing Heuristic
Mathematics
simulated annealing
traveling salesman problem
unmanned aerial vehicle
flying sidekick traveling salesman problem
title Solving the Flying Sidekick Traveling Salesman Problem by a Simulated Annealing Heuristic
title_full Solving the Flying Sidekick Traveling Salesman Problem by a Simulated Annealing Heuristic
title_fullStr Solving the Flying Sidekick Traveling Salesman Problem by a Simulated Annealing Heuristic
title_full_unstemmed Solving the Flying Sidekick Traveling Salesman Problem by a Simulated Annealing Heuristic
title_short Solving the Flying Sidekick Traveling Salesman Problem by a Simulated Annealing Heuristic
title_sort solving the flying sidekick traveling salesman problem by a simulated annealing heuristic
topic simulated annealing
traveling salesman problem
unmanned aerial vehicle
flying sidekick traveling salesman problem
url https://www.mdpi.com/2227-7390/11/20/4305
work_keys_str_mv AT vincentfyu solvingtheflyingsidekicktravelingsalesmanproblembyasimulatedannealingheuristic
AT shihweilin solvingtheflyingsidekicktravelingsalesmanproblembyasimulatedannealingheuristic
AT pancajodiawan solvingtheflyingsidekicktravelingsalesmanproblembyasimulatedannealingheuristic
AT yuchilai solvingtheflyingsidekicktravelingsalesmanproblembyasimulatedannealingheuristic