🕴️

Pythonで巡回セールスマン問題を解く

まつの | AIエンジニア

2025/10/16に公開

はじめまして、まつのです！

機械学習や生成AIの受託開発・AI学習サービス「aipass」の運営をしている株式会社dotConfという会社で、代表をしております！

この記事では、Pythonを使って巡回セールスマン問題を解く方法についてわかりやすく解説します。

巡回セールスマン問題とは？

巡回セールスマン問題は、複数の都市を一度ずつ訪れ、出発点に戻る最短ルートを求める問題です。ここでは、出発点・ゴールを「東京駅」とし、途中で「上野駅・新宿駅・渋谷駅・品川駅」を一度ずつ訪問する例を考えます。

これらの駅間の距離を以下のように定義します。実運用では地図APIや実測データを使いますが、ここでは説明のために駅間の「所要時間イメージ」に近い簡易な距離を仮定して使います。

	東京	上野	新宿	渋谷	品川
東京	0	4	7	7	6
上野	4	0	8	9	10
新宿	7	8	0	3	7
渋谷	7	9	3	0	5
品川	6	10	7	5	0

全探索を実装してみる

Pythonで全てのパターンの距離を計算してみましょう。

from itertools import permutations

# 駅の並びを定義（先頭は東京：出発・到着点）
stations = ["東京", "上野", "新宿", "渋谷", "品川"]

# 距離行列（対称・完全グラフを仮定）
dist = {
    ("東京", "上野"): 4,  ("上野", "東京"): 4,
    ("東京", "新宿"): 7,  ("新宿", "東京"): 7,
    ("東京", "渋谷"): 7,  ("渋谷", "東京"): 7,
    ("東京", "品川"): 6,  ("品川", "東京"): 6,
    ("上野", "新宿"): 8,  ("新宿", "上野"): 8,
    ("上野", "渋谷"): 9,  ("渋谷", "上野"): 9,
    ("上野", "品川"): 10, ("品川", "上野"): 10,
    ("新宿", "渋谷"): 3,  ("渋谷", "新宿"): 3,
    ("新宿", "品川"): 7,  ("品川", "新宿"): 7,
    ("渋谷", "品川"): 5,  ("品川", "渋谷"): 5,
}

start = "東京"
others = [s for s in stations if s != start]

def route_length(route):
    """route は ['東京', ..., '東京'] のような巡回ルート"""
    total = 0
    for a, b in zip(route, route[1:]):
        total += dist[(a, b)]
    return total

best_route = None
best_cost = float("inf")

# 中間の並びを総当たり
for order in permutations(others):
    route = [start] + list(order) + [start]
    cost = route_length(route)
    if cost < best_cost:
        best_cost = cost
        best_route = route

print("最短ルート:", " → ".join(best_route))
print("総距離:", best_cost)

最短ルート: 東京 → 新宿 → 渋谷 → 品川 → 上野 → 東京
総距離: 25

東京駅の次にどの駅に行くか：4通り
次にどの駅に行くか：3通り
次にどの駅に行くか：2通り
次にどの駅に行くか：1通り

というように、駅の数がnのとき、並べ替える通り数は ((n-1)!)（出発・到着を固定するため）となります。今回の5駅なら (4! = 24) 通りなので一瞬で終わりますが、10駅では (9! = 362,880) 通りと爆発的にパターンが増え、20駅までいくと現実的には、計算が終わらなくなります。これが「巡回セールスマン問題」が難しいと言われる最大の理由です。

駅の数（n）	訪問順序の数（(n−1)!）	概算
5	24	瞬時に計算可能
8	5,040	数秒〜数十秒
10	362,880	数分
12	39,916,800	数時間
15	871億通り	現実的に不可能

現実的なアプローチ

全探索では正解を100%保証できますが「現実的な計算コストで、ほどほどに良いルート」を求めたいケースでは次のような近似法・改善法が使われます。

方法	概要	特徴
貪欲法（Greedy）	近い駅から順に選んでいく	速いが、最適解ではないことが多い
2-opt法	経路の一部を入れ替えて改善	シンプルで実用的
遺伝的アルゴリズム	複数ルートを進化的に最適化	大規模問題に対応可
数理最適化（OR-Toolsなど）	ソルバが最適化を自動で実施	精度高いが設定がやや複雑

ここでは最も汎用的で実務にも応用できる数理最適化（整数計画法）で実装してみます。モデル化には古典的な MTZ（Miller–Tucker–Zemlin）法を採用数理最適化について知りたいかはこちらの記事も読んでみてください！

まずは事前準備としてライブラリをインストールしておきましょう。

pip install pulp

1. データ(駅と距離)の定義

例として、東京駅を出発・到着に固定し、「上野」「新宿」「渋谷」「品川」を巡回するケースを考えます。駅間の距離は仮のデータですが、対称的（行きと帰りが同じ距離）とします。

# 駅のリストとインデックス
nodes = ["東京", "上野", "新宿", "渋谷", "品川"]
idx = {name: i for i, name in enumerate(nodes)}
n = len(nodes)
start = idx["東京"]  # 東京を出発・到着に固定

