複数地点を効率よく回る経路を求める ― Pythonで巡回経路探索（TSP）入門

1. はじめに

複数地点を効率よく回る経路を求める 巡回経路探索（巡回セールスマン問題：TSP） を、Pythonで実装してみます。

今回は、基本的なアルゴリズムを取り上げ、実装から結果の確認までを行います。

2. 巡回経路探索（TSP）とは

巡回経路探索（TSP） とは、訪問すべき複数の地点（都市や観光地など）のリストを基に、
すべての地点を1回ずつ訪問して最後に出発点に戻るときの 最短経路 を求める問題です。

実世界での応用例

• 営業・訪問活動：複数顧客を回る営業ルートの最適化
• 配送・物流：倉庫から各配達先を回って再び倉庫に戻るトラックルート
• 観光：観光スポットを効率よく回るモデルコースの作成

巡回経路探索 はシンプルに見えますが、地点数が増えると組合せが急激に増大し、効率的な探索が難しくなるという特徴があります。

3. 代表的な解法の概要

巡回経路探索（TSP）は、地点数が増えると組合せが爆発的に増加するため、
解法は大きく 厳密解 と 近似解 に分けられます。

厳密解

• 小規模（地点数10〜12程度）であれば、動的計画法（Held–Karpアルゴリズム） などで最適解を求めることができます。
• 分枝限定法や整数計画法でも解けますが、計算量は指数関数的に増えるため、大規模には不向きです。
• 特徴：必ず最適解を保証できる。

近似解（ヒューリスティック）

必ずしも最適解ではありませんが、現実的な時間で「十分良い解」を得ることができます。

• 最近近傍法（Nearest Neighbor, NN）

  • 現在地点から最も近い未訪問地点を順に選んで経路を作る。
  • 計算が速くシンプルですが、全体としては遠回りなルートになることもある。

• 2-opt 改善法

  • 経路内の2本の辺を入れ替えて交差をなくすことでルートを改善する。
  • NNなどで作った初期解を入力にすると、かなり短い経路を得られる。
  • 繰り返せば局所的に最適な解に収束する。

解法の位置づけ

• 小規模：厳密解で最適ルートを求められる
• 中規模以上：NNで初期解を作り、2-optで改善するのが典型的なアプローチ
• この組み合わせはシンプルで計算も軽く、多くの場面で有効に機能する

4. サンプルデータの準備

ここではサンプルとして、東京都内の観光スポットをいくつか用意します。
名称と緯度経度をリストにまとめ、アルゴリズムの入力として利用します。

places = [
    ("東京駅", 35.681236, 139.767125),
    ("浅草寺", 35.714765, 139.796655),
    ("東京スカイツリー", 35.710063, 139.8107),
    ("上野公園", 35.714167, 139.774444),
    ("渋谷駅", 35.658034, 139.701636),
]

ここでは便宜的に少数の地点だけを対象にしていますが、
アルゴリズム自体はより多くの地点に対しても同じように利用できます。

5. 距離計算

地点間の移動距離を求めるために、ここでは地球上の2点間の直線距離（大円距離）を計算します。
代表的な方法として ハーサイン（Haversine）公式 を利用します。

ハーサイン距離の関数

import math

def haversine(lat1, lon1, lat2, lon2):
    """2地点間の距離をキロメートル単位で返す"""
    R = 6371.0  # 地球の半径[km]
    phi1, phi2 = math.radians(lat1), math.radians(lat2)
    dphi = math.radians(lat2 - lat1)
    dlambda = math.radians(lon2 - lon1)

    a = math.sin(dphi/2)**2 + math.cos(phi1) * math.cos(phi2) * math.sin(dlambda/2)**2
    return 2 * R * math.asin(math.sqrt(a))

距離行列の作成

次に、すべての地点ペアについて距離を計算し、距離行列を作ります。

def build_distance_matrix(places):
    n = len(places)
    D = [[0.0]*n for _ in range(n)]
    for i in range(n):
        for j in range(i+1, n):
            d = haversine(places[i][1], places[i][2], places[j][1], places[j][2])
            D[i][j] = D[j][i] = d
    return D

# サンプルデータで距離行列を作成
D = build_distance_matrix(places)
for row in D:
    print([round(d, 2) for d in row])

6. 最近近傍法（NN）の実装

最近近傍法（Nearest Neighbor, NN） は、
「現在地から最も近い未訪問地点を順に選んでいく」シンプルな手法です。

アルゴリズムの流れは以下の通りです。

1. 任意の地点からスタートする
2. まだ訪問していない地点の中から、最も近い地点を選んで移動する
3. すべての地点を訪問するまで繰り返す
4. 最後に出発点に戻る

実装例

