2-opt
組合せ最適化において、2-opt は巡回セールスマン問題を解く局所探索法の1つである。
2-optは、Croesによって1958年に初めて提案されたが[1]、基本的な動作は既にFloodによって提案されていた[2]。背景にある基本的なアイディアは、交わる経路はそうならないように順路を変更できるということである。完全な2-optは、交換可能なすべての組合せを比較する。この手法は、巡回セールスマン問題だけでなく、関連する多くの問題にも適用できる。例えば、vehicle routing problem(VRP)やその容量付き版などが挙げられるが、これらに適用するにはアルゴリズムを少し修正する必要がある。
擬似コード
[編集]図で表すと、交換は次のように行う。
- A B - - A - B -
× ==>
- C D - - C - D -
擬似コードでは、経路を更新するルーチンは次のようになる。
procedure 2optSwap(route, v1, v2) {
1. route[0]からroute[v1]までを順番にnew_routeに追加する。
2. new_route[v1+1]をroute[v2]とし、逆順にnew_routeに追加する。
3. route[v2+1]から末尾までを順番にnew_routeに追加する。
return new_route;
}
以下は、2optSwapの動作例である。
- 経路(変数 route): A → B → E → D → C → F → G → H → A
- v1=1, v2=4 (開始インデックスを0とする)
- ステップ毎のnew_routeの内容:
- (A → B)
- A → B → (C → D → E)
- A → B → C → D → E → (F → G → H → A)
2optSwapをサブモジュールとして、完全な2-optは次のように書ける。
repeat until 改善が見られない {
best_distance = calculateTotalDistance(existing_route)
start_again:
for (i = 0; i <= 交換可能なノード数 - 1; i++) {
for (j = i + 1; j <= 交換可能なノード数; j++) {
new_route = 2optSwap(existing_route, i, j)
new_distance = calculateTotalDistance(new_route)
if (new_distance < best_distance) {
existing_route = new_route
best_distance = new_distance
goto start_again
}
}
}
}
始点や終点にある特定のノードは、順番を逆にすると無効な経路になるため、交換の候補から外すべきである。例えば、Aに戻る経路を次のように表しているとする。
A → B → C → D → A
route[0]とroute[2]を交換すると、new_routeは次のようになり、正しい経路情報ではなくなる。
C → B → A → D → A
効率的な実装
[編集]新しい経路を構築しその距離を計算するのは、非常に高価な処理で、ふつうnを頂点数としてかかる。ただし、交換によって経路長が減少するかはで分かる。
lengthDelta = - dist(route[v1], route[v1+1]) - dist(route[v2], route[v2+1]) + dist(route[v1+1], route[v2+1]) + dist(route[v1], route[v2])
もしlengthDeltaが負であれば、交換後の新しい距離が短くなることを意味するので、そのときのみ2-optの交換を行うことで、計算コストを大幅に抑えられる。
関連項目
[編集]参考文献
[編集]- ^ G. A. Croes (1958), “A Method for Solving Traveling-Salesman Problems”, Operations Research 6 (6): 791-812, doi:10.1287/opre.6.6.791
- ^ Merrill M. Flood (1956), “The Traveling-Salesman Problem”, Operations Research 4 (1): 61-75, doi:10.1287/opre.4.1.61