この記事について
前回は3-optを説明しました。今回は局所探索の中でも特に高精度なLin-Kernighan法（LK法） を説明します。
LK法は「可変長の辺交換」を行うことで、2-optや3-optよりも高品質な解が得られることで知られています。少し複雑なアルゴリズムですが、直感的なイメージから理解していきましょう。
配送最適化入門シリーズの記事一覧はこちら。
| 記事 | 内容 |
|---|---|
| ⓪ | 配送最適化とは？基礎概念 |
| ① | 近傍法の説明 |
| ② | 2-optの説明 |
| ③ | 3-optの説明 |
| ④（本記事） | Lin-Kernighan法の説明 |
| ⑤ | 焼きなまし法（SA）の説明 |
| ⑥ | 遺伝的アルゴリズム（GA）の説明 |
| ⑦ | VRPとは？ |
| ⑧ | VRPをアルゴリズムで解く |
Lin-Kernighan法とは？
Lin-Kernighan法は1973年に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.
2-optは「2辺」、3-optは「3辺」と固定の辺数を交換するのに対して、LK法は交換する辺の数を動的に決めるという発想が核心です。
核心のアイデア
LK法の基本的な考え方は「連鎖的な辺の追加・削除」です。2-optが「2本の辺を入れ替える」のと同じ発想ですが、LK法では入れ替える辺の本数を状況に応じて動的に増やすところが違います。
「削除→追加」の連鎖のイメージ
ルート上の都市 $t_1$ を起点として、以下の操作を繰り返します。
| ステップ | 操作 | 意味 |
|---|---|---|
| ① | 辺 $e_1 = (t_1, t_2)$ を削除 | 距離 $|e_1|$ 分だけ「節約」 |
| ② | 辺 $x_1 = (t_2, t_3)$ を追加 | 距離 $|x_1|$ 分だけ「消費」 |
| ③ | 辺 $e_2 = (t_3, t_4)$ を削除 | さらに節約を積み上げる |
| ④ | 続けるか、$t_4 \to t_1$ でルートを閉じる | ここで辺交換を確定 |
ここで重要なのは**「節約 − 消費」の累計（ゲイン）が正を保てる限り、連鎖を続ける**という点です。ゲインが負になりそうな方向には進まないので、無駄な探索を大幅に刈り込めます。
ゲインの計算
各ステップでのゲイン $G_i$ は次のように定義されます。
G_i = G_{i-1} + \underbrace{|e_i|}_{\text{削除した辺}} - \underbrace{|x_i|}_{\text{追加した辺}}
- $G_i > 0$：この時点で閉じれば改善になる（採用候補）
- $G_i \leq 0$：ここで打ち切り（これ以上続けても回収できない）
最終的に「閉じる辺を追加したときの $G_i$ が最大」となるタイミングを採用します。
2-opt・3-optとの関係
| 手法 | 連鎖の長さ | 探索方法 |
|---|---|---|
| 2-opt | 常に 1（辺を 2 本交換） | 全組み合わせを試す |
| 3-opt | 常に 2（辺を 3 本交換） | 全組み合わせを試す |
| LK法 | 動的（ゲインが正の限り延長） | ゲインが正の方向だけを辿る |
2-opt・3-opt が「全通り試して一番いい交換を選ぶ」のに対し、LK法は ゲインが正の経路だけを辿ってどんどん深掘りするイメージです。「全通り試さなくても高精度な改善が見つかる」ところが最大の特徴かと思います。
Python実装（簡略版）
完全なLK法の実装は複雑なため、ここでは核心となる「連鎖的な辺交換」の考え方を示すシンプル版を実装します。
import numpy as np
def lk_move(route, dist, t1_idx):
"""
LK法の1ステップ：t1から始まる改善を探索
route: 現在のルート
dist: 距離行列
t1_idx: 起点都市のインデックス
"""
n = len(route)
t1 = route[t1_idx]
# t1に隣接する2辺を候補に（ルート上の前後）
for direction in [-1, 1]:
t2_idx = (t1_idx + direction) % n
t2 = route[t2_idx]
# 削除する辺 e1 = (t1, t2)
g1_base = dist[t1][t2]
# t2から到達できる候補都市 t3 を探索
for t3_idx in range(n):
t3 = route[t3_idx]
if t3 == t1 or t3 == t2:
continue
# 追加する辺 x1 = (t2, t3) のコスト
x1_cost = dist[t2][t3]
g1 = g1_base - x1_cost
# ゲインがマイナスなら打ち切り
if g1 <= 0:
continue
# t3 に隣接する辺 e2 = (t3, t4) を削除候補として
for direction2 in [-1, 1]:
t4_idx = (t3_idx + direction2) % n
t4 = route[t4_idx]
if t4 == t1 or t4 == t2:
continue
# 閉じる辺 (t4, t1) を追加したときの総ゲイン
close_cost = dist[t4][t1]
g2 = g1 + dist[t3][t4] - close_cost
if g2 > 1e-10:
# 改善が見つかったので2-optムーブとして適用
i = min(t1_idx, t3_idx)
j = max(t1_idx, t3_idx)
new_route = route[:i + 1] + route[i + 1:j + 1][::-1] + route[j + 1:]
return new_route, g2
return None, 0
def lin_kernighan(route, dist, max_iter=1000):
"""
Lin-Kernighan法（簡略版）
"""
n = len(route)
best = route[:]
best_dist = sum(dist[best[i]][best[(i + 1) % n]] for i in range(n))
for _ in range(max_iter):
improved = False
for t1_idx in range(n):
new_route, gain = lk_move(best, dist, t1_idx)
if new_route is not None and gain > 1e-10:
best = new_route
best_dist -= gain
improved = True
break
if not improved:
break
return best
実行してみる
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)
nn_route = nearest_neighbor(dist, start=7)
opt2_route = two_opt(nn_route, dist)
lk_route = lin_kernighan(opt2_route, dist)
print(f'近傍法: {total_distance(nn_route, dist):.1f}')
print(f'2-opt後: {total_distance(opt2_route, dist):.1f}')
print(f'LK法後: {total_distance(lk_route, dist):.1f}')
実用上のLK法：LKH
実際の研究・実務では Keld Helsgott による LKH（Lin-Kernighan-Helsgott） というLK法の改良版がデファクトスタンダードとして広く使われています。
LKHでは以下のような工夫が加えられています。
- 候補辺リスト：全辺を試すのでなく、近くの辺だけを候補に絞ることで高速化
- バックトラッキング：ゲインが小さくなっても、より深い改善を探索する
- 5-opt以上のムーブ：より長い連鎖を試すことで高精度化
LKHはC言語で実装されており、公開されています。Pythonから呼び出すラッパーライブラリも存在します。
# pip install lkh でインストール可能（LKHバイナリが必要）
import lkh
# 問題をTSPLIB形式で渡す
# solver = lkh.solve('problem.tsp')
手法の比較まとめ
| 手法 | 交換する辺の数 | 計算量（1スキャン） | 解の質 |
|---|---|---|---|
| 2-opt | 2 | $O(n^2)$ | 普通 |
| 3-opt | 3 | $O(n^3)$ | やや高い |
| LK法 | 可変（2〜k） | $O(n^2)$ 〜 | 高い |
| LKH | 可変+工夫 | 実用的 | 非常に高い |
まとめ
今回はLin-Kernighan法を説明しました。
- LK法：連鎖的な辺の追加・削除を動的な長さで行う高精度局所探索
- 2-opt・3-optの一般化として位置付けられる
- ゲイン（削除コスト - 追加コスト）が累積してプラスになる限り探索を続ける
- 実用上は改良版の LKH が広く使われている
次回は局所最適から「確率的に脱出する」焼きなまし法（SA） を説明します。
参考にした記事や本、論文等
- S. Lin and B. Kernighan, "An Effective Heuristic Algorithm for the Traveling-Salesman Problem," Operations Research, vol. 21, no. 2, pp. 498-516, 1973.
- K. Helsgott, "An Effective Implementation of the Lin-Kernighan Traveling Salesman Heuristic," European Journal of Operational Research, vol. 126, pp. 106-130, 2000.