🔖 キーワード索引

「巡回セールスマン問題」を取り巻く中核キーワード群です。 検索やインデックス作成で参照する際の手がかりにしてください。 各キーワードは関連する概念・手法・道具立てを含み、 文献検索や学習計画の起点になります。

🎨 直感で掴む

5 都市の TSP は (5-1)!/2 = 12 通り。 全列挙可能。

でも n = 20 では 約 6 京通り。 1 秒に 10 億通り計算しても 700 年。

n = 100 では宇宙の年齢を超える。 だから「全列挙」は諦め、 「ほぼ最適」で妥協するのが現実解。

🎨 概念図で押さえる

巡回セールスマン問題 (TSP) を 3 枚で押さえる: (1) 都市と巡回路の幾何、 (2) 分枝限定法 (Branch and Bound) の探索木、 (3) 都市数に対する計算量の爆発。 これで「なぜ近似/メタヒューリスティクスが必要か」が直感で分かる。

図 1: 5 都市の巡回路 — 距離合計を最小化する閉路

下図は 5 都市の例。 出発地に戻る閉路 (Hamilton 閉路) のうち、 総距離が最短になるものを選ぶのが TSP。 5 都市なら手で全 12 通り (=(5-1)!/2) を試せる。

辺の数字は都市間距離。 5 都市の場合は全数列挙で最適解が求まる。 都市数 N が増えると組合せ数が爆発する (図 3 参照)。

図 2: 分枝限定法 (Branch and Bound) の探索木

部分巡回路を「枝」、 部分解の下界を「節点」として、 現在の最良解より下界が悪い部分木を枝刈り (prune) する。 これで N! 通り全探索しなくても済む。

緑ノード=展開して探索する分枝、 赤ノード=下界が現在の最良解を超えるので刈り取られる枝。 良い下界の評価関数 (例: 最小全域木) を使うほど刈れる枝が増える。

図 3: 計算量の爆発 — 都市数 N と (N-1)!/2 通りの組合せ

全探索の場合、 ルートの数は (N-1)!/2 で増える。 N=10 で約 18 万、 N=15 で約 4.4 億、 N=20 で約 6.1 × 10^16。 N=20 を秒 10^9 通り評価しても 1.9 年かかる。 だから近似アルゴリズム (最近傍法、 2-opt、 遺伝アルゴリズム) が現実的選択肢になる。

この曲線が「TSP は NP-hard クラスに属する」ことを直感的に示す。 厳密最適解を求める時間は都市数とともに爆発するので、 実務では Concorde (専用ソルバ) や局所探索 + メタヒューリスティクスを併用する。

この3枚で「問題定義」→「探索戦略」→「計算量限界」の三段論法が完成する。 派生問題は 組合せ最適化・数理最適化・最適化 へ。

📝 理解度チェック（練習問題）

TSP の核を本当に掴めたかを 6 問で確認する。 すべて 1 分以内で答えられる粒度。 「自分で」答えを口に出して言える状態を目指したい。

Q1. なぜ TSP は NP-hard か、 一言で説明できるか

Q2. 「最近傍法 (Nearest Neighbor) は必ず最適解を返す」は ◯ か ×

Q3. 分枝限定法の「限定 (bound)」の役割

Q4. 都市 30 で全探索は何秒かかるか (秒 10⁹ 通り評価)

Q5. SSDSE-B-2026 の 47 都道府県を回るとき、 厳密解はどの程度の時間で解けるか

Q6. 配送計画でよくある TSP の派生は

これらの問題に詰まったセクションがあれば、 直前の「概念図」「数式」「Python 実装」セクションへ戻って再確認しよう。 TSP は厳密解の限界を理解した上で、 メタヒューリスティクスをうまく使い分けるのが現代的な向き合い方である。

🎮 触って理解する

最近傍法の「悪手」を 2-opt / Or-opt がほどく過程を、 1 手ずつ目で追うデモです。 組合せ最適化 のページに基本の TSP デモがあるので、 ここでは一歩踏み込んで 「アルゴリズム間の比較」 に焦点を当てます: (1) 貪欲な最近傍法がどこで遠回りの「ツケ」を払うか、 (2) 2-opt / Or-opt が交差を 1 手ずつ張り替えて改善する過程、 (3) 総当たり厳密解とのギャップ%、 (4) MST 下界との比較。 キャンバスの空白をクリック（タップ）で都市を追加、 既存の都市をクリックすると 開始都市 が変わります。

🧭 推奨の遊び方 — 3 分でアルゴリズム比較を体感

1. 💣 罠の8都市 → ⏩ 最後まで: 序盤は短い辺を快調に拾うのに、 後半で長い辺と 交差 (赤色表示) が生まれる様子をログで確認。 都市1スタートの総距離は 1489.4。
2. 🏁 厳密解: 総当たり (8都市なら 2520 通り) で最適 1140.9。 最近傍法のギャップは +30.5% と判明。
3. 🔧 改善: 最近傍法の解 (1489.4) を初期解に、 2-opt が交差した 2 辺を張り替える (赤の点線=削除 → 緑の点線=追加)。 この配置では 2-opt だけの 6 手で厳密解 1140.9 に到達する過程をアニメーションで観察できる。 Or-opt (都市の移植) は 2-opt で改善が尽きた後の仕上げ役として、 ランダム配置で登場することがある。
4. 都市をクリックして起点変更 → ⏩: 最近傍法の結果が起点で変わる。 🔁 全起点でNN比較 を押すと、 罠配置では 1267.0〜1598.6 まで揺れることが分かる (開始依存)。
5. 🧹 クリア して自分で都市を置き、 「最近傍法が失敗する配置」「2-opt でも厳密解に届かない配置 (局所最適)」を作ってみる。

🎨 直感 — 貪欲は近視眼、 改善法は「交差をほどく」

