この記事について
前回は近傍法でルートを構築しました。今回はその初期解をさらに改善する2-opt を説明します。
2-optは局所探索（ローカルサーチ）の代表的な手法で、「2本の辺を入れ替えることで総距離を短くできないか」を繰り返し試します。シンプルな仕組みながら、近傍法の解を大幅に改善できることが多いです。
配送最適化入門シリーズの記事一覧はこちら。
| 記事 | 内容 |
|---|---|
| ⓪ | 配送最適化とは？基礎概念 |
| ① | 近傍法の説明 |
| ②（本記事） | 2-optの説明 |
| ③ | 3-optの説明 |
| ④ | Lin-Kernighan法の説明 |
| ⑤ | 焼きなまし法（SA）の説明 |
| ⑥ | 遺伝的アルゴリズム（GA）の説明 |
| ⑦ | VRPとは？ |
| ⑧ | VRPをアルゴリズムで解く |
2-optとは？
2-optは 「2本の辺を削除し、別の形で再接続することでルートを短くする」 改善手法です。
直感的なイメージ
ルートの中で辺が「交差（クロス）」している箇所があると、必ず無駄が生じています。
2-optはこの交差を解消することで総距離を短くします。
アルゴリズムの手順
① ルート中の全ての辺の組み合わせ $(i, j)$ を試す
② 辺 $(i, i+1)$ と辺 $(j, j+1)$ を削除し、間の区間を反転して再接続する
③ 距離が改善されれば採用
④ 改善が見られなくなるまで①〜③を繰り返す（局所最適に収束）
数式による改善条件
辺 $(i, i+1)$ と $(j, j+1)$ を削除して再接続するとき、以下の条件で改善されます。
d(i, i+1) + d(j, j+1) > d(i, j) + d(i+1, j+1)
つまり「現在の2辺の合計」より「入れ替え後の2辺の合計」が短ければ採用します。
Python実装
import numpy as np
import matplotlib
import matplotlib.pyplot as plt
plt.rcParams['font.family'] = 'Yu Gothic'
def two_opt(route, dist):
"""
2-optによるルートの改善
route: 現在のルート（都市インデックスのリスト）
dist: 距離行列
戻り値: 改善後のルート
"""
n = len(route)
best_route = route[:]
improved = True
while improved:
improved = False
for i in range(1, n - 1):
for j in range(i + 1, n):
# 辺 (i-1, i) と (j, j+1) を入れ替えるコスト差を計算
a, b = best_route[i - 1], best_route[i]
c, d = best_route[j], best_route[(j + 1) % n]
# 現在の辺のコスト
current_cost = dist[a][b] + dist[c][d]
# 入れ替え後のコスト
new_cost = dist[a][c] + dist[b][d]
if new_cost < current_cost - 1e-10:
# i〜j 区間を反転
best_route[i:j + 1] = best_route[i:j + 1][::-1]
improved = True
return best_route
実行してみる
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):
dist[i][j] = np.linalg.norm(cities[i] - cities[j])
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):
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)
# 近傍法で初期解を作成
nn_route = nearest_neighbor(dist, start=7)
nn_dist = total_distance(nn_route, dist)
print(f'近傍法の総距離: {nn_dist:.1f}')
# 2-optで改善
opt_route = two_opt(nn_route, dist)
opt_dist = total_distance(opt_route, dist)
print(f'2-opt後の総距離: {opt_dist:.1f}')
print(f'改善率: {(nn_dist - opt_dist) / nn_dist * 100:.1f}%')
近傍法の総距離: 497.1
2-opt後の総距離: 459.4
改善率: 7.6%
7%以上の改善が得られました。
改善前後の可視化
def plot_route(cities, route, title='Route', filename=None):
dist = calc_distance(cities)
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, dist)
plt.title(f'{title} (総距離: {d:.1f})')
plt.grid(True, alpha=0.3)
plt.tight_layout()
if filename:
plt.savefig(filename, dpi=150)
plt.show()
plot_route(cities, nn_route, title='近傍法', filename='route_nn.png')
plot_route(cities, opt_route, title='2-opt後', filename='route_2opt.png')
2-optの計算量
2-optの1回のスキャンで調べる辺の組み合わせは $O(n^2)$ です。
改善が収束するまで複数回スキャンするため、全体の計算量は $O(n^2 \times k)$（$k$：改善回数）となります。
都市数が数百程度であれば実用的に動作しますが、数千以上になると工夫が必要になります。
2-opt の限界
2-optは「2辺の入れ替え」しか試さないため、2辺の交換では改善できない局所最適に陥ることがあります。
これを解消するのが3-optやLin-Kernighan法です。
まとめ
今回は2-optを説明しました。
- 2-opt：2本の辺を入れ替えて距離を改善する局所探索
- 辺が「交差」している箇所を見つけてほどくことで改善する
- 近傍法の解に対して大幅な改善（今回の例で約7%）が期待できる
- 計算量は $O(n^2)$ スキャンで都市数が数百程度まで実用的
次回はさらに改善幅を増やせる3-optを説明します。