Solving the Flying Sidekick Traveling Salesman Problem by a Simulated Annealing Heuristic
Vincent F. Yu, Shih-Wei Lin, Panca Jodiawan, Yu‐Chi Lai
National Taiwan University of Science and Technology Ming Chi University of Technology Chang Gung University Keelung Chang Gung Memorial Hospital
阅读操作
确认中在文库中上传 PDF 后可生成中文音频讲解。
摘要与影响
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.
逐年被引趋势
关键指标
同类平均 = 1
同领域 · 同年份 · 同类型
Google Scholar 与 OpenAlex 的被引统计范围不同,数值存在差异属正常。
AI 辅助阅读
依据:摘要
可就本文提问;依据不足时会说明。
学术脉络
学科主题
工程Vehicle Routing Optimization Methods
Metaheuristic Optimization Algorithms Research · Facility Location and Emergency Management