• 最近傍法のツケ払い構造: いま一番近い都市に飛びつくので、 序盤は最短の辺ばかり選べて快調。 しかし近場を食い尽くした後、 取り残した都市への長距離移動という「ツケ」を後半にまとめて支払う。 特に 閉路を閉じる最後の辺 が極端に長くなりがち (デモでは最長辺に距離ラベルが付く)。
• 交差=改善余地のサイン: 平面ユークリッド TSP の最適巡回路は自分自身と交差しない。 交差する 2 辺は、 三角不等式により張り替えれば必ず短くなるからである。 2-opt はまさに「交差した 2 辺を外して繋ぎ替える」操作で、 デモの赤点線 (削除) → 緑点線 (追加) がその 1 手に当たる。
• Or-opt は「移植」: 連続する 1〜3 都市を丸ごと切り出して別の位置に差し込む。 2-opt (辺の張り替え) では届かないタイプの改善を拾うため、 両者を交互に使うと局所最適の質が上がる。
• MST 下界: 巡回路から 1 辺を抜くと全域木になるので、 「最適解 ≥ 最小全域木 (MST) の長さ」が常に成り立つ。 スコアボードの「下界比」が 1 に近いほど良い解 — 厳密解が計算できない規模でも解の品質を保証できるのが下界の威力で、 分枝限定法の枝刈りもこの発想で動く。

⚠️ よくある落とし穴 — 局所最適と開始依存

• 局所最適: 2-opt / Or-opt が止まった解は「この近傍操作では改善不可」というだけで、 厳密解の保証はない (局所解と探索)。 🎲 ランダム配置を何度か生成し、 改善後もギャップが残る例を探してみよう。 脱出には multi-start・焼きなまし・より深い近傍 (3-opt, LK) を使う。
• 開始依存: 最近傍法は起点で結果が大きく変わる (罠配置で 1267.0〜1598.6、 約 26% の差)。 全起点を試して最良を採る multi-start が定石だが、 それでも貪欲構築の限界は超えられない。
• 答え合わせできない領域: n≤10 なら総当たりで検算できるが、 n=20 では約 6×10¹⁶ 通りで不可能。 実務では「ヒューリスティック解 vs 下界 (MST・Held-Karp)」の比率でしか品質を語れない。 このデモの下界比の見方が、 そのまま大規模問題での品質管理に繋がる。

🚀 発展 — 近似保証とモダンな解法

• Christofides (1976): MST + 最小重み完全マッチングで構築し、 対称かつ三角不等式が成り立つ TSP で 最適解の 1.5 倍以内を保証。 この壁は約 45 年破られず、 2020 年にようやく 1.5 − 10⁻³⁶ へ微改良されたことが大ニュースになった。
• 近似の限界: 三角不等式のない一般 TSP は、 P≠NP の下で定数倍近似すら不可能。 一方、 平面ユークリッド TSP には任意精度の多項式時間近似 (PTAS, Arora 1998) が存在する。 「距離の性質」が難しさを左右する好例。
• LKH (Lin-Kernighan-Helsgaun): 2-opt / 3-opt を「可変深さの張り替え」に一般化した実務最強級ヒューリスティック。 100 万都市級でも最適解の 1% 以内に迫る。 このデモの 2-opt はその最小構成要素と言える。
• 体系的な位置づけは 組合せ最適化・メタヒューリスティクス を参照。 SSDSE-B-2026 の 47 都道府県 (n=47) は「総当たり不可能・厳密解ソルバなら可能・2-opt なら一瞬」という境界サイズで、 まさにこのデモの延長線上にある。

📐 定義・数式

🔬 記号・要素の読み解き

🔬 数式を言葉で読み解く（詳細版）

「TSP（巡回セールスマン問題）」は 全都市を 1 回ずつ訪問して出発点に戻る最短ルートを求める NP 困難問題。組合せ最適化の代名詞。 です。 ここでは定義式の各記号、 直感的意味、 SSDSE-B-2026 への当てはめを段階的に解きほぐします。

① TSP の定式化

② TSP の計算量

③ 整数計画 (ILP) 定式化

④ 主要アルゴリズム比較

⑤ NP 困難の位置づけ

TSP は NP 困難。 「P = NP?」問題に直結する代表的組合せ最適化問題。 厳密解の多項式時間アルゴリズムは存在しない (証明されているわけではないが、 50 年以上発見されていない)。 実務では近似解で十分という割り切りが標準。

SSDSE-B-2026 で「TSP（巡回セールスマン問題）」を体感する

SSDSE-B-2026 で「47 都道府県庁所在地を巡回する TSP」。 入力は 47 都道府県の地理座標（仮想）と都道府県人口を訪問コストに、 出力は OR-Tools / nearest-neighbor で近似解。 47 都道府県 × 複数年の実データで具体計算を実施します。

🏭 産業界での活用事例（6 件）

⚖️ 関連手法との比較表

💥 失敗例から学ぶ

📝 演習問題（5 問・解答付き）

1. 問題 1：47 都道府県の TSP を SSDSE-B-2026 の総人口・出生数で 2 次元座標化して Nearest Neighbor で解け。
   ▼ 解答

   📥 入力例（SSDSE-B-2026 の 2023 年・47 都道府県から 3 行） 都道府県 SSDSE-B-2026(年度) A1101(総人口) A4101(出生数) 北海道 2,023 5,092,000 24,430 東京都 2,023 14,086,000 86,348 沖縄県 2,023 1,468,000 12,549 …（全 47 行）

   📋 コピー

   1 2 3 4 5 6 7 8 9 10 11 12 13 14

   import pandas as pd, numpy as np from sklearn.metrics.pairwise import euclidean_distances df = pd.read_csv('data/raw/SSDSE-B-2026.csv', encoding='cp932', skiprows=1) # 日本語の列名で読む（2 行目を見出しにする） d = df[df['年度']==2023].reset_index(drop=True) xy = np.column_stack([d['総人口']/1e6, d['出生数']/1e3]) D = euclidean_distances(xy) # Nearest Neighbor: 北海道から出発し、未訪問のうち最も近い県へ移る tour, rest = [0], set(range(1, len(d))) while rest: nxt = min(rest, key=lambda j: D[tour[-1], j]) tour.append(nxt); rest.remove(nxt) length = sum(D[tour[i], tour[(i+1) % len(tour)]] for i in range(len(tour))) print(f"NN 経路長: {length:.2f}") print("訪問順 (先頭 5):", ' → '.join(d['都道府県'][tour[:5]]))

   📤 実行例（実測） NN 経路長: 171.97 訪問順 (先頭 5): 北海道 → 静岡県 → 広島県 → 茨城県 → 京都府

   💬 北海道（総人口 5.09、出生数 24.43 の点）から最寄りの県へ貪欲に移ると、静岡・広島・茨城・京都と人口 250〜360 万人級の県が続き、47 県を 1 周した経路長は 171.97 になる。この長さは「百万人」と「千人」を混ぜた座標上の距離なので単位に意味はなく、比べられるのは同じ座標で作った別の経路（2-opt 後の 169.36 など）とだけ。

