巡回セールスマン問題

すべての都市をちょうど 1 回ずつ訪れて出発点に戻る、最短の経路を求める問題。 Traveling Salesman Problem、TSP。組合せ最適化の代表例。

$$\underset{\pi }{\min }\sum _{i=1}^{n}d(\pi (i),\pi (i+1))$$

候補数#

経路は $(n-1)!/2$ 通り。

$n$	経路数
10	181,440
20	$6.1\times {10}^{16}$
50	$3.0\times {10}^{62}$

全探索は $n=20$ で既に非現実的。

解き方#

厳密解 — 分枝限定法と切除平面法を組み合わせた Concorde が代表的な実装で、 数万都市規模の最適解が報告されている。NP 困難だが、 問題構造を使い込めば実用規模は解ける、という好例。

近似 — 距離が三角不等式を満たす場合、 Christofides のアルゴリズムが最適解の 1.5 倍以内を保証する。

ヒューリスティック — 2-opt、3-opt、Lin-Kernighan。 焼きなまし法や GA の近傍・交叉として使われる。

2-opt#

経路から 2 辺を選んで繋ぎ替える操作。 差分だけで評価できる（4 本の辺の長さだけ見ればよい）ので、 局所探索の近傍として非常に効率が良い。 良い近傍の条件を満たす典型例。

参考文献#

• David L. Applegate et al. The Traveling Salesman Problem: A Computational Study. Princeton University Press, 2006. https://doi.org/10.1515/9781400841103
• Nicos Christofides. Worst-Case Analysis of a New Heuristic for the Travelling Salesman Problem. Operations Research Forum 3, 2022（1976 年の技術報告の再版）. https://doi.org/10.1007/s43069-021-00101-z
• Christos H. Papadimitriou, Kenneth Steiglitz. Combinatorial Optimization: Algorithms and Complexity. Prentice Hall, 1982 / Dover, 1998. https://store.doverpublications.com/products/9780486402581