站内快照 · 国内可打开。外网原文可能无法访问。
- 论文公开站arXiv
凸集图上Steiner旅行商问题的统一分支定界搜索
Unified Branch-and-Bound Search for the Steiner Traveling Salesman Problem on Graphs of Convex Sets
摘要提出了一种在凸集图（GCS）上求解Steiner旅行商问题（Steiner-TSP）的统一分支定界搜索方法，该问题要求寻找通过所需凸集的最小成本闭合轨迹，允许可选中转顶点和重复访问。通过根行走前缀的搜索，利用加性下界图成本和割分离连通流松弛来界定前缀和剩余成本。在均匀正成本假设下，最佳优先遍历在有限次扩展后终止，深度优先遍历在有限可行解存在时终止。对于用户指定的因子ε≥1，全局下界保证任一策略的解成本至多为全局最优的ε倍。在移动机械臂检查任务中，该方法同时选择感知模式、访问顺序和连续轨迹，并处理LTL_f动作前提。两种遍历策略在30秒内找到所有基准实例的可行解，平均认证最优性差距分别为28.1%和29.7%，而两个近期基线仅在约一半实例上成功。
意义：为机器人路径规划等组合优化问题提供统一求解框架，兼顾最优性保证与计算效率，对AI决策与自动化领域有参考价值。