2. 問題 2：Held-Karp 動的計画法の計算量はなぜ $O(2^n n^2)$ か説明せよ。
   ▼ 解答

   状態 = (訪問済み都市集合 S, 現在都市 v)。 S は $2^n$ 通り、 v は $n$ 通り、 遷移計算が $O(n)$。 合計 $O(2^n \cdot n^2)$。 $n=20$ で $4 \times 10^8$ 操作、 数秒で解ける。
3. 問題 3：2-opt の操作を 1 ステップ図示せよ。
   ▼ 解答

   経路 A-B-...-C-D を A-C-...-B-D に「逆順化」する操作。 エッジ (A,B), (C,D) を (A,C), (B,D) に置換。 距離が減れば採用、 そうでなければ次のペアへ。
4. 問題 4：Google OR-Tools で 10 都市 TSP を解け。
   ▼ 解答

   📋 コピー

   1 2 3 4 5 6 7 8 9

   from ortools.constraint_solver import pywrapcp, routing_enums_pb2 m = pywrapcp.RoutingIndexManager(10, 1, 0) routing = pywrapcp.RoutingModel(m) def distance(from_i, to_i): return abs(m.IndexToNode(from_i) - m.IndexToNode(to_i)) t = routing.RegisterTransitCallback(distance) routing.SetArcCostEvaluatorOfAllVehicles(t) sol = routing.Solve() print(sol.ObjectiveValue())

5. 問題 5：TSP と VRP (Vehicle Routing Problem) の違いを述べよ。
   ▼ 解答

   TSP: 1 台で全都市を巡る。 VRP: 複数車両で分担、 容量制約・時間枠制約あり。 VRP の方が実務適合度高い。 VRP は TSP の一般化。 Amazon・FedEx は VRP を解いている。

📖 関連用語辞典（10 語）

TSP

Traveling Salesman Problem。 巡回セールスマン問題。 NP 困難。

VRP

Vehicle Routing Problem。 複数車両版 TSP。 容量・時間枠付き。

Hamilton 閉路

全頂点を 1 回ずつ訪れて出発点に戻る閉路。 TSP の解。

NP 困難

多項式時間で解けないと予想される問題クラス。

Nearest Neighbor

現在地から最近未訪問都市へ移る貪欲法。 簡易だが質はやや低い。

2-opt

経路の 2 エッジを入れ替える局所探索。 質改善の標準。

Christofides

ユークリッド TSP に 1.5 倍以内保証を与える古典アルゴリズム。

LKH (Lin-Kernighan-Helsgaun)

TSP の現代最強ヒューリスティック。 世界記録レベル。

ILP (整数計画)

TSP を整数 0/1 変数で定式化する手法。 厳密解。

Concorde

TSP 厳密解の最先端ソルバー。 85,900 都市の世界記録 (2006)。

🧮 実値で計算してみる

解法のスケール感（n 都市）：

🧮 数式に値を入れて手で計算する: TSP 巡回路の長さ

合成 4 都市で全巡回路長を列挙する。

Step 1: 都市座標

Step 2: 順路の長さ

Step 3: 都市 n での巡回路数

🐍 Python で再現

1
2
3
4
5
6
7
8
9

import numpy as np
from itertools import permutations
cities = np.array([[0,0],[1,0],[1,1],[0,1]])
def length(perm):
    return sum(np.linalg.norm(cities[perm[i]] - cities[perm[(i+1)%4]]) for i in range(4))
routes = list(permutations(range(1,4)))
lens = [float(length([0]+list(r))) for r in routes]
print(f"全巡回路長: {[round(x, 3) for x in lens]}")
print(f"最短: {min(lens)}")

📤 実行結果

💬 手計算 (Step 2) 4.0 と Python 出力が完全一致。

🐍 Python での扱い

最小再現コード。 SSDSE-B のような実データを前提に、 4〜8 行で動く例です：

1
2
3
4
5
6
7
8
9
10

from itertools import permutations
# n=6 都市の全列挙（ブルートフォース、 デモ用）
cities = [(0,0),(1,3),(4,3),(6,1),(3,0),(5,4)]
def dist(a,b): return ((a[0]-b[0])**2+(a[1]-b[1])**2)**0.5
def tour_len(p):
    route = (0,) + p + (0,)   # 都市 0 から出発して都市 0 に戻る
    return sum(dist(cities[route[i]], cities[route[i+1]]) for i in range(len(route)-1))
best = min(permutations(range(1,len(cities))), key=tour_len)
print('最短順路:', best)
print('巡回路長:', round(tour_len(best), 3))

💬 5 都市の並べ方 5! = 120 通りをすべて試し、都市 0 から出て 0 に戻る最短路は 0→1→2→5→3→4→0 で長さ 16.901。逆回り (4, 3, 5, 2, 1) も同じ 16.901 なので、min は先に出てきた方を返しているだけで、実質的な解は 1 本（向きを区別しないなら 60 通りの中の 1 本）。都市が 11 個になると並べ方は 10! = 362 万 8,800 通りに増えるため、この全列挙は 10 都市前後が限界で、それ以上は 2-opt などの近似解法に切り替える。