def nearest_neighbor(D, start=0):
    n = len(D)
    assert 0 <= start < n, "start が範囲外です"
    unvisited = set(range(n))
    unvisited.discard(start)
    route = [start]
    current = start

    while unvisited:
        next_city = min(unvisited, key=lambda j: D[current][j])
        unvisited.remove(next_city)
        route.append(next_city)
        current = next_city

    # 出発点に戻る（閉路）
    route.append(start)
    return route

最近近傍法は計算が速い一方で、
局所的な最短選択の積み重ねにより、全体としては遠回りになることもあります。
この弱点を補うために、次章では 2-opt 改善法 を紹介します。

7. 2-opt による改善

2-opt 改善法 は、ルートの交差をなくして経路を短縮するシンプルな改善手法です。

アルゴリズムの流れは以下の通りです。

1. 現在のルートから任意の2本の辺を選ぶ
2. それらを「入れ替え」て経路が交差しないようにする
3. もし総距離が短くなれば、そのルートを採用する
4. これを改善が見られなくなるまで繰り返す

def two_opt(route, D):
    best = route[:]
    improved = True
    while improved:
        improved = False
        for i in range(1, len(best) - 2):
            for j in range(i + 1, len(best) - 1):
                if j - i == 1:  # 隣接区間は入れ替え不要
                    continue
                new_route = best[:i] + best[i:j][::-1] + best[j:]
                if total_distance(D, new_route) < total_distance(D, best):
                    best = new_route
                    improved = True
    return best

スクリプト全体

import math

# ---- サンプルデータ（東京都内のスポット） --------------------
places = [
    ("東京駅",         35.681236, 139.767125),
    ("浅草寺",         35.714765, 139.796655),
    ("東京スカイツリー", 35.710063, 139.810700),
    ("上野公園",       35.714167, 139.774444),
    ("渋谷駅",         35.658034, 139.701636),
]

# ---- 距離（ハーサイン：大円距離, km） ------------------------
def haversine(lat1, lon1, lat2, lon2) -> float:
    """2地点間の大円距離を km 単位で返す。"""
    R = 6371.0  # 地球半径 [km]
    phi1, phi2 = math.radians(lat1), math.radians(lat2)
    dphi = math.radians(lat2 - lat1)
    dlmb = math.radians(lon2 - lon1)
    a = math.sin(dphi / 2) ** 2 + math.cos(phi1) * math.cos(phi2) * math.sin(dlmb / 2) ** 2
    return 2 * R * math.asin(math.sqrt(a))

# ---- 距離行列の作成（対称性を利用して計算を半分に） ----------
def build_distance_matrix(places):
    n = len(places)
    D = [[0.0] * n for _ in range(n)]
    for i in range(n):
        for j in range(i + 1, n):
            d = haversine(places[i][1], places[i][2], places[j][1], places[j][2])
            D[i][j] = D[j][i] = d
    return D

# ---- 総距離の計算（閉路前提） --------------------------------
def total_distance(D, route) -> float:
    """route は都市インデックスの並び（最後は出発点に戻る前提）。"""
    return sum(D[route[i]][route[i + 1]] for i in range(len(route) - 1))

# ---- 最近近傍法（初期解生成） ---------------------------------
def nearest_neighbor(D, start=0):
    """距離行列 D を受け取り、start から始めて NN で巡回し、最後に start に戻るルートを返す。"""
    n = len(D)
    assert 0 <= start < n, "start が範囲外です"
    unvisited = set(range(n))
    unvisited.discard(start)
    route = [start]
    current = start

    while unvisited:
        next_city = min(unvisited, key=lambda j: D[current][j])
        unvisited.remove(next_city)
        route.append(next_city)
        current = next_city

    # 出発点に戻る（閉路）
    route.append(start)
    return route

# ---- 2-opt 改善法（個別掲載と同一実装） ----------------------
def two_opt(route, D):
    best = route[:]  # シャローコピー（参照共有を避ける）
    improved = True
    while improved:
        improved = False
        for i in range(1, len(best) - 2):
            for j in range(i + 1, len(best) - 1):
                if j - i == 1:  # 隣接区間は入れ替え不要
                    continue
                new_route = best[:i] + best[i:j][::-1] + best[j:]
                if total_distance(D, new_route) < total_distance(D, best):
                    best = new_route
                    improved = True
    return best

# ---- 実行例 ---------------------------------------------------
if __name__ == "__main__":
    D = build_distance_matrix(places)

    # 初期解（NN）
    start = 0
    route_nn = nearest_neighbor(D, start=start)
    dist_nn = total_distance(D, route_nn)

    # 2-opt 改善
    route_2opt = two_opt(route_nn, D)
    dist_2opt = total_distance(D, route_2opt)

    # 出力（インデックスと名称）
    def route_names(route, places):
        return [places[i][0] for i in route]

    print("NN ルート（インデックス）:", route_nn)
    print("NN ルート（名称）       :", " -> ".join(route_names(route_nn, places)))
    print(f"NN 総距離: {dist_nn:.2f} km")

    print("2-opt ルート（インデックス）:", route_2opt)
    print("2-opt ルート（名称）       :", " -> ".join(route_names(route_2opt, places)))
    print(f"2-opt 総距離: {dist_2opt:.2f} km")


