巡回セールスマン問題（TSP）とは
巡回セールスマン問題（TSP：Traveling Salesman Problem）とは、指定されたすべての都市を一度ずつ巡り、出発地点に戻る際の移動距離を最短にする経路を求める問題です。
一見シンプルに見えるこの問題ですが、都市数が増えるにつれて計算量が爆発的に増加するという特徴を持っています。そのため、現実世界の物流や配送計画、ネットワーク設計など、幅広い分野で重要な研究対象となっています。
例えば、巡回ルートを少し変更するだけで、移動距離が大きく短縮される場合があります。ある例では、ルートA（青線）からルートB（赤線）に変更するだけで、約8.5cmも距離が短くなりました。このように、いかに効率よく最短経路を見つけるかがTSPの核心です。
巡回セールスマン問題はなぜ「解けない」と言われるのか
巡回セールスマン問題は、しばしば「解けない問題」と表現されます。ただし、これは理論的に解が存在しないという意味ではありません。
ここで言う「解けない」とは、「現実的な時間内に最適解を求めることが極めて困難」という意味です。
TSPは「NP困難（NP-hard）」と呼ばれる問題に分類されます。都市数を n とすると、考えられる巡回ルートの数は指数関数的に増加します。つまり、都市が増えるほど計算量が急激に膨れ上がり、必要な時間や計算資源が現実的ではなくなってしまうのです。
都市数が増えた場合の経路数と計算量
都市数が n 個ある場合、セールスマンが取りうる巡回経路の総数は、次の式で表されます。
(n − 1)! ÷ 2この式をもとに、都市数ごとの経路数と計算時間を推定すると、以下のようになります（1秒間に100万回計算できると仮定）。
都市数と経路数の増加例
| 都市数 n | 4 | 5 | 6 | 10 | 15 | 20 |
|---|---|---|---|---|---|---|
| 経路数（推定） | 3 | 12 | 60 | 約18万 | 約4,360億 | 約6.1兆 |
| 計算時間（推定） | 0秒 | 0秒 | 0秒 | 0.2秒 | 約12.11時間 | 約1,927年 |
この表から分かるように、都市数が15から20に増えるだけで、計算量は一気に天文学的な規模になります。
全ての経路を調べる「全探索」による解法は、現実的ではないことが明らかです。
実際にはどうやって効率的なルートを求めているのか
巡回セールスマン問題では、すべての都市を厳密に最短で回る経路を求めることは非常に難しいとされています。
そのため、実際の現場では次のような近似解法が用いられています。
- 最近近傍法
- 2-opt法
- 機械学習を用いたルート最適化
例えば、Amazonの配送システムでは、単純に「最短距離」だけを追求しているわけではありません。
天候、交通状況、荷物の優先度などの要素を加味しながら、「完全な最適解」ではなく「十分に良い解」を高速に求める仕組みが導入されています。
これにより、現実的な時間内で柔軟かつ効率的な配送ルートを決定することが可能になっています。
まとめ
巡回セールスマン問題（TSP）は、都市数の増加に伴って計算量が指数関数的に増大するため、全探索による最適解の算出は現実的ではありません。
特に都市数が20になるだけで、経路数は約6×10¹⁶通りにもなり、1秒間に10億回計算できる高性能なコンピュータを使っても、計算には数年規模の時間が必要になります。
そのためTSPは、
- 理論的には解ける
- しかし現実的な時間内には解けない
という特徴を持つ問題だと言えます。
この課題に対し、Amazonをはじめとする大手物流企業では、最近近傍法や2-opt法、機械学習を活用し、「だいたい良い解」を短時間で求め、状況に応じて動的にルートを修正しています。
このような考え方は、限られた時間や計算資源の中で最善の判断を行う、効率的なプログラム設計の重要性を学ぶ上でも非常に有益です。
著者