# 駅間距離（仮の値、単位はkmなど）
pairs = {
    ("東京","上野"):4, ("東京","新宿"):7, ("東京","渋谷"):7, ("東京","品川"):6,
    ("上野","新宿"):8, ("上野","渋谷"):9, ("上野","品川"):10,
    ("新宿","渋谷"):3, ("新宿","品川"):7,
    ("渋谷","品川"):5,
}

# 対称な距離行列を作成
D = [[0]*n for _ in range(n)]
for (a,b), w in pairs.items():
    i, j = idx[a], idx[b]
    D[i][j] = D[j][i] = w

2. 数理最適化モデルの定義

どの駅からどの駅へ移動するかを示す二値変数を定義します。

$x_{ij} \in \{0,1\}$

駅 $i$ から $j$ へ移動するなら1、そうでなければ0とします。

import pulp

prob = pulp.LpProblem("TSP_MTZ_Tokyo", pulp.LpMinimize)

# x[i][j]: 駅i→jを通るなら1、そうでなければ0
x = [[None]*n for _ in range(n)]
for i in range(n):
    for j in range(n):
        if i != j:
            x[i][j] = pulp.LpVariable(f"x_{i}_{j}", 0, 1, cat="Binary")

3. 目的関数：総移動距離を最小化する

最短経路問題のゴールは「移動距離の合計を最小化する」ことです。これを式で表すと、次のようになります。

\text{Minimize} \quad \sum_{i}\sum_{j} d_{ij} \, x_{ij}

ここで：

$d_{ij}$ ：駅 $i$ から $j$ までの距離
$x_{ij}$ ：その区間を実際に使う場合は 1、使わなければ 0

つまり「どのルートを通るか」が決まれば、そのルート上の距離 $d_{ij}$ の合計が自動的に計算されます。最適化ソルバは、この合計が最も小さくなるように $x_{ij}$ の値（＝どの経路を使うか）を決定します。

# 目的関数：総距離を最小化
prob += pulp.lpSum(D[i][j] * x[i][j] for i in range(n) for j in range(n) if i != j)

4. 各駅を1回だけ訪問する制約

各駅は一度だけ訪れる必要があります。つまり、「入る本数＝1」「出る本数＝1」という制約を追加します。

for i in range(n):
    prob += pulp.lpSum(x[i][j] for j in range(n) if j != i) == 1  # 出る
    prob += pulp.lpSum(x[j][i] for j in range(n) if j != i) == 1  # 入る

5. 部分ループを防ぐ制約

ここまでの制約だけでは、「東京→新宿→東京」や「上野→渋谷→上野」のように 小さな輪 が複数できる可能性があります。これを防ぐために、補助変数 $u_i$ を導入します。 $u_i$ は巡回順序を表す整数で、次の制約を加えます：

u_i - u_j + n \, x_{ij} \le n - 1 \quad (i \ne j)

これは、「もし $i \to j$ を通るなら、 $j$ は $i$ より後に訪問される」
と読み替えることができます。

# 補助変数 u[i]: 巡回順序を表す
u = [pulp.LpVariable(f"u_{i}", lowBound=(0 if i==start else 1), upBound=n-1, cat="Integer")
     for i in range(n)]
# 始点（東京）の順位を 0 に固定（重要）
prob += u[start] == 0


# MTZ制約
for i in range(n):
    for j in range(n):
        if i != j and i != start and j != start:
            prob += u[i] - u[j] + n*x[i][j] <= n - 1

6. 解を求めルートを復元

PuLP の内蔵ソルバ（CBC）を使って最適化します。どの駅からどの駅へ移動したか（x[i][j]=1）を辿って、ルートを再構築します。

prob.solve(pulp.PULP_CBC_CMD(msg=False))

route = [start]
cur = start
while len(route) < n:
    for j in range(n):
        if j != cur and x[cur][j].value() > 0.5:
            route.append(j)
            cur = j
            break
route.append(start)

# 出力
named = " → ".join(nodes[i] for i in route)
total = sum(D[route[k]][route[k+1]] for k in range(len(route)-1))
print("最適ルート:", named)
print("総距離:", total)

最適ルート: 東京 → 新宿 → 渋谷 → 品川 → 上野 → 東京
総距離: 25

まとめ

このように、数理最適化を使うことで「数学的に最も短いルート」を厳密に導くことができます。
小規模であれば現実的な時間で解けるため、配送ルートの設計や訪問順最適化などにも応用できます

Pythonを学習したい方へ

Pythonを体系的に学び、プロの指導のもとで実践的なAIスキルを習得したい方、
キャリアの幅を広げたい方や複業を目指す方は、ぜひこちらからお問い合わせください。
https://b2c.aipass.tech
https://lin.ee/pbd6SZJ

Zenn以外の情報発信媒体はこちら👇

dotConf, Inc

株式会社dotConfのテックブログです！生成AIや機械学習・データ分析を中心にノウハウを発信していきます。dotConfは、AI技術のPoC・開発から運用に至るまで、企業課題解決を支援するAIソリューション事業と、AI学習サービス「aipass」を運営しています。お問合先→info@dotconf.co.jp