巡回セールスマン問題

巡回セールスマン問題を総当たりで解く場合のイメージ。左側で一つずつ探していき、より効率のいいルートが見つかった場合、右側のグラフが更新される。

巡回セールスマン問題（じゅんかいセールスマンもんだい、英: traveling salesman problem、TSP）は、都市の集合と各2都市間の移動コスト（たとえば距離）が与えられたとき、全ての都市をちょうど一度ずつ巡り出発地に戻る巡回路のうちで総移動コストが最小のものを求める（セールスマンが所定の複数の都市を1回だけ巡回する場合の最短経路を求める）組合せ最適化問題である。

詳細

問題例の大きさは、都市の数で表される。この問題は、計算複雑性理論においてNP困難と呼ばれる問題のクラスに属する。すなわち、問題例の大きさに関する決定性の多項式時間アルゴリズムが見つかりそうにない、計算量的に困難な問題である。なお、この問題の特殊ケースとして考えられるハミルトン閉路問題は、NP困難であると共にNP完全と呼ばれるクラスにも属するので、扱いが異なる。

都市間の移動コストが三角不等式を満たす、すなわち移動コストを距離と呼べる部分問題（あるいは制約つき問題）も、NP困難である。都市を平面上の点、都市間の距離を平面上のユークリッド距離とする部分問題は最も直感的で理解しやすいが、これも NP困難である。この部分問題は平面TSPなどと呼ばれ、実用上の応用も多く、またベンチマークの問題例としても距離関数の定義が自明なため頻繁に現れる。 都市の間の移動コストを 1 または 2 に制限しても、この問題もNP困難である。ハミルトン閉路問題は、移動コストを 1 または無限大に制限した TSP とみなすことができる。

一方で制約のない巡回セールスマン問題の直接の応用事例は無いと言ってもよい。逆に実際の応用事例では、より複雑な定義で配送計画や表面実装ロボットの動作計画などに適用される。

整数線形計画問題による定式化

巡回セールスマン問題は整数線形計画問題として定式化することができる。定式化の方法としてはいくつか知られており、そのうち Miller–Tucker–Zemlin (MTZ) 定式化と Dantzig–Fulkerson–Johnson (DFJ) 定式化の2種類が著名な定式化として知られている。DFJ定式化はMTZ定式化と比べて制約によって構成される多面体が厳密に小さいという意味で強い定式化とされているが、MTZ定式化についても特定の状況下では使用される。

両者の定式化に共通して与えられる定数は都市 $1,\ldots ,n$ および都市$i,j$ 間の距離（移動費用）を表す$c_{ij}>0$ が挙げられる。また定式化で使われる主な変数としては:

$x_{ij}={\begin{cases}\,\\\,\end{cases}}$		$1$		都市$i$と都市$j$を結ぶ経路を通るとき
		$0$		そうでないとき

という $0$ か $1$ の値をとる変数を導入する。0-1変数によって巡回セールスマン問題は整数計画問題として定式化され、かつすべての制約は線形で表される。整数計画問題の目的関数は総移動距離が最小となる巡回路を求める:

$\sum _{i=1}^{n}\sum _{j\neq i,j=1}^{n}c_{ij}x_{ij}.$

もし定式化において巡回セールスマン問題に関する制約が与えられない場合、$\{x_{ij}\}_{i,j}$ はいかなる値も取り得ることができ、任意の辺集合が解として許容されることから、定式化によって求めたい巡回路とは大きく異なった解が求まってしまう。この場合、最適解は $x_{ij}=0$ となる自明な解が求まってしまう。それゆえ、両者の定式化では都市に関する制約が与えられる。具体的には各都市について巡回路を成す経路の数は入次数、出次数ともにちょうど1つずつとなる等式の線形制約が $2n$ 個与えられる。

$\sum _{i=1,i\neq j}^{n}x_{ij}=1$ ${\textrm {for}}$ $j=1,\ldots ,n$	かつ
$\sum _{j=1,j\neq i}^{n}x_{ij}=1$ ${\textrm {for}}$ $i=1,\ldots ,n.$

これらの制約により、選択された辺の集合が局所的には巡回路のように見えることが保証されるが、それでも真の制約、すなわち「すべての頂点を訪れる単一の巡回路であること」を満たさない解が求まる可能性がある。これは、選択された辺が複数の巡回路を構成し、それぞれが頂点の部分集合のみを訪れる場合が起こり得るためである。実際、すべての頂点を訪れる単一の巡回路という制約が、巡回セールスマン問題を難しくしている要因であるとも言える。MTZ、DFJ定式化は、この制約を線形制約として表現する方法が異なっている。

