移動障害物を伴う移動目標巡回セールスマン問題のための二段階二重レベル探索
Two-Phase Bilevel Search for the Moving-Target Traveling Salesman Problem with Moving Obstacles
移動する目標を時間窓内で訪問しつつ、移動障害物を回避する経路を計画する問題に対し、混合整数錐計画法と高速な二段階探索アルゴリズムを提案し、既存手法より高品質な解を短時間で得られることを示した。
詳しい要約
1. どんなもの？
2. 先行研究と比べてどこがすごい？
3. 技術・手法の肝は？
4. どうやって有効だと検証した？
5. 議論はある？
6. 次に読むべき論文は？
※ AIが要旨から生成した要約です。正確性は原文をご確認ください。
著者: Allen George Philip, Anoop Bhat, Sivakumar Rathinam, Howie Choset
分類: cs.RO, cs.AI, math.CO, math.OC
原文アブストラクト
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.