補足：ライブラリのバージョンや前処理状態によって出力は変わります。 自分の環境で動かすときは pip list でバージョンを確認し、 入力 CSV のパス・列名を実態に合わせてください。

🐍 Python 完全コード（4 要素ナレーション付き）

コード 1：SSDSE-B-2026 で「47 都道府県 TSP」を Nearest Neighbor で解く

🎯 このコードでやること：47 都道府県を「総人口・出生数」の 2 次元空間にマップし、 ユークリッド距離で TSP を構成。 Nearest Neighbor 法で初期解を求める。

📥 入力データ：df: SSDSE-B-2026 (2023 年データ)。 「総人口」「出生数」を都市座標として使う。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

import pandas as pd
import numpy as np
from sklearn.metrics.pairwise import euclidean_distances

df = pd.read_csv('data/raw/SSDSE-B-2026.csv', encoding='cp932', skiprows=1)
d  = df[df['年度']==2023].reset_index(drop=True)

# 都市座標: 総人口 (1e6 単位) + 出生数 (1e3 単位)
xy = np.column_stack([d['総人口'].values / 1e6,
                      d['出生数'].values / 1e3])
D = euclidean_distances(xy)

def nn_tour(D, start=0):
    n = len(D)
    visited = [start]
    remaining = set(range(n)) - {start}
    while remaining:
        nxt = min(remaining, key=lambda j: D[visited[-1]][j])
        visited.append(nxt)
        remaining.remove(nxt)
    return visited

def tour_length(t, D):
    return sum(D[t[i]][t[(i+1)%len(t)]] for i in range(len(t)))

tour = nn_tour(D, start=0)
print(f"NN 経路長 : {tour_length(tour, D):.2f}")
print(f"\n訪問順 (先頭 10):")
for i in tour[:10]:
    print(f"  {d.iloc[i]['都道府県']}")

📤 実行結果：

💬 結果の読み方：Nearest Neighbor で初期解 (経路長 171.97) を得た。 出発点 (北海道) から「総人口・出生数」の値が近い県を順に訪問。 北海道→静岡→広島と、 地理的な近さではなく 人口規模の近さ で並ぶ点に注意 (この座標は地理座標ではない)。 NN は素朴だが初期解として有用。

コード 2：2-opt で経路を改善

🎯 このコードでやること：NN 解を 2-opt 局所探索で改善し、 経路長をできるだけ短縮する。

📥 入力データ：前のコードの tour, D を使用。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

def two_opt(tour, D, max_iter=100):
    n = len(tour)
    improved = True
    iter_count = 0
    while improved and iter_count < max_iter:
        improved = False
        iter_count += 1
        for i in range(1, n - 1):
            for j in range(i + 1, n):
                new_tour = tour[:i] + tour[i:j+1][::-1] + tour[j+1:]
                if tour_length(new_tour, D) < tour_length(tour, D):
                    tour = new_tour
                    improved = True
                    break
            if improved:
                break
    return tour, iter_count

opt_tour, iters = two_opt(tour, D)
print(f"NN 経路長     : {tour_length(tour, D):.2f}")
print(f"2-opt 経路長  : {tour_length(opt_tour, D):.2f}")
print(f"改善率        : {(1 - tour_length(opt_tour, D)/tour_length(tour, D)) * 100:.2f}%")
print(f"2-opt 反復回数: {iters}")

📤 実行結果：

💬 結果の読み方：2-opt で経路長を 171.97 → 169.36 と約 1.5% 短縮。 26 回の反復で収束。 この座標空間 (総人口×出生数) は点がほぼ 1 本の帯状に並ぶため NN 解が既に良く、 改善幅は小さい。 さらに 3-opt や Lin-Kernighan を使えばより最適に近づく。 NN + 2-opt は実務でも頻用される定番組合せ。

コード 3：Held-Karp 動的計画法で厳密解 (15 都市まで)

🎯 このコードでやること：都市数を 15 に絞り、 Held-Karp DP で TSP 厳密解を求める。 NN + 2-opt との差を確認。

📥 入力データ：D の先頭 15×15 部分行列を使用。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

from python_tsp.exact import solve_tsp_dynamic_programming
from python_tsp.heuristics import solve_tsp_local_search

D15 = D[:15, :15]

# 厳密解
perm_exact, dist_exact = solve_tsp_dynamic_programming(D15)
# 近似解 (LS)
perm_ls, dist_ls = solve_tsp_local_search(D15)

print(f"Held-Karp (厳密)    : {dist_exact:.4f}")
print(f"Local Search (近似) : {dist_ls:.4f}")
print(f"近似誤差            : {(dist_ls/dist_exact - 1) * 100:.3f}%")

print(f"\n厳密解の訪問順:")
for i in perm_exact[:10]:
    print(f"  {d.iloc[i]['都道府県']}")

📤 実行結果：

💬 結果の読み方：15 都市なら Held-Karp DP で 1 秒以下で厳密解。 ローカル探索はランダムな初期解から始めるので、実行ごとに 167.6042（厳密解と一致）か 167.6062（0.001% 長い）のどちらかになる。 47 都市での DP は約 $2^{47} \times 47^2 \approx 3 \times 10^{17}$ 操作で数年かかるため、 OR-Tools/LKH などのヒューリスティックが必要。

コード 4：Google OR-Tools で 47 都道府県 TSP

🎯 このコードでやること：Google OR-Tools の Guided Local Search を使って 47 都道府県 TSP を実用品質で解く。

📥 入力データ：D: 47×47 距離行列。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

from ortools.constraint_solver import pywrapcp, routing_enums_pb2

manager = pywrapcp.RoutingIndexManager(47, 1, 0)
routing = pywrapcp.RoutingModel(manager)

def distance_callback(from_i, to_i):
    f = manager.IndexToNode(from_i)
    t = manager.IndexToNode(to_i)
    return int(D[f][t] * 10000)  # 整数化

transit_id = routing.RegisterTransitCallback(distance_callback)
routing.SetArcCostEvaluatorOfAllVehicles(transit_id)

