Traveling Salesman Problem

巡回セールスマン問題（TSP）とは、例えばセールスマンが得意先を一度づつまわって会社へ戻ってくるまでの巡回路を探す問題のことで、得意先がNあるとすると巡回路の組み合わせがN!通り存在するため、得意先の数が増えてくると巡回路の組み合わせはものすごい数になります。なので、最短の巡回路を求めることが非常に難しいです。（当然Nが小さければ求まります。）そんなわけで現在、多項式時間での厳密解法のみつかっていない（多分、存在しない）NP-困難な問題です。多項式時間で求まる厳密解法が存在しなければ、条件を変えないで精度を保証した多項式時間での解法もみつかることはありません。

ちなみに純粋なTSPはさほど実用的ではないようで、実際には様々な条件の下で研究されているようです。

たとえば、ユークリッド空間上の地点というように問題を狭めれば精度を保証した解法は存在することが示されています。しかし、精度を保証した解法よりも精度を保証しない解法の方がよい性能を示すことが多いです。ここでいくつかの近似解法を以下に挙げます。

構築法（tour construction method）

巡回路が与えられない状態から、巡回路を求める方法

• 貪欲法(greedy, multiple fragment)
• セービング法(saving method)
• 最近追加法(nearest addition method)
• 最近挿入法(nearest insertion method)
• 最安挿入法(cheapest insertion method)
• 最遠挿入法(farther insertion method)
• christofides
• 空間充填曲線法(spacefilling curve metod)
• バケット法

改善法（improvement method, local method）

巡回路が与えられた状態から、よりコストの小さい巡回路を求めていく方法

• 2-Opt近傍 - 枝2本を付け替える手法
• Or-opt近傍 - 部分路を別の場所に挿入する手法（3-Optに含まれると思われる）
• 3-opt近傍 - 枝を3本付け替える手法
• convex hull insertion

改善法を用いれば確かに精度は向上しますが、厳密解に収束するわけではなく局所最適解が求まることが多いのです。また局所最適解か厳密解を判断することも難しいです。構築法での巡回路の精度が良いほど、改善法を適用した巡回路が良くなるわけではなく、最適解と共有する辺が多いほうがいいようです。

代表的な改善法(Improvement method)のλ-Optの特徴を以下に挙げます。

• λの数だけ辺をつなぎ変えて巡回路が短くなるようであれば実際に変える。
• 2-Optを適用できない状態でも、3-Optを適用すれば、また2-Optを適用できる場合がある。
• 局所最適解は求まるが、厳密解はなかなか求まらない。
• 適用する順番によって求まる解は異なる。
• λの値に応じて計算量が増えるため、現実的ではないがλ=nまで適用できれば厳密解が求まる。
• 実装の仕方にもよるが3-Optに2-Optは含まれてしまうと思う。（それでも2-Optの方が良い解を導くことがある。）

とりあえず実装するなら、nearest neighbor法で構築して2-Optで改善するのが楽だと思いました。

地図上の地点へのTSPの応用

特に地図上の任意の地点に対して応用しようとする際に問題となりそうなことを以下に挙げます。

1. 必ずしも巡回する必要はない。
   • 始点と終点間の経路を決定して巡回させればよい。
2. 頂点間のコストを移動時間や、料金とすれば、ユークリッド距離をそのまま用いることはできない。
3. 一方通行に加え渋滞が存在するため、動的な有向グラフである。
   • 歩行者には一方通行はほとんど関係ない。
4. 任意の2頂点間の最短経路上に他の巡回する頂点が含まれていることがありえる。
   • 最初に距離テーブルを作ってしまえば問題にならない。
5. 対話型のナビゲーションシステムにおいて、巡回する地点の数は多く見積もってもたかだた十数ではないだろうか。
6. 巡回する地点間の距離テーブルを作らなければならない。
   • DijkstraをN回実行するか、N×N回A*を実行する必要がある。

厳密解法

1-tree

任意の頂点ひとつとその頂点につながっている辺を取り除いたグラフから最小スパニング木を求め、その木に含まれない最も小さいコストの辺を2本選び，すでに求めた最小スパニング木に加えることで求まる。

ラグランジュ緩和

1-treeの辺の長さをうまく調整してやることで、最適解の下解を求めます。厳密解を求めるためには、得られた下解をもとに分枝限定法を使って求めます。

切除平面法

最も早く厳密解が求まる。

データ構造

発見的手法や、minimum spanning treesを求めるためにはk-d treesを用いるとよいようです。

デモ

Javaソフトウェアの無料ダウンロード

アプレットの動作には、Sun MicrosystemsのJ2SE5.0以上が必要です。

クリック

頂点の追加

Run

巡回路の計算の開始

Stop

巡回路の計算の中断

Clear

頂点の消去

計算中は、RunのボタンがStopになり、計算が終われば、Runに戻ります。Wikipediaでは、2000頂点くらいまでなら解けるというようになっていますが、そこまではとても無理です。

ライセンスはGPLとしておきます。

参考文献

• 山本芳嗣・久保幹雄著、”巡回セールスマン問題への招待”、朝倉書店
• Jon Louis Bentley、”K-d Trees for Semidynamic Point Sets”