この記事について
前回は2-optでルートを改善しました。今回はさらに一歩進んだ3-optを解説します。
3-optは「3本の辺を入れ替える」改善手法で、2-optで改善できない局所最適を脱出できることがあります。ただし、組み合わせが増える分、計算コストも上がります。
配送最適化入門シリーズの記事一覧はこちら。
| 記事 | 内容 |
|---|---|
| ⓪ | 配送最適化とは？基礎概念 |
| ① | 近傍法の説明 |
| ② | 2-optの説明 |
| ③（本記事） | 3-optの説明 |
| ④ | Lin-Kernighan法の説明 |
| ⑤ | 焼きなまし法（SA）の説明 |
| ⑥ | 遺伝的アルゴリズム（GA）の説明 |
| ⑦ | VRPとは？ |
| ⑧ | VRPをアルゴリズムで解く |
3-optとは？
3-optは 「3本の辺を削除し、残ったセグメントを再接続する」 改善手法です。
2-optとの違い
2-optでは2本の辺を選んで入れ替えるため、再接続のパターンは1通りしかありません（間のセグメントを反転するだけ）。
3-optでは3本の辺を選ぶため、残った3つのセグメントの再接続パターンが複数存在します。
3本の辺 $(e_1, e_2, e_3)$ を削除すると、ルートは3つのセグメント $(A, B, C)$ に分かれます。
これらを再接続するパターンは（元の接続を除いて）7通りあります。
再接続パターンを図にすると以下のようになります。
（きれいに作ったつもりですが、わかりづらくなってたら申し訳ないです。）
| パターン | 説明 |
|---|---|
| 2-opt(A,B) | $e_1, e_2$ の入れ替え（Bを反転） |
| 2-opt(B,C) | $e_2, e_3$ の入れ替え（Cを反転） |
| 2-opt(A,C) | $e_1, e_3$ の入れ替え（A,Bを反転） |
| 3-opt(順) | A→B→C（元と同じ向き） |
| 3-opt(逆B) | A→B反転→C |
| 3-opt(逆C) | A→B→C反転 |
| 3-opt(純) | A→C→B（セグメントの順序を変える） |
最後の「セグメントの順序を変える」パターンが2-optでは到達できないケースに対応しています。
Python実装
3-optの完全な実装は複雑なため、ここでは「or-optムーブ」（1都市または複数都市を別の位置に挿入する）と組み合わせたシンプルな版を示します。
import numpy as np
from itertools import combinations
def three_opt_segment(route, dist):
"""
3-opt（セグメント順序変更を含む簡略版）
route: 現在のルート
dist: 距離行列
"""
n = len(route)
best = route[:]
improved = True
while improved:
improved = False
for i in range(n - 2):
for j in range(i + 1, n - 1):
for k in range(j + 1, n):
# 3本の辺を特定
a, b = best[i], best[(i + 1) % n]
c, d = best[j], best[(j + 1) % n]
e, f = best[k], best[(k + 1) % n]
d0 = dist[a][b] + dist[c][d] + dist[e][f]
# 全パターンを試す
seg_A = best[i + 1: j + 1]
seg_B = best[j + 1: k + 1]
# パターン1: セグメントA, B を順序変更（A→C再接続→B）
new_route = best[:i + 1] + seg_B + seg_A + best[k + 1:]
new_dist = (dist[a][seg_B[0]] + dist[seg_B[-1]][seg_A[0]]
+ dist[seg_A[-1]][f])
if new_dist < d0 - 1e-10:
best = new_route
improved = True
# パターン2: Bを反転してセグメント順序変更
seg_B_rev = seg_B[::-1]
new_route = best[:i + 1] + seg_B_rev + seg_A + best[k + 1:]
new_dist = (dist[a][seg_B_rev[0]] + dist[seg_B_rev[-1]][seg_A[0]]
+ dist[seg_A[-1]][f])
if new_dist < d0 - 1e-10:
best = new_route
improved = True
return best
2-optと組み合わせる
実務では2-optで収束した後に3-optを適用するパターンが多いです。
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
def two_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):
a, b = best_route[i - 1], best_route[i]
c, d = best_route[j], best_route[(j + 1) % n]
if dist[a][c] + dist[b][d] < dist[a][b] + dist[c][d] - 1e-10:
best_route[i:j + 1] = best_route[i:j + 1][::-1]
improved = True
return best_route
cities = generate_cities(n=20, seed=42)
dist = calc_distance(cities)
# 近傍法 → 2-opt → 3-opt の順で改善
nn_route = nearest_neighbor(dist, start=7)
opt2_route = two_opt(nn_route, dist)
opt3_route = three_opt_segment(opt2_route, dist)
print(f'近傍法: {total_distance(nn_route, dist):.1f}')
print(f'2-opt後: {total_distance(opt2_route, dist):.1f}')
print(f'3-opt後: {total_distance(opt3_route, dist):.1f}')
近傍法: 497.1
2-opt後: 459.4
3-opt後: 386.6
計算量の比較
| 手法 | 1スキャンの計算量 | 特徴 |
|---|---|---|
| 2-opt | $O(n^2)$ | シンプル・高速 |
| 3-opt | $O(n^3)$ | 改善幅大きい・低速 |
3-optは2-optに比べて計算量が $n$ 倍増加します。都市数が100を超えてくると、3-optの完全実装は実用的でなくなってくることがあります。。。
（おまけ）実用的な工夫：Or-opt
3-optの代替として Or-opt がよく使われます。Or-optは「1〜3都市のサブシーケンスを別の位置に挿入する」操作で、3-optの一部のムーブを効率的に試すことができます。（雰囲気だけ）
def or_opt(route, dist, seg_len=1):
"""
Or-opt：seg_len個の都市を別の位置に挿入
seg_len: 移動するセグメントの長さ（1〜3）
"""
n = len(route)
best = route[:]
improved = True
while improved:
improved = False
for i in range(n):
# セグメント [i, i+seg_len) を取り出す
seg = [best[(i + k) % n] for k in range(seg_len)]
seg_prev = best[(i - 1) % n]
seg_next = best[(i + seg_len) % n]
# セグメントを取り除いたコスト削減
remove_gain = (dist[seg_prev][seg[0]] + dist[seg[-1]][seg_next]
- dist[seg_prev][seg_next])
# 別の位置に挿入するコスト
for j in range(n):
if j in range(i, i + seg_len):
continue
jn = (j + 1) % n
insert_cost = (dist[best[j]][seg[0]] + dist[seg[-1]][best[jn]]
- dist[best[j]][best[jn]])
if remove_gain - insert_cost > 1e-10:
# 挿入操作を実行
new_route = [c for c in best
if c not in seg]
idx = new_route.index(best[j])
for k, city in enumerate(seg):
new_route.insert(idx + 1 + k, city)
best = new_route
improved = True
break
return best
まとめ
今回は3-optを説明しました。
- 3-opt：3本の辺を入れ替えてルートを改善する局所探索
- 2-optで到達できない局所最適を脱出できるケースがある
- 計算量は $O(n^3)$ で、都市数が増えると重くなる
- 実用上は Or-opt（1〜3都市の移動）と組み合わせると効果的
次回はより高精度な局所探索であるLin-Kernighan法を説明します。
参考にした記事や本、論文等
- S. Lin and B. Kernighan, "An Effective Heuristic Algorithm for the Traveling-Salesman Problem," Operations Research, vol. 21, no. 2, pp. 498-516, 1973.
- G. Gutin and A. P. Punnen, eds., "The Traveling Salesman Problem and Its Variations," Springer, 2002.