params = pywrapcp.DefaultRoutingSearchParameters()
params.first_solution_strategy = routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC
params.local_search_metaheuristic = routing_enums_pb2.LocalSearchMetaheuristic.GUIDED_LOCAL_SEARCH
params.time_limit.seconds = 10

solution = routing.SolveWithParameters(params)
if solution:
    obj = solution.ObjectiveValue() / 10000
    print(f"OR-Tools 経路長 : {obj:.4f}")
    print(f"NN + 2-opt 比較 : {tour_length(opt_tour, D):.4f}")
    print(f"OR-Tools 改善率 : {(1 - obj/tour_length(opt_tour, D)) * 100:.2f}%")

📤 実行結果：

💬 結果の読み方：OR-Tools の Guided Local Search で経路長 169.05 を達成。 NN + 2-opt より 0.18% 改善。 10 秒で実行完了。 産業界では Amazon・UPS が同様のソルバーを使い毎日数百万ルートを最適化。 47 都道府県でも OR-Tools は実用的に動く。

❓ FAQ 20 問

📖 TSP（巡回セールスマン問題） の包括ガイド（追補編）

🔍 TSP（巡回セールスマン問題） の多角的解釈

TSP の決定問題

「経路長 $\leq K$ のツアーがあるか?」は NP 完全。 TSP は NP 困難。

Hamilton 閉路の厳格な定義

$G = (V, E)$ で全 $|V|$ 頂点を 1 回ずつ訪れる閉路。 TSP は重み付き Hamilton 閉路の最短。

Christofides の魔法

MST + 奇数次数頂点の完全マッチング + Euler ツアー + ショートカット。 三角不等式で 1.5 倍以内。

Lin-Kernighan の発想

k-opt を可変 k で行う。 経験的に LKH が最強。

Concorde の世界記録

2006 年 85,900 都市 (集積回路 PLA) を 136 CPU 年で厳密解。 並列計算で達成。

📓 「TSP（巡回セールスマン問題）」をさらに深掘り — 実データ実践ノート

SSDSE-B-2026 を使った段階的ハンズオン。 初学者→中級→上級と順に深めるシナリオ構成です。

ステップ 1: 都市座標

47 都道府県を「総人口・出生数」の 2D 空間にマップ。 SSDSE-B-2026 で実現。

ステップ 2: 距離行列

euclidean_distances(xy) で 47×47 行列を生成。

ステップ 3: Nearest Neighbor

起点 0 から最近未訪問を反復、 初期解を得る。

ステップ 4: 経路長

tour_length(tour, D) で総距離計算。

ステップ 5: 2-opt 改善

2 エッジを反転して短縮可能なら採用、 収束まで反復。 通常 5-20% 改善。

ステップ 6: Held-Karp

都市数を 15 まで絞れば DP で厳密解。 NN+2-opt と比較。

ステップ 7: OR-Tools

RoutingModel + Guided Local Search で 47 県を 10 秒で解決。

ステップ 8: 可視化

matplotlib で経路を線で結ぶ。 都道府県名をラベル表示。

ステップ 9: 実距離化

ユークリッドを OSRM 実道路距離に置換。 経路長が現実的に。

ステップ 10: VRP 拡張

2 台車両に分割、 容量制約付きで 47 県を分担配送。

📋 TSP（巡回セールスマン問題） チートシート

実務で頻用するコード・概念・公式を 1 ページにまとめた早見表。 印刷して机に貼っておくと便利です。

🐍 SSDSE-B-2026 × TSP（巡回セールスマン問題） 追加コード集 (4 要素ナレーション)

本編のコードに加え、 さらに 4 種の発展的コード例を 4 要素 (🎯/📥/📤/💬) 付きで提示。 段階的に「読む→動かす→改造する」を体験できます。

追加コード 1：3 つの解法で 47 都道府県 TSP を比較

🎯 このコードでやること：NN、 2-opt、 OR-Tools の経路長と実行時間を比較。

📥 入力データ：SSDSE-B-2026 の関連カラム。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

import time
import numpy as np
from sklearn.metrics.pairwise import euclidean_distances

xy = np.column_stack([d['総人口']/1e6, d['出生数']/1e3])
D = euclidean_distances(xy)

def nn_tour(D, start=0):
    n=len(D); v=[start]; rem=set(range(n))-{start}
    while rem:
        nxt=min(rem, key=lambda j: D[v[-1]][j])
        v.append(nxt); rem.remove(nxt)
    return v

def tour_len(t, D):
    return sum(D[t[i]][t[(i+1)%len(t)]] for i in range(len(t)))

def two_opt(tour, D):
    improved=True
    while improved:
        improved=False
        for i in range(1, len(tour)-1):
            for j in range(i+1, len(tour)):
                new = tour[:i] + tour[i:j+1][::-1] + tour[j+1:]
                if tour_len(new, D) < tour_len(tour, D):
                    tour = new; improved = True
    return tour

t0 = time.time()
nn = nn_tour(D)
t_nn = time.time() - t0; len_nn = tour_len(nn, D)

t0 = time.time()
opt = two_opt(nn, D)
t_opt = time.time() - t0; len_opt = tour_len(opt, D)

print(f"NN          : 経路長={len_nn:.2f}, 時間={t_nn:.3f}s")
print(f"NN + 2-opt  : 経路長={len_opt:.2f}, 時間={t_opt:.3f}s")
print(f"改善率      : {(1-len_opt/len_nn)*100:.1f}%")

📤 実行結果：

💬 結果の読み方：NN は瞬時 (1ms 未満) で、 2-opt が 0.04 秒で 1.5% 改善。 このデータでは NN 解が既に良質なため改善幅は小さいが、 「構築は速く・改善は時間をかける」という組合せ最適化の典型 trade-off (時間 vs 質) は同じ。 実務では OR-Tools/LKH でさらに改善。

追加コード 2：TSP を可視化

🎯 このコードでやること：matplotlib で経路を線で描画。 都道府県名をラベル表示。

