每日 Arxiv

本页面整理了世界各地发表的人工智能相关论文。
本页面使用 Google Gemini 汇总而成，并以非盈利为基础运营。
论文版权归作者及相关机构所有，分享时请注明出处。

基于 MIP 构造和多邻域局部搜索的触发弧 TSP 快速 GRASP 元启发式算法

Created by
  • Haebom

作者

琼·萨尔夫·索勒 (Joan Salv a Soler)，格雷瓜尔·兰伯特 (Lambertye)

大纲

本文介绍了一种基于 GRASP 的元启发式算法，用于求解触发弧旅行商问题 (TA-TSP)。该算法考虑了动态弧成本，并在构建阶段利用混合整数规划 (MIP) 将 TA-TSP 转换为一系列 TSP 实例。在优化阶段，该算法使用 2-Opt、Swap 和 Relocate 算子进行局部探索。在 MESS 2024 竞赛实例中，该算法在 60 秒内实现了相对于最优解 0.77% 和 0.40% 的平均差距；在小型合成数据集上，其性能比 Gurobi 求解器高出 11.3%。

Takeaways, Limitations

•
Takeaways：
◦
为TA-TSP问题提供有效的解决方案
◦
MESS 2024 竞赛前三名
◦
经验证适用于实时路由应用
◦
比 Gurobi 求解器性能更好
•
Limitations：
◦
论文中没有具体说明Limitations。
👍
Made with Slashpage