近年，過疎地における安価な通信インフラや，被災地における緊急用ネットワークの確立などが求められている．このような環境では既存の有線に基づく通信インフラが存在しない，もしくは一時的に利用できない．その結果，エンドエンド間での通信経路が必ずしも常時存在するとは限らないことから，無線通信可能な移動ノードによるデータの中継を基盤とした遅延耐性ネットワーク(DTN: Delay Tolerant Network)の利用が検討されている．本研究では，フェリーと呼ばれる特別な移動ノードが，各ノードと外部ネットワークとの間の仲介を行うフェリー支援型DTNを想定する．これは前述の安価な通信インフラのシナリオに相当する．ここで，外部ネットワークへのアクセス回線を有するノードをシンク，近接するノードの集まりをクラスタと呼ぶ．クラスタは村や拠点などと見なすことができ，複数のクラスタが共通のシンクを利用して外部ネットワークとの通信を実現する．これまでに，1台のフェリーとシンク，地理的に離れた複数のクラスタからなるシステムにおいて，各ノードで発生したデータがフェリーによってシンクに届けられるまでの平均配送遅延を最小化するための最適なフェリーのクラスタ訪問順序が検討されてきた．さらに，クラスタ数の増加に対するスケーラビリティの確保のために，システム全体を複数のグループに分割する方式も検討されている．ただし，各グループは1台のシンクとフェリー，複数のクラスタ群からなるものとする．このグループ化問題は施設配置問題の一種であるが，目的関数がグループ全体の平均配送遅延を表す非線形関数となっている．元々の施設配置問題ではクラスタに相当する顧客とシンクに相当する施設間の距離の総和もしくは最大距離を最小化することが目的であり，この問題自体がNP完全であることが知られている．したがって，グループ化問題も同様にNP完全となる．本研究では，クラスタ群が大規模な場合にもグループ化問題を解くことのできる手法を提案する．具体的には，局所探索で一般的に用いられるシフト近傍操作と交換近傍操作とランダム探索を組み合わせた手法を提案する．シミュレーション評価により，提案手法を用いることで汎用の非線形ソルバを用いた場合と同等の結果をより短時間に得られることを示す．

泉 芳明, フェリー支援型DTNにおける大規模クラスタ群グループ化手法, Ph.D. Dissertation, 大阪大学, 学士学位論文, March 2013.