📥 入力データ：SSDSE-B-2026 の関連カラム。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

import matplotlib.pyplot as plt

fig, ax = plt.subplots(figsize=(10, 6))
for i in range(len(opt)-1):
    x1, y1 = xy[opt[i]]
    x2, y2 = xy[opt[i+1]]
    ax.plot([x1, x2], [y1, y2], 'b-', alpha=0.5)

x_close, y_close = xy[opt[-1]], xy[opt[0]]
ax.plot([x_close[0], y_close[0]], [x_close[1], y_close[1]], 'b-', alpha=0.5)

for i, pref in enumerate(d['都道府県']):
    ax.annotate(pref, xy[i], fontsize=8)

ax.set_xlabel('総人口 (百万人)')
ax.set_ylabel('出生数 (千人)')
ax.set_title(f'47 都道府県 TSP (2-opt: {len_opt:.2f})')
plt.savefig('tsp_47.png', dpi=120)
plt.show()

📤 実行結果：

💬 結果の読み方：総人口・出生数空間で 47 県の TSP を可視化。 経路は北海道から千葉・埼玉・神奈川と大きい県を上って東京（1,409 万人）で折り返し、大阪・愛知・福岡・兵庫を経て規模の小さい県へ下り、鳥取（54 万人）付近で底を打ってから中規模の県を上り直し、茨城から北海道へ戻る。座標が人口規模なので、地図上の道順とは無関係な「規模の山を 1 周する」閉路になる。

追加コード 3：Held-Karp 動的計画法 (15 都市)

🎯 このコードでやること：python-tsp の DP で厳密解を計算、 NN+2-opt と比較。

📥 入力データ：SSDSE-B-2026 の関連カラム。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

from python_tsp.exact import solve_tsp_dynamic_programming

D15 = D[:15, :15]
perm_exact, dist_exact = solve_tsp_dynamic_programming(D15)

nn15 = nn_tour(D15)
opt15 = two_opt(nn15, D15)
len_opt15 = tour_len(opt15, D15)

print(f"Held-Karp (厳密)    : {dist_exact:.4f}")
print(f"NN + 2-opt          : {len_opt15:.4f}")
print(f"近似誤差            : {(len_opt15/dist_exact - 1)*100:.3f}%")

📤 実行結果：

💬 結果の読み方：15 都市なら NN+2-opt でも誤差 0.003% とほぼ厳密解に到達。 47 都市では局所最適にハマる可能性も。 厳密解と近似解の差を体感できる教材。

追加コード 4：OR-Tools で Guided Local Search

🎯 このコードでやること：Google OR-Tools で 47 県 TSP を解く。

📥 入力データ：SSDSE-B-2026 の関連カラム。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

from ortools.constraint_solver import pywrapcp, routing_enums_pb2

manager = pywrapcp.RoutingIndexManager(47, 1, 0)
routing = pywrapcp.RoutingModel(manager)

def dist_cb(i, j):
    return int(D[manager.IndexToNode(i)][manager.IndexToNode(j)] * 10000)

transit_id = routing.RegisterTransitCallback(dist_cb)
routing.SetArcCostEvaluatorOfAllVehicles(transit_id)

params = pywrapcp.DefaultRoutingSearchParameters()
params.first_solution_strategy = routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC
params.local_search_metaheuristic = routing_enums_pb2.LocalSearchMetaheuristic.GUIDED_LOCAL_SEARCH
params.time_limit.seconds = 5

sol = routing.SolveWithParameters(params)
or_len = sol.ObjectiveValue() / 10000
print(f"OR-Tools 経路長 : {or_len:.4f}")
print(f"NN + 2-opt 比較 : {len_opt:.4f}")
print(f"OR-Tools 改善率 : {(1 - or_len/len_opt) * 100:.2f}%")

📤 実行結果：

💬 結果の読み方：OR-Tools の Guided Local Search が NN+2-opt より 0.19% 短い経路を発見。 5 秒で完了。 大規模 (1000 都市超) でも OR-Tools が実用標準。

⚠️ よくある落とし穴

巡回セールスマン問題 を実務で扱うとき、 多くの分析者が同じところでつまずきます。 代表的な失敗パターンを先回りで押さえておくと、 後工程のトラブルを大幅に減らせます。

※ 上記は文献調査・現場経験で報告される頻度の高い注意点。 ドメインや手法のバージョンによって追加の落とし穴がある場合があります。

⚠️ さらに踏み込んだ失敗パターン 10 連

初学者を超えた中級者がハマる「2 周目の失敗例」を集めました。 本編の 5 件と合わせて 15 件のチェックリストとして活用してください。

📖 TSP（巡回セールスマン問題） 関連語拡張辞典（20 語）

本編の 10 語に加え、 さらに専門用語 20 個を整理。 文献を読むときの「分からない単語チェッカー」として使えます。

VRP

Vehicle Routing Problem。 複数車両版 TSP。

CVRP

Capacitated VRP。 容量制約付き。

VRPTW

VRP with Time Windows。 時間枠付き。

PDPTW

Pickup-Delivery Problem with TW。

ATSP

Asymmetric TSP。 距離が非対称。

mTSP

Multiple TSP。 複数巡回路。

Open TSP

出発点に戻らない TSP。

Generalized TSP

クラスタから 1 都市選択型 TSP。

Steiner TSP

中継点を追加可能な TSP。

Online TSP

都市が動的追加される。

Held-Karp

TSP DP 解法 (1962)。

Christofides

TSP 1.5 倍保証アルゴ (1976)。

Lin-Kernighan

TSP 局所探索 (1973)。

LKH

LK の Helsgaun 改良 (2000)。

Concorde

TSP 厳密解ソルバー (Bixby et al.)。

Branch and Bound

分枝限定法。 厳密最適化。

Branch and Cut

B&B + 切除平面。 ILP 標準。

Cutting Plane

解空間を平面で切る。

Subtour Elimination

部分巡回除去制約。

Lagrangian Relaxation

制約を目的関数に組込。 下界計算。

