A new MILP formulation for the flying sidekick traveling salesman problem
Maurizio Boccia, Andrea Mancuso, Adriano Masone, Claudio Sterle
University of Naples Federico II National Research Council Istituto di Analisi dei Sistemi ed Informatica Antonio Ruberti
阅读操作
确认中在文库中上传 PDF 后可生成中文音频讲解。
摘要与影响
Nowadays, truck‐and‐drone problems represent one of the most studied classes of vehicle routing problems. The Flying Sidekick Traveling Salesman Problem ( FS‐TSP ) is the first optimization problem defined in this class. Since its definition, several variants have been proposed differing for the side constraints related to the operating conditions and for the structure of the hybrid truck‐and‐drone delivery system. However, regardless the specific problem under investigation, determining the optimal solution of most of these routing problems is a very challenging task, due to the vehicle synchronization issue. On this basis, this work provides a new arc‐based integer linear programming formulation for the FS‐TSP . The solution of such formulation required the development of a branch‐and‐cut solution approach based on new families of valid inequalities and variable fixing strategies. We tested the proposed approach on different sets of benchmark instances. The experimentation shows that the proposed method is competitive or outperforms the state‐of‐the‐art approaches, providing either the optimal solution or improved bounds for several instances unsolved before.
逐年被引趋势
关键指标
同类平均 = 1
同领域 · 同年份 · 同类型
Google Scholar 与 OpenAlex 的被引统计范围不同,数值存在差异属正常。
AI 辅助阅读
依据:摘要
可就本文提问;依据不足时会说明。
学术脉络
学科主题
工程Vehicle Routing Optimization Methods
Facility Location and Emergency Management · Complexity and Algorithms in Graphs