この記事について
前回の記事ではTSP（巡回セールスマン問題）の基礎概念と、アプローチの全体像を説明しました。
今回はその第一歩として、近傍法（Nearest Neighbor Heuristic） を説明します。
「まず動くルートを素早く作る」ための構築ヒューリスティクスです。シンプルですが、後続の改善手法の出発点になる重要なアルゴリズムです。
配送最適化入門シリーズの記事一覧はこちら。
| 記事 | 内容 |
|---|---|
| ⓪ | 配送最適化とは？基礎概念 |
| ①（本記事） | 近傍法の説明 |
| ② | 2-optの説明 |
| ③ | 3-optの説明 |
| ④ | Lin-Kernighan法の説明 |
| ⑤ | 焼きなまし法（SA）の説明 |
| ⑥ | 遺伝的アルゴリズム（GA）の説明 |
| ⑦ | VRPとは？ |
| ⑧ | VRPをアルゴリズムで解く |
近傍法とは？
近傍法（Nearest Neighbor Heuristic）は、「今いる都市から最も近い未訪問の都市へ移動する」 という単純なルールでルートを構築するアルゴリズムです。
人間が地図を見ながら「とりあえず近いところから回ろう」と考えるのとほぼ同じ発想です。
アルゴリズムの手順
① 出発都市をランダム（または固定）に選ぶ
② 現在地から最も近い未訪問の都市へ移動する
③ すべての都市を訪問するまで②を繰り返す
④ 最後に出発地へ戻る
具体例
5都市の例で考えてみましょう。都市0からスタートするとします。
都市0 → 最近傍=都市3 → 最近傍=都市1 → 最近傍=都市4 → 最近傍=都市2 → 都市0に戻る
このように、訪問済みの都市を除きながら「次に近い都市」を貪欲に選んでいきます。
Python実装
import numpy as np
import matplotlib
import matplotlib.pyplot as plt
plt.rcParams['font.family'] = 'Yu Gothic'
def generate_cities(n=20, seed=42):
"""ランダムな都市座標を生成"""
np.random.seed(seed)
return np.random.rand(n, 2) * 100
def calc_distance(cities):
"""都市間の距離行列を計算"""
n = len(cities)
dist = np.zeros((n, n))
for i in range(n):
for j in range(n):
diff = cities[i] - cities[j]
dist[i][j] = np.sqrt(np.sum(diff ** 2))
return dist
def total_distance(route, dist):
"""ルートの総距離を計算"""
n = len(route)
return sum(dist[route[i]][route[(i + 1) % n]] for i in range(n))
def nearest_neighbor(dist, start=0):
"""
近傍法によるTSP解の構築
dist: 距離行列
start: 出発都市のインデックス
"""
n = len(dist)
unvisited = set(range(n))
route = [start]
unvisited.remove(start)
while unvisited:
current = route[-1]
# 未訪問都市の中で最も近い都市を選ぶ
nearest = min(unvisited, key=lambda city: dist[current][city])
route.append(nearest)
unvisited.remove(nearest)
return route
実行してみる
cities = generate_cities(n=20, seed=42)
dist = calc_distance(cities)
# 全都市をスタート地点として試し、最良のものを選ぶ
best_route = None
best_dist = float('inf')
for start in range(len(cities)):
route = nearest_neighbor(dist, start=start)
d = total_distance(route, dist)
if d < best_dist:
best_dist = d
best_route = route
print(f'近傍法の総距離: {best_dist:.1f}')
print(f'最良スタート都市: {best_route[0]}')
近傍法の総距離: 603.2
最良スタート都市: 7
可視化
def plot_route(cities, route, title='Route'):
plt.figure(figsize=(7, 6))
plt.scatter(cities[:, 0], cities[:, 1], c='red', s=80, zorder=5)
for i, (x, y) in enumerate(cities):
plt.annotate(str(i), (x + 1.5, y + 1.5), fontsize=8)
for i in range(len(route)):
c1 = cities[route[i]]
c2 = cities[route[(i + 1) % len(route)]]
plt.plot([c1[0], c2[0]], [c1[1], c2[1]], 'b-', linewidth=1.2, alpha=0.7)
d = total_distance(route, calc_distance(cities))
plt.title(f'{title} (総距離: {d:.1f})')
plt.grid(True, alpha=0.3)
plt.tight_layout()
plt.savefig('route_nn.png', dpi=150)
plt.show()
plot_route(cities, best_route, title='近傍法')
近傍法の長所と短所
長所
- 実装がシンプル：数十行で書ける
- 高速：計算量は $O(n^2)$ で大規模な問題にも使いやすい
- 直感的に理解しやすい：「近いところから回る」だけ
短所
- 局所的な選択のため大域的に最悪になることがある：目先の最短を選び続けると、最後の方で遠回りになりやすい
- スタート都市によって結果が変わる：スタートを変えて複数試すのが有効
近傍法が失敗するケース
近傍法の弱点として「最後の戻りで長い辺が生まれる」問題があります。
この問題を解消するのが、次回から説明する改善ヒューリスティクスです。
スタート都市の工夫
全スタート都市を試すのが最も確実ですが、都市数が多い場合はコストがかかります。
代わりに「最も外側の都市（凸包の頂点）からスタートする」という工夫もよく使われます。
まとめ
今回は近傍法を説明しました。
- 近傍法：今いる都市から最も近い未訪問都市へ移動し続ける構築ヒューリスティクス
- シンプルで高速だが、局所的な選択で全体が最悪になりやすい
- スタート都市を複数試すことで改善できる
次回は近傍法で作ったルートをさらに改善する2-optを説明します。
参考にした記事や本、論文等
- D. S. Johnson and L. A. McGeoch, "The Traveling Salesman Problem: A Case Study in Local Optimization," in Local Search in Combinatorial Optimization, pp. 215-310, 1997.