❓ FAQ 追補 20 問（中〜上級者向け）

🌟 SSDSE-B-2026 で「TSP（巡回セールスマン問題）」の総合演習

47 都道府県 × 12 年分（2012〜2023 年度）のデータを使い、 TSP（巡回セールスマン問題） を多角的に体験する総合演習。 単発の操作ではなく、 一連の分析フローを通して理解を深めます。

ハンズオン 1: 47 都道府県 TSP を 1 ジャブで実行

🎯 このコードでやること：47 都道府県 TSP を 1 ジャブで実行

📥 入力：SSDSE-B-2026.csv の 47 都道府県データ。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

import pandas as pd
import numpy as np
from sklearn.metrics.pairwise import euclidean_distances

df = pd.read_csv('data/raw/SSDSE-B-2026.csv', encoding='cp932', skiprows=1)
d  = df[df['年度']==2023].reset_index(drop=True)

xy = np.column_stack([d['総人口']/1e6, d['出生数']/1e3])
D = euclidean_distances(xy)

# 簡易 NN
n = 47
tour = [0]
remaining = set(range(1, n))
while remaining:
    nxt = min(remaining, key=lambda j: D[tour[-1]][j])
    tour.append(nxt); remaining.remove(nxt)

length = sum(D[tour[i]][tour[(i+1)%n]] for i in range(n))
print(f"NN 経路長: {length:.4f}")
print(f"\n最初の 10 訪問:")
for i in tour[:10]:
    print(f"  {d.iloc[i]['都道府県']:<6s}: 人口 {d.iloc[i]['総人口']:>9,}, 出生 {d.iloc[i]['出生数']:>5,}")

📤 実行結果：

💬 結果の読み方：Nearest Neighbor で北海道→静岡→広島→茨城…と、 「総人口×出生数」空間で規模の近い県を順に巡る (地理的な順序ではない点に注意)。 NP 困難でも 47 都市なら 0.001 秒で初期解。

🌐 関連手法・派生

• VRP (Vehicle Routing Problem)：複数車両、 容量制約付き
• 2-opt / 3-opt：経路の部分入れ替えで改善
• Lin-Kernighan：実務最強級ヒューリスティック
• Concorde：厳密解の世界記録（85,900 都市）
• 強化学習による TSP：Pointer Network, AM (Attention Model)

❓ よくある質問

🔗 関連用語 — 前提・並列・発展

「巡回セールスマン問題」をより深く理解するには、 周辺の用語を セットで 押さえるのが効率的です。 以下は前提（先に知っておくべき）、 並列（兄弟概念）、 発展（次に学ぶべき）の関係にある用語群：

クリックで各用語の詳細ページへ移動します。 全用語の体系は 用語集トップ または 概念マップ から俯瞰できます。

📚 関連グループ教材

「巡回セールスマン問題」は単独で完結する概念ではなく、 より大きな分野の一部です。 上位カテゴリの教材を読むことで、 この用語の 位置づけ が立体的に見えてきます：

• 📚 最適化 — このカテゴリの体系的解説
• 📚 機械学習の基礎 — このカテゴリの体系的解説

📚 参考文献・出典

• Applegate, D. et al. (2006). The Traveling Salesman Problem: A Computational Study. Princeton.
• Lawler, E. et al. (1985). The Traveling Salesman Problem: A Guided Tour. Wiley.
• Cook, W. (2012). In Pursuit of the Traveling Salesman. Princeton. 一般向け解説。
• Christofides, N. (1976). Worst-case analysis of a new heuristic for the TSP. Tech Report CMU.
• Helsgaun, K. (2000). An effective implementation of the Lin-Kernighan TSP heuristic. EJOR.
• Google OR-Tools 公式 https://developers.google.com/optimization/routing
• Concorde TSP Solver https://www.math.uwaterloo.ca/tsp/concorde.html
• 独立行政法人統計センター. SSDSE-B-2026 (CC BY 4.0). https://www.nstac.go.jp/use/literacy/ssdse/

🌟 拡張ハンドブック

📜 TSP の歴史

TSP は 1800 年代に Hamilton (アイルランドの数学者) が Icosian ゲームとして 12 面体の頂点を巡るパズルを発表したのが起源。 1930 年代に Karl Menger が一般化、 1950 年代に RAND 研究所で実用問題化。 1954 年に 49 都市問題が厳密解決、 2006 年に Concorde が 85,900 都市を 136 CPU 年で厳密解。 2010 年代以降は OR-Tools・Gurobi 等の実用ソルバーが進化、 ラストマイル配送・ドローン・3D プリンタ経路など多分野に応用。

📐 TSP の整数計画定式化

⚙️ TSP の解法分類

💼 TSP を実務で使う 5 つの場面

• ラストマイル配送：Amazon・UPS・FedEx の毎日数百万ルート。
• 製造業の工程最適化：プリント基板の穴あけ順序、 ピッキングロボット経路。
• ドローン配送：複数地点の最短訪問。
• 遺伝子シーケンシング：DNA 断片の最適配置 (TSP 変種)。
• 観光ルート設計：観光地巡り、 修学旅行プランニング。

📊 47 都道府県 TSP の難易度感

47 都市は Held-Karp（計算量 O(2ⁿn²)）では 2⁴⁷×47² ≈ 3×10¹⁷ 回の更新が必要で現実的に解けないが、 Concorde のような分枝カット法なら厳密解が得られる規模。 Christofides は三角不等式の下で最適の 1.5 倍以内が理論保証、 2-opt・LKH の「最適から数 % 以内」は理論保証ではなく経験的な目安。 教育用には、 15 都市程度まで絞れば Held-Karp の厳密解と近似解を並べて比べられる。

📚 50 連発レシピ集（TSP（巡回セールスマン問題） × Python）

SSDSE-B-2026 を題材に、 TSP（巡回セールスマン問題） の実装を 50 ミニコードで一気に俯瞰します。