Miller–Tucker–Zemlin定式化

MTZ定式化では変数 $x_{ij}$ に加えて、各都市を訪れる順番を表す補助変数 $u_{i}$,$i=1,\ldots ,n$ を用いる。これは都市$1$;を出発地とし、都市 $i$ が都市 $j$ よりも先に訪れるならば、$u_{i}<u_{j}$ を満たす変数である。与えられた巡回路（$x_{ij}$ の値によって求まる）に対して、$u_{i}$ がとるべき値は、都市 $1$ から都市 $i$ までで経由した巡回路上の辺の数と等しくなることから求まる。

このことから、最適化問題の制約条件で用いられる不等式（($>$),でなく $\geq$ として表す）を用いて、以下の条件を考慮した制約を求めることを考える:

もし $x_{ij}=1$ ならば $u_{j}\geq u_{i}+1.$

一見 $u_{j}\geq u_{i}+x_{ij}$ と書き換えても同等の制約を課しているようにも見えるが、$x_{ij}=0,$ の場合にも $u_{j}\geq u_{i}$ の先行順序関係を強制してしまうこととなり、制約が正しく機能しない。以上のことを踏まえて、MTZ定式化では次の $n(n-1)$ 個の線形制約を導入する:

$u_{i}-u_{j}+1\leq (n-1)(1-x_{ij})$ for all distinct $i,j\in \{2,\dotsc ,n\},$

$x_{ij}=0$ のときは $u_{j}$ と $u_{i}$ に対して先行順序関係を保証しないことから、先行順序関係を保証する制約の数は実質 $n-1$ 個となる。

変数 $u_{i}$ を導入して「単一の巡回路がすべての都市を訪れる」ことを満たす方法は、巡回路に沿った訪問する都市ごとに $u_{i}$ が少なくとも 1 ずつ増加し、減少が許されるのは巡回路が都市 $1$ を最後に訪れる場合のみとすることである。この制約によって、巡回路が単一でないとき都市 $1$ を通過しないことで制約が違反されるため、単一の巡回路によって都市 $1$ から出発し、最終的に都市 $1$ に戻ることを強制している。

巡回セールスマン問題に対するMTZ定式化は次の整数線形計画問題として定式化することができる:

$\min$		$\sum _{i=1}^{n}\sum _{j=1,j\neq i}^{n}c_{ij}x_{ij}\colon$
$\mathrm {s.t.}$		$x_{ij}\in {}\{0,1\}$		$i,j=1,\ldots ,n;$
		$\sum _{i=1,i\neq j}^{n}x_{ij}={}1$		$j=1,\ldots ,n;$
		$\sum _{j=1,j\neq i}^{n}x_{ij}={}1$		$i=1,\ldots ,n;$
		$u_{i}-u_{j}+1\leq {}(n-1)(1-x_{ij})$		$2\leq i\neq j\leq n;$
		$2\leq u_{i}\leq {}n$		$2\leq i\leq n.$

一つ目の制約は各都市において一つ前に訪れる都市はちょうど１つ存在することを表し、2つ目の制約についても各都市において一つ後に訪れる都市の数もちょうど1つ存在することを表している。最後の制約は求まる巡回路がすべての都市をちょうど1回ずつ訪れることを保証する制約で、独立した2つ以上の巡回路が生じることを禁止している。

Dantzig–Fulkerson–Johnson定式化

都市 $1,\ldots ,n$ が与えられたとする。変数としては:

$x_{ij}={\begin{cases}\,\\\,\end{cases}}$		$1$		都市$i$と都市$j$を結ぶ経路を通るとき
		$0$		そうでないとき

という $0$ か $1$ の値をとる変数を導入する。都市 $i,j$ 間の距離は $c_{ij}>0$ とする。このとき巡回セールスマン問題は次の整数線形計画問題として定式化することができる:

$\min$		$\sum _{i=1}^{n}\sum _{j=1,j\neq i}^{n}c_{ij}x_{ij}\colon$
$\mathrm {s.t.}$		$x_{ij}\in {}\{0,1\}$		$i,j=1,\ldots ,n;$
		$\sum _{i=1,i\neq j}^{n}x_{ij}={}1$		$j=1,\ldots ,n;$
		$\sum _{j=1,j\neq i}^{n}x_{ij}={}1$		$i=1,\ldots ,n;$
		$\sum _{i\in Q}{\sum _{j\in Q,j\neq i}{x_{ij}}}\leq |Q|-1$		$\forall Q\subsetneq \{1,\ldots ,n\},|Q|\geq 2.$

