给每个访问点加圆障碍，优化路径与障碍大小
Making a Complete Mess and Getting Away with it: Traveling Salesperson Problems with Circle Placement Variants
- 访问节点后放置圆形障碍，最大化障碍半径
- 新算法在路径质量上超越现有最优解
- 适用于采矿、采收等实际场景
本文研究旅行商问题的一种变体——环形障碍放置旅行商问题（TSP-CP），即每次访问节点后在其附近放置一个圆形障碍物。目标是最大化仍能存在有效闭合路径的障碍半径，并在此基础上最小化路径成本。该问题在采收、采石场及露天矿开采等实际场景中具有应用价值。本文提出了针对TSP-CP及其适用于杜宾斯车辆的变体，以及关键子问题——自删除图上的旅行商问题（TSP-SD）的新颖求解器。大量实验表明，所提方法在解的质量上优于现有最先进算法。
原文摘要 · Abstract (English)
This paper explores a variation of the Traveling Salesperson Problem, where the agent places a circular obstacle next to each node once it visits it. Referred to as the Traveling Salesperson Problem with Circle Placement (TSP-CP), the aim is to maximize the obstacle radius for which a valid closed tour exists and then minimize the tour cost. The TSP-CP finds relevance in various real-world applications, such as harvesting, quarrying, and open-pit mining. We propose several novel solvers to address the TSP-CP, its variant tailored for Dubins vehicles, and a crucial subproblem known as the Traveling Salesperson Problem on self-deleting graphs (TSP-SD). Our extensive experimental results show that the proposed solvers outperform the current state-of-the-art on related problems in solution quality.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。