针对动态成本旅行商问题，提出快速启发式算法，适合实时路径规划。
A Fast GRASP Metaheuristic for the Trigger Arc TSP with MIP-Based Construction and Multi-Neighborhood Local Search
- 用MIP将问题转为一系列定制化TSP实例进行构造
- 60秒内平均差距仅0.77%，比已知最优解更优
- 适合状态依赖成本的实时路由场景，如仓库调度
触发弧旅行商问题（TA-TSP）在经典TSP基础上引入动态弧成本，当特定‘触发’弧被遍历时成本会改变，适用于可压缩存储系统的仓储操作建模。本文提出一种基于GRASP的元启发式算法，结合多种构造启发式与多邻域局部搜索。构造阶段采用混合整数规划（MIP）技术，将TA-TSP转化为一系列定制化TSP实例；优化阶段应用2-Opt、Swap和Relocate算子。在MESS 2024竞赛数据集上的计算实验显示，60秒内平均最优性间隙分别为0.77%和0.40%。在较小合成数据集上，该方法在相同时间内所得解比Gurobi求解器提升11.3%。算法在MESS 2024中位列前三，证明其在具有状态依赖旅行成本的实时路径规划中的适用性。
原文摘要 · Abstract (English)
The Trigger Arc Traveling Salesman Problem (TA-TSP) extends the classical TSP by introducing dynamic arc costs that change when specific "trigger" arcs are traversed, modeling scenarios such as warehouse operations with compactable storage systems. This paper introduces a GRASP-based metaheuristic that combines multiple construction heuristics with a multi-neighborhood local search. The construction phase uses mixed-integer programming (MIP) techniques to transform the TA-TSP into a sequence of tailored TSP instances, while the improvement phase applies 2-Opt, Swap, and Relocate operators. Computational experiments on MESS 2024 competition instances achieved average optimality gaps of 0.77% and 0.40% relative to the best-known solutions within a 60-second limit. On smaller, synthetically generated datasets, the method produced solutions 11.3% better than the Gurobi solver under the same time constraints. The algorithm finished in the top three at MESS 2024, demonstrating its suitability for real-time routing applications with state-dependent travel costs.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。