DFJ定式化の最後の制約は要素数が $2$ 以上の都市集合の部分集合 $Q$ について（部分）巡回路が発生しないことを保証するために導入しており、これを部分巡回路除去制約と呼ぶ。これは巡回セールスマン問題で求めたい巡回路はすべての都市をちょうど1回ずつ訪れて出発地に戻ならければならないため、定式化を解くことで求まる巡回路が複数求まることを禁止する制約として働く。具体的には、都市集合の部分集合 $Q$ ごとに、巡回路を成す辺の総数は部分集合 $Q$ の要素数より厳密に少なければならない。もし部分集合 $Q$ 内で巡回路を成す辺の総数が $Q$ の要素数以上の数が存在する場合は、$Q$ 内に部分巡回路が含まれていることになる。DFJ定式化の部分巡回路除去制約は都市集合の部分集合すべてに対して制約を課す必要があることから、制約の個数は都市数のべき乗倍の数課す必要がある。実用上は分枝カット法によって段階的に制約を加えることで、効率的に定式化の最適解を求めている。

解法

全ての経路を計算することで最適解を得る手法は時間計算量は $O(n!)$ であり、都市数の増加に対して時間計算量が急速に増加するため、都市数が20以上になると現実的でない。 比較的効率的なアルゴリズムとしては時間計算量と空間計算量が共に $O(n^{2}2^{n})$ である動的計画法を用いたヘルドカープのアルゴリズムが存在する。

NP困難な問題は、任意の大きさの任意の問題例に対しての多項式時間アルゴリズムが存在しないと考えられているが、巡回セールスマン問題の場合、約2000都市以内の比較的小さい問題例に対して、あるいは問題例によっては解が得られないことがあってもよいのであれば、線形計画法と論理木を組み合わせた分枝限定法や、線形計画法と巡回群を組み合わせた切除平面法により、パーソナルコンピュータでおよそ1日以内で厳密解を得られることが多い。

厳密に最適解を求めることを放棄して計算時間を短くする方法は、2-optやリン・カーニハン・アルゴリズムなどの局所探索アルゴリズム、焼きなまし法、ホップフィールドネットワークあるいはボルツマン機械などのヒューリスティックアルゴリズムと、出力される解のコストと最適解のコストとの差をなんらかの形で保証する多項式時間近似アルゴリズムの二つに大別できる。

より複雑な定義の問題をあつかう解法としては、欧州では前述した分枝限定法、切除平面法、（前者2つをミックスした）分枝カット法といった厳密解法を用いることが多く、アメリカ合衆国では遺伝的アルゴリズム、タブー探索といった厳密に最適な解を保証しないヒューリスティックアルゴリズムを用いることが多い。

三角不等式が成り立つ TSP については多項式時間近似アルゴリズムが数多く存在する。 たとえば近似アルゴリズムが 2（最悪でも出力が最適解の長さの2倍以内である）のアルゴリズム（最近追加法他）や近似度 1.5 のアルゴリズム（クリストフィードのアルゴリズム）が知られている。 近年、平面TSP には、近似率を任意に 1 に近づけることができるアルゴリズム、多項式時間近似戦略 PTAS が Arora によって与えられた。 ハミルトン閉路問題の多項式時間の厳密解が多項式時間で求められない（ハミルトン閉路問題はNP完全なのでP≠NPと同じ）なら三角不等式を満たさないTSPは近似率を保証する多項式時間のアルゴリズムはない。

関連項目

• ハミルトン閉路問題
• 中国人郵便配達問題 - すべての辺（頂点ではなく）を少なくとも1回ずつ通る巡回路でコスト最小のものを求める。こちらは多項式時間で解けることが知られている。
• 配送計画問題
• DNAコンピュータ
• 粘菌コンピュータ
• 最近傍法
• P≠NP予想
• 配車配送計画ソフト

外部リンク

• 『巡回セールスマン問題の意味と2近似アルゴリズム』 - 高校数学の美しい物語
• Traveling Salesman Problem - TSPのベンチマーク問題集その2 (World TSP，National TSPs, VLSI)