# ---- 実行結果 --------------------------------------------
# NN ルート（インデックス）: [0, 3, 1, 2, 4, 0]
# NN ルート（名称）       : 東京駅 -> 上野公園 -> 浅草寺 -> 東京スカイツリー -> 渋谷駅 -> 東京駅
# NN 総距離: 24.98 km
# 
# 2-opt ルート（インデックス）: [0, 2, 1, 3, 4, 0]
# 2-opt ルート（名称）       : 東京駅 -> 東京スカイツリー -> 浅草寺 -> 上野公園 -> 渋谷駅 -> 東京駅
# 2-opt 総距離: 23.97 km

2-opt により、初期の NN ルートよりも短い経路を得られることが分かります。
このように「単純な初期解 → 改善アルゴリズム」の組み合わせは、TSPの代表的なアプローチです。

次章では、この結果を地図上に可視化して確認します。

8. 結果の確認（地図表示）

計算結果を地図上に表示してみます。

folium を使った可視化

import folium

def plot_route_numbered(places, route, filename="route.html", color="blue"):

    start_idx = route[0]
    center = [places[start_idx][1], places[start_idx][2]]
    m = folium.Map(location=center, zoom_start=13)

    # ルート座標（閉路でなければ最後に開始点を追加して線を閉じる）
    def to_latlons(r):
        return [(places[i][1], places[i][2]) for i in r]

    latlons = to_latlons(route)
    if route[-1] != route[0]:
        latlons.append((places[start_idx][1], places[start_idx][2]))

    # 線を描画
    folium.PolyLine(latlons, weight=3, opacity=0.85, color=color).add_to(m)

    # 訪問順の番号（routeが閉路なら最後の重複を除く）
    seq = route[:-1] if route[-1] == route[0] else route[:]

    for order, idx in enumerate(seq, start=1):
        name, lat, lon = places[idx]

        # 丸番号バッジ
        badge = f"""
        <div style="
            background:white; border: 2px solid {'#2b8a3e' if order==1 else '#333'};
            color: {'#2b8a3e' if order==1 else '#333'};
            width: 26px; height: 26px; line-height: 22px;
            text-align: center; font-weight: 700;
            border-radius: 50%; font-size: 13px;">
            {order}
        </div>
        """
        icon = folium.DivIcon(html=badge, icon_size=(26,26), icon_anchor=(13,13))

        # ポップアップ
        popup_html = f"""
        <div style="white-space: nowrap; word-break: keep-all; font-size: 14px; line-height: 1.4;">
            {order}: {name}
        </div>
        """
        popup = folium.Popup(popup_html, max_width=400)

        # ついでにツールチップ（ホバー時）も表示
        tooltip = folium.Tooltip(f"{order}: {name}", sticky=True)

        folium.Marker(
            location=[lat, lon],
            icon=icon,
            popup=popup,
            tooltip=tooltip
        ).add_to(m)

    # 開始/終了のリング強調
    start_lat, start_lon = places[start_idx][1], places[start_idx][2]
    folium.CircleMarker(
        location=[start_lat, start_lon],
        radius=8, fill=True, fill_opacity=0.7,
        color="#2b8a3e", fill_color="#2b8a3e",
        popup="START"
    ).add_to(m)

    end_idx = seq[-1]
    end_lat, end_lon = places[end_idx][1], places[end_idx][2]
    folium.CircleMarker(
        location=[end_lat, end_lon],
        radius=7, fill=True, fill_opacity=0.7,
        color="#c92a2a", fill_color="#c92a2a",
        popup="END" if end_idx != start_idx else "END (=START)"
    ).add_to(m)

    m.save(filename)
    return filename


# 例: すでに route_nn と route_2opt が計算済みのとき
plot_route_numbered(places, route_nn,   filename="route_nn.html",   color="blue")
plot_route_numbered(places, route_2opt, filename="route_2opt.html", color="red")

最近近傍法（NN）

2-opt 改善法

9. まとめ

本記事では、複数地点を効率よく回る経路を求める 巡回経路探索（TSP） を Python で実装しました。
代表的な手法は次の2つです。

• 最近近傍法（NN）
  現在地から最も近い未訪問地点を順に選んでいくシンプルな方法。

• 2-opt 改善法
  経路の一部を入れ替えて交差をなくし、ルートを改善する方法。

今回扱った方法はシンプルですが、少数の地点を回るケースであれば有効に機能します。
地点数が増える場合や制約条件がある場合には、さらに工夫された手法が必要になります。