- 论文公开站arXiv
凸集图上Steiner旅行商问题的统一分支定界搜索
Unified Branch-and-Bound Search for the Steiner Traveling Salesman Problem on Graphs of Convex Sets
摘要提出了一种在凸集图（GCS）上求解Steiner旅行商问题（Steiner-TSP）的统一分支定界搜索方法，该问题要求寻找通过所需凸集的最小成本闭合轨迹，允许可选中转顶点和重复访问。通过根行走前缀的搜索，利用加性下界图成本和割分离连通流松弛来界定前缀和剩余成本。在均匀正成本假设下，最佳优先遍历在有限次扩展后终止，深度优先遍历在有限可行解存在时终止。对于用户指定的因子ε≥1，全局下界保证任一策略的解成本至多为全局最优的ε倍。在移动机械…
意义：为机器人路径规划等组合优化问题提供统一求解框架，兼顾最优性保证与计算效率，对AI决策与自动化领域有参考价值。