研究成果 > アルゴリズムのデモ > 巡回セールスマン問題

巡回セールスマン問題 Traveling Salesman Problem (TSP)とは

この問題は,セールスマンが与えられたすべての都市をちょうど1度だけ訪れてもとに戻ってくるルート(巡回 路)のうちで最も移動距離の短いものを求めよ,という問題です(出発地点をどこに選んでも話は同じですね). このデモの例では,北米48都市, 532都市,TSPの文字を模った配列の105都市, 225都市に対する巡回セールスマ ン問題を扱っています.二つの都市間は直線距離で移動できるとします.

実は,最短の巡回路を求めるには膨大な時間がかかるため,局所探索法と呼ばれる簡便な方法で巡回路を計算し ます.最初に適当な巡回路(初期解と呼ぶ)からスタートし以下を反復します.巡回路の一部を変更し新しい巡 回路で移動距離の短いものが作れるかを調べます(この局所的な変更で改良されるかを調べることが局所探索で す).そして移動距離を改善する巡回路(改良解と呼ぶ)が見つかればこれに移ります.この一部の変更で移動 距離の改善ができなくなった時点で計算を止め,得られている巡回路を出力します.この巡回路が真に最短であ るとは言えないのですが,デモでは簡単な方法の割りにかなり最短に近い巡回路が得られることが分かります.

デモの説明

デモ TSP1 を選択してクリックすると48都市の問題例が呼び出され ます(TSP2, TSP3, TSP4 はそれぞれ都市数が 105, 225, 532 の問題例です).呼び出さ れた画面には各都市が緑の点で描かれ,黄色い線分がとりあえずの巡回路を表していて,これを初期解 (initial solution)としてスタートします.(この巡回路はランダムに選んであります.532都市では綿飴の ようですね.)実は,このデモでは最短巡回路の長さが(長い時間をかけた計算の末に)分かっていて,スター ト時の巡回路の長さ(tour length)が最短なものの何倍になっているかが画面右上の灰色のバー内に表示され ます.例えば,

  [initial] tour length = 54321 (+1234.5%)
となっていれば,それは初期解の長さが 54321km で,最短なものに比べ,相対誤差が1234.5パーセントである (つまり,1234.5%余分に長い,言い換えると最短なものの 12.345+1=13.345 倍の長さいということ)を意味し ています.アルゴリズムは,この初期解からはじめ,その一部を変更し改良解(前より長さの短い巡回路)を作っ ていきます.巡回路の変更の仕方は,第1段階で 2-opt 近傍と呼ばれる方法を用い,第2段階で Or-opt 近傍と 呼ばれる方法を用い,改良解が得られなくなった時点でアルゴリズムは終了します.(2-opt, Or-optについて は「高校生,高専生,学部生向け説明」の付録をご覧ください.)

遊び方

画面右上のバーの説明: 次の4色のバーが現れます.

灰色のバー [initial] tour length = 54321 (+1234.5%)
青色のバー [2-opt] tour length = 4457 (+9.5%)
紫色のバー [Or-opt] tour length = 4221 (+3.7%)
黄土色のバー [finish] tour length = 4221 (+3.7%)

これらの意味はそれぞれ以下の通りです.

灰色のバー: ランダムな初期解
青色のバー: 第1段階で2-opt近傍によって得られた改良解
紫色のバー: 第2段階でOr-opt近傍によって得られた改良解
黄土色のバー: 最終的に得られた解(表示中の解)

最短巡回路長からの相対誤差(%)を表しています. 青色,紫色,黄土色のバーは[play]ボタンを押し計算が始まってから表示されます. 探索が停止したとき黄土色のバーが表示されます. アルゴリズムは比較的単純なものですが, 最適解からの相対誤差がかなり小さくなって終了することが分かります(通常相対誤差数 % 以内). [init]ボタンを使って初期解をいろいろ変えて試してみてください.