巡回セールスマン問題（Traveling Salesman Problem, TSP）とは、セールスマンが複数の都市を訪問して出発地に戻る際、総移動距離が最小となる経路を求める問題です。都市の数が増えると、可能な経路の数が爆発的に増加するため、最適解を求めることが非常に難しい問題（NP困難）として知られています。
巡回セールスマン問題とは
巡回セールスマン問題は、以下のような状況をモデル化したものです。
- 一人のセールスマンが、複数の都市をすべて訪問して、自分の出発地に戻ってきたいと考えています。
- 各都市間の移動コスト（距離、時間、費用など）は分かっています。
- セールスマンは、どの順番で都市を回れば、最も効率的に（＝総移動コストを最小に）できるでしょうか？
この問題を定式化すると、「与えられた都市の集合と都市間の距離（コスト）に対して、すべての都市をちょうど1度ずつ訪問し、出発地に戻る巡回路の中で、総移動距離（コスト）が最小となるものを求めよ」となります。
問題の構成要素
- 都市: セールスマンが訪問する地点の集合です。都市の数は有限個です。
- 距離（コスト）: 都市間の移動にかかるコストです。通常は正の値で表され、対称性（都市Aから都市Bへの距離と、都市Bから都市Aへの距離が等しい）を仮定することが多いですが、非対称な場合（例えば、一方通行の道路や、移動手段によってコストが異なる場合）も考えられます。
- 巡回路（経路）: 全ての都市をちょうど1度ずつ訪問し、出発地に戻る経路のことです。巡回セールスマン問題の解は、この巡回路の中で総移動コストが最小となるものを求めることになります。
問題の難しさ
都市の数が少ないうちは、全ての巡回路を列挙して総移動コストを計算し、最小のものを探すことができます（全探索）。しかし、都市の数が n のとき、可能な巡回路の数は (n-1)! / 2 となり、n が大きくなるとこの数は爆発的に増加します（階乗オーダー）。例えば、n=10 のときは約18万通りですが、n=20 になると約1016通りにもなります。そのため、全探索は現実的な時間で解くことができません。巡回セールスマン問題は、NP困難と呼ばれる問題クラスに属し、効率的な（多項式時間の）解法は見つかっていません。
補足: NP困難とは
NP困難とは、計算量理論において「少なくともNP完全問題と同程度に難しい問題」を指します。NP完全問題とは、「NP問題の中で最も難しい問題」であり、「非決定性チューリングマシンを用いて多項式時間で解ける問題」かつ「他の全てのNP問題を多項式時間で帰着できる問題」です。 NP困難な問題は、効率的なアルゴリズム（多項式時間で解けるアルゴリズム）が存在しないと考えられています。
巡回セールスマン問題の解法
巡回セールスマン問題の解法は、大きく分けて以下の3つに分類されます。
解法1: 厳密解法
全ての可能な経路を比較して最適解を求める方法です。都市数が少ない場合には有効ですが、都市数が増えると計算量が指数関数的に増加するため、現実的な時間で解くことが困難になります。
具体的な手法: 全探索（総当たり）法、分枝限定法、動的計画法など
解法2: 近似解法
必ずしも最適解が得られるとは限りませんが、現実的な時間で比較的良い解（近似解）を得ることを目指す方法です。
具体的な手法
- 最近傍法（Nearest Neighbor Method）: 現在いる都市から最も近い未訪問の都市を次に訪問する都市として選択することを繰り返す方法です。シンプルで高速ですが、精度はあまり高くありません。
- 2-opt法: 経路中の2本の辺を交換することで経路長が短くなる場合、交換を行う操作を繰り返す方法です。
- 3-opt法: 経路中の3本の辺を交換することで経路長が短くなる場合、交換を行う操作を繰り返す方法です。2-opt法よりも精度が向上しますが、計算量も増加します。
解法3: メタヒューリスティクス
特定の解法に依存せず、汎用的に利用できる最適化アルゴリズムです。局所探索と大域探索を組み合わせることで、近似解法よりも良い解が得られる可能性があります。
具体例: 遺伝的アルゴリズム（Genetic Algorithm, GA）、シミュレーテッドアニーリング（Simulated Annealing, SA）、タブーサーチ（Tabu Search, TS）、蟻コロニー最適化（Ant Colony Optimization, ACO）など
具体例：6都市の巡回セールスマン問題
6つの都市（都市1〜都市6）を巡回する場合を例に、巡回セールスマン問題を具体的に考えてみましょう。各都市間の距離は以下の表で与えられるものとします。
| 都市1 | 都市2 | 都市3 | 都市4 | 都市5 | 都市6 | |
|---|---|---|---|---|---|---|
| 都市1 | 0 | 2 | 3 | 1 | 4 | 5 |
| 都市2 | 2 | 0 | 4 | 2 | 3 | 4 |
| 都市3 | 3 | 4 | 0 | 1 | 2 | 1 |
| 都市4 | 1 | 2 | 1 | 0 | 5 | 2 |
| 都市5 | 4 | 3 | 5 | 5 | 0 | 3 |
| 都市6 | 5 | 4 | 2 | 2 | 3 | 0 |
最近傍法による経路探索
- 都市1を出発点とします。
- 都市1から最も近い都市4を訪問します（距離1）。
- 都市4から最も近い未訪問の都市は都市3です（距離1）。
- 都市3から最も近い未訪問の都市は都市6です（距離1）。
- 都市6から最も近い未訪問の都市は都市2です（距離4）。
- 都市2から最も近い未訪問の都市は都市5です（距離3）。
- 都市5から出発点の都市1に戻ります（距離4）。
この場合の経路は「1→4→3→6→2→5→1」となり、総移動距離は1+1+1+4+3+4 = 14となります。
遺伝的アルゴリズム(GA)による経路探索の例
遺伝的アルゴリズムは生物の進化を模倣したアルゴリズムで、以下の手順で解を探索します。
- 初期化: ランダムな経路を複数生成します（個体群）。
- 評価: 各経路の総移動距離を計算し、適応度とします。
- 選択: 適応度の高い個体を優先的に選択します。
- 交叉: 選択された個体間で経路の一部を交換し、新しい個体を生成します。
- 突然変異: 一定確率で個体の経路の一部をランダムに変更します。
- 上記2〜5のステップを繰り返し、適応度が最も高い個体（最も総移動距離が短い経路）を解とします。
（例）
初期個体として以下の2つの経路を考えます。
- 経路A: 1-3-5-6-2-4-1 (総移動距離: 16)
- 経路B: 6-5-4-2-1-3-6 (総移動距離: 16)
これらの経路を交叉させます。例えば、経路Aの「5-6-2」の部分と経路Bの「4-2-1」の部分を交換すると、
- 経路C: 1-3-4-2-1-5-6 (不適切な経路)
- 経路D: 6-5-5-6-2-4-3 (不適切な経路)
となり巡回路になりません。 経路が巡回路となるように調整します。例えば経路の一部を入れ替えるなどの処理をします。また、突然変異の具体的な方法、調整などはいくつか種類があります。
まとめ
巡回セールスマン問題は、NP困難な問題であるため、都市数が多くなると厳密解を求めることは困難です。しかし、近似解法やメタヒューリスティクスを用いることで、実用的な時間内に精度の高い解を得ることができます。
巡回セールスマン問題は、配送経路最適化、基盤配線設計、スケジューリングなど、幅広い分野で応用されており、その解法の研究は、現在も活発に行われています。
[PR] 巡回セールスマン問題についても学べるUdemyコースを紹介します
