■巡回セールスマン問題(TSP)とは?
簡単にいうと,複数の都市を,最も短い距離でまわる順番を求める問題です．セールスマンは,なるべく短い距離で都市間を移動することにより,効率的にセールスを行うことができます．
■巡回セールスマン問題(TSP)はどのような事柄に応用されるか
巡回セールスマン問題といっても,セールスマンのみに有用な問題ではありません．巡回セールスマン問題は実際に次の事柄に応用されています．
・基盤穴あけ
・スケジューリング
・ルーティング
・運搬経路計画
最も有名であるものとして基盤の穴あけが挙げられます．基盤の穴あけで,複数の穴をあける場合を考えてみます．1つの穴あけを終わり次の穴をあけようとするとき,ドリルまたは基盤の移動が必要になります．当然，この移動には時間がかかります．よってこの穴あけの順番によって移動距離は変わり,速く終了する順番,遅く終了する順番が発生します．一枚の基盤を完成させる時間の数秒かもしれません．しかし,工場では何千,何万枚という基盤が作られます．工場にとっては数秒の時間の差が,大きな時間のロス,生産性低下,無駄な機器稼働経費浪費につながるのです．
■何故このような古くさい問題が未だに研究されているか
通常,コンピュータで,ある事柄に最も適した組み合わせを求める場合,全ての組み合わせを検索し,最もよいものを求めます．都市数Nの巡回路の組み合わせは(N-1)!/2通りとなります．つまり,(N-1)!/2種類の組み合わせ全部の経路の長さを調べて,比較し,たった一つの組み合わせを見つけるわけです．(N-1)!/2通りという数にピンと来ないかもしれませんが,とてつもない数です．例えば,10都市の巡回路の組み合わせは,9×8×7×6×5×4×3×2×1÷2=181440通りとなります．今時のコンピュータでも,15都市の最短巡回路を求めるために,何時間もかかってしまいます．16都市,17都市となると何日というレベルに達します．このようなことから,TSPは未だに解を求めるために良い方法が見つかっておらず,様々なアプローチで研究されているのです．またTSPは遺伝的アルゴリズムやニューラルネットワークなどのベンチマーク問題としてもよく用いられています．
|
