ワイヤレスセンサーネットワークにおける最適ロボットルーティング問題

ユークリッド平面に散発的に分散されたセンサーのセットが与えられた場合、モバイルロボットはすべてのセンサーを訪れてデータをダウンロードし、最終的に基地に戻る必要があります。各センサーの有効範囲は円によって指定されており、ロボットは通信を開始するために少なくとも境界に到達しなければなりません。このシナリオにおける最適化の主な目標は、ロボットの移動距離を最小限に抑えることです。この問題は、近隣を持つ巡回セールスマン問題（TSPN）の特別なケースと見なすことができ、NP困難であることが知られています。本論文では、このクラスのTSPNに対して新しいTSPNアルゴリズムを提示し、最新の近似アルゴリズムに比べて顕著に改善された結果を得られることを示します。