提出新算法解决动态目标与障碍物下的巡检路径优化问题
Two-Phase Bilevel Search for the Moving-Target Traveling Salesman Problem with Moving Obstacles
- 分两阶段的双层搜索算法，兼顾效率与解质量
- 在40个目标和40个障碍场景中成功率超基线，耗时更低
- 适合无人机、自动驾驶等需避障的动态路径规划场景
移动目标旅行商问题（MT-TSP）旨在为从固定出发点出发的代理寻找最小成本轨迹，使其在各自的时间窗内访问一组移动目标并返回起点。本文研究了带有移动障碍物的移动目标旅行商问题（MT-TSP-MO），即代理轨迹必须避开移动障碍物。我们提出了一个可使用现成求解器解决的混合整数锥规划（MICP）模型，以及一种快速且可扩展的两阶段双层搜索（TPBS）算法，用于计算高质量可行解。我们在包含最多40个目标和40个障碍物的广泛问题实例上对所提方法与现有基线算法进行了对比评估。结果表明，两种方法在成功率、解成本和计算时间方面均显著优于基线。
原文摘要 · Abstract (English)
The Moving-Target Traveling Salesman Problem (MT-TSP) seeks a minimum cost trajectory for an agent that departs from a static depot, visits a set of moving targets, each within one of their assigned time windows, and returns to the depot. In this article, we study the Moving-Target Traveling Salesman Problem with Moving Obstacles (MT-TSP-MO), a generalization of the MT-TSP where the agent trajectory must avoid moving obstacles. We present a Mixed-Integer Conic Programming (MICP) formulation that can be solved using off-the-shelf solvers, as well as a fast and scalable Two-Phase Bilevel Search (TPBS) algorithm that computes high-quality feasible solutions for the problem. We evaluate our approaches against an existing baseline algorithm on a broad range of problem instances with up to 40 targets and 40 obstacles. The results demonstrate that both the proposed methods significantly outperform the baseline with respect to success rates, solution costs, and computation time.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。