散らかして逃げ切れ:円配置を伴う巡回セールスマン問題
Making a Complete Mess and Getting Away with it: Traveling Salesperson Problems with Circle Placement Variants
訪問した各地点の隣に円形障害物を置く制約下で、有効な閉路が存在する最大半径と最小巡回コストを求める問題(TSP-CP)を定式化し、Dubins車両版や自己消去グラフ上のTSPを含む新解法を提案した。
著者: David Woller, Masoumeh Mansouri, Miroslav Kulich
分類: cs.RO
原文アブストラクト
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.
