返回主页Multi-tabu

Multi-tabu

广义旅行商问题的多起点限时邻域搜索

2024.10 — 2024.11

3D 求解演示

每组选择一个点,走完所有组再回到起点。试试换一组点,看看搜索怎样缩短路线。

种子 42 · 7 组 · 24 个候选点

分组候选点

当前长度
—
初始长度
—
已找到的最短长度
—
1 组2 组3 组4 组5 组6 组7 组

搜索预算为 0.6 秒。回放保留实际改进与部分中间步骤,3D 高度仅用于区分选中点,距离按平面坐标计算。

项目介绍

广义旅行商问题同时要决定每组选哪个点,以及按什么顺序访问。路径长度包括从最后一个点回到起点的距离。

比较质心、原点距离与多次贪心初始化。每轮尝试交换顺序、重新插入、反转片段或替换组内选点,限时内可以从新的初始解继续搜索。

我的工作

独立完成算法设计、实验与竞赛提交;仓库保留可复现样例、约束检查和路径可视化。

  • 欧氏距离矩阵与分组可行解
  • 多起点贪心初始化
  • swap / relocate / reverse / swap_within_layer
  • 限时搜索与真实样例结果记录

竞赛记录

竞赛记录420 + 815.62

算法巅峰专项赛前四题满分 420 分、第五题 815.62 分。

竞赛荣誉国家级一等奖

全球校园人工智能算法精英大赛算法巅峰专项赛。

使用说明

  • 当前候选筛选尚未使用禁忌表,实际采用多起点随机邻域搜索。
  • 限时搜索返回本次找到的最短路径。运行时间和搜索轮数会随服务器负载变化。