ニューラルネットワークを用いた分業TSPの解法

概要

論文の詳細を見る
ニユーラルネットワーク(以下NN)を用いて組合せ最適化問題を解く手法はNP完全問題の近似解高速解法として現在まで様々な研究がなされている。その応用例として有名なTSP(Traveling Salesman Problem)は、NNを用いて準最適解を現実的な時間内に解くことができるようになったので実用的に応用することが可能となった。しかし、TSPの解は単一のループであるために逐次型処理の問題のスケジューリングとしては応用できても、並列分散型処理のスケジューリングに対する解を要求される問題に対しての有用性を述ベた研究は見当たらない。しかし現実的には並列分散型処理のスケジューリングの要請が高まっている。そこで、本研究ではTSPを拡張した分業TSP(以下nTSP:n-Traveling Salesmen Problem)モデルを作り並列分散型のスケジューリングを解として要求される問題に対する高速解法の開発を行なっている。本稿ではnTSPの最も簡単な場合として2TSP(2人のセールスマンによる分業TSP)をNNを用いて近似的に解くモデルとそのシミュレーション結果を述べる。なお2TSPからnTSPへの拡張の方法についても述べる。
1994-03-07