1. import numpy as np; from scipy.spatial.distance import cdist
2. xy = np.column_stack([d['総人口']/1e6, d['出生数']/1e3]) — SSDSE-B-2026 から都市座標
3. D = cdist(xy, xy) — 距離行列
4. def nn_tour(D, start=0): n=len(D); v=[start]; rem=set(range(n))-{start} while rem: nxt=min(rem, key=lambda j: D[v[-1]][j]); v.append(nxt); rem.remove(nxt) return v
5. tour = nn_tour(D)
6. def tour_length(tour, D): return sum(D[tour[i]][tour[(i+1)%len(tour)]] for i in range(len(tour)))
7. print(tour_length(tour, D))
8. from itertools import permutations
9. best = min(permutations(range(1,5)), key=lambda p: tour_length([0]+list(p), D))
10. print('厳密解:', best) — 5 都市までなら全探索可
11. def two_opt(tour, D): improved=True while improved: improved=False for i in range(1,len(tour)-1): for j in range(i+1,len(tour)): new=tour[:i]+tour[i:j+1][::-1]+tour[j+1:] if tour_length(new,D)<tour_length(tour,D): tour=new; improved=True return tour
12. opt_tour = two_opt(nn_tour(D), D)
13. print('2-opt:', tour_length(opt_tour, D))
14. from ortools.constraint_solver import pywrapcp, routing_enums_pb2
15. m = pywrapcp.RoutingIndexManager(47, 1, 0)
16. routing = pywrapcp.RoutingModel(m)
17. def d_cb(i,j): return int(D[m.IndexToNode(i)][m.IndexToNode(j)] * 1000)
18. t = routing.RegisterTransitCallback(d_cb)
19. routing.SetArcCostEvaluatorOfAllVehicles(t)
20. sp = pywrapcp.DefaultRoutingSearchParameters()
21. sp.local_search_metaheuristic = routing_enums_pb2.LocalSearchMetaheuristic.GUIDED_LOCAL_SEARCH
22. sp.time_limit.seconds = 10
23. sol = routing.SolveWithParameters(sp)
24. print('OR-Tools 解:', sol.ObjectiveValue()/1000)
25. import pandas as pd; df=pd.read_csv('data/raw/SSDSE-B-2026.csv',encoding='cp932',skiprows=[1])
26. d = df[df['年度']==2023]
27. print('47 都道府県、 TSP 入力データ準備完了')
28. from sklearn.metrics.pairwise import euclidean_distances
29. D = euclidean_distances(np.column_stack([d['総人口'], d['出生数']]))
30. print('人口空間での距離行列:', D.shape)
31. tour_nn = nn_tour(D)
32. print('NN 経路長:', tour_length(tour_nn, D))
33. tour_opt = two_opt(tour_nn, D)
34. print('2-opt 改善:', tour_length(tour_opt, D))
35. print('改善率:', (1-tour_length(tour_opt,D)/tour_length(tour_nn,D))*100, '%')
36. import matplotlib.pyplot as plt
37. plt.plot([xy[i][0] for i in tour_opt+[tour_opt[0]]], [xy[i][1] for i in tour_opt+[tour_opt[0]]], 'o-')
38. plt.show()
39. from python_tsp.exact import solve_tsp_dynamic_programming
40. perm, dist = solve_tsp_dynamic_programming(D[:15, :15])
41. print('Held-Karp:', dist)
42. from python_tsp.heuristics import solve_tsp_local_search
43. perm, dist = solve_tsp_local_search(D)
44. print('LS:', dist)
45. print('Christofides 三角不等式チェック')
46. print('TSP は P=NP? 問題の代表例')
47. print('実務は OR-Tools か Gurobi が定番')
48. print('🎓 TSP の本質：探索空間 (n-1)!/2 を効率的に切り詰める')

🗺 概念マップ

TSP (巡回セールスマン問題) を中心に、 NP 困難性・厳密解法 (整数計画/分枝限定)・近似解法 (最近傍/2-opt/遺伝的)・実応用 (物流/配車) への分岐を 6 方向に整理。

TSP の中心から、 2-opt / 3-opt (局所探索)、 遺伝アルゴリズム、 Lin-Kernighan ヒューリスティック、 Concorde solver、 強化学習による TSP (Pointer Network) が放射状に配置される。 SSDSE-B-2026 の 47 都道府県庁所在地を点群と見立て、 全 47 都市を最短で巡回する経路問題は古典的 TSP の好例。

🔗 隣接手法への橋渡し

TSP は組合せ最適化の基礎で、 上流の問題定式化から下流の経路可視化まで多様な手法と連携する。

• 上流: 距離行列 構築 (47 県緯度経度から Haversine で 47×47 行列)、 制約モデル化 (時間窓・容量)
• 並列: VRP (Vehicle Routing Problem) (複数車両)、 CVRP (容量制約付き)、 最短経路問題 (出発・到着固定)、 ハミルトン路問題
• 下流: 最適 tour の評価 (総距離・最大区間)、 地図可視化 (folium / plotly で 47 県を結ぶ路線)、 感度分析 (距離 ±10% で経路がどう変わるか)

SSDSE-B-2026 から「47 県庁所在地を 1 回ずつ訪問」する場合、 OR-Tools で約 2 秒、 距離は約 8500km。 ブルートフォースだと 47! ≈ 10^58 通りで不可能。

🌳 手法選択フロー

TSP を解く方法は、 都市数 n の大きさで 4 通りに分岐する。

1. n ≤ 15? Yes → 動的計画法 (Held-Karp) で厳密解 O(n²2ⁿ)
2. n ≤ 200? Yes → 分枝限定法 + cutting plane (Concorde solver) で厳密解
3. n ≤ 10000? Yes → 2-opt / LKH + Or-Tools で 1-2% 誤差の近似解
4. n > 10000 or 動的に都市が増減? Yes → GA / 蟻コロニー / Pointer Network (強化学習)

SSDSE-B-2026 の 47 県は n=47 なので Concorde で厳密解可能。 ただし都内 23 区を含めると n=70 になり、 OR-Tools の近似で実用十分。