巡回セールスマン問題を2-opt法で解く（Python）
概要
巡回セールスマン問題(TSP:Traveling Salesman Problem) は、都市の集合と各2都市間の移動コストが与えられたとき、 全ての都市をちょうど一度ずつ巡り出発地に戻る巡回路の総移動コストを最小化する、組み合わせ最適化問題です。 以前、大学の講義で自由に課題を設定してレポートを書く際に実装したのですが、割と苦労したので公開しておきます。
2-opt法
2-opt 法は逐次改善法の一種であり、逐次改善法とは、ある巡回路を基として、 それより更にコストの小さい巡回路を探す方法です。 2-opt 法のアルゴリズムは、次のように表されます。
- 入力した巡回路に対し、適当な二つの辺を選択し、それらを入れ替えた結果のコストを計算する。 そのコストが入れ替える前より小さくなれば、入れ替えを採用し、巡回路を改善する。
- 1.を、巡回路の改善ができなくなるまで繰り返す。
逐次改善法は既存の巡回路を改善していくことで最適解に近づけていくものなので、 事前に初期解として何らかの巡回路を与えておかなければなりません。 適当に巡回路を定めても良いのですが、ここでは構築法(与えられた都市間のコストから、巡回路を構築していく方法) であるNearest Neighbor法、Convex Hull Insertion法の2つを実装しました。
Nearest Neighbor法
Nearest Neighbor法のアルゴリズムは、次のように表されます。
- 適当な都市を選び、出発点とする。
- まだ訪れていない都市のうち、現在いる都市から最も近い都市を選び、その都市との経路を巡回路に加え、その都市に移動する。
- 2.を、まだ訪れていない都市がなくなるまで繰り返す。なくなったら、最後に訪れた都市と出発点とをつなぐ経路を巡回路に加えて終了する。
Convex Hull Insertion法
凸包を初期部分巡回路とし、それ以外の都市を最近挿入法により加えながら巡回路を構築する方法です。アルゴリズムは以下で表されます。
- 都市を頂点とする凸包の境界上の都市を初期巡回路とする。
- 巡回路上の連続した都市を
とし、巡回路以外の各都市
に対して、追加コスト
を計算し、この値を最小とする都市
を計算し、この値を最小とする都市
を巡回路 に追加する。
- 全ての都市を通過する巡回路ができるまで2.を繰り返す。
グラハムスキャン法
ややこしい話になりますが、CHI法で巡回路を構築する前に、さらに初期段階として 都市の点集合の凸包を求める必要があります。 凸包を求めるアルゴリズムには、分割統治法、逐次添加法などが存在しますが、 ここではグラハムスキャン法というアルゴリズムを採用します。
- 都市の集合のうち、y座標が最小のもの（複数ある場合は、そのうちx座標最小の もの）を基準点とし、基準点に対する角度の順に、残りの点に番号をつける。
- 番号順に点を見ていき、一つ前の点H、現在の点I、次点の角度Jの角度∠HIJ を 計算する。角度がマイナスになる場合、凸包にはならないため、点I を削除する。 そして、その次の点Kとの角度∠HJK を計算し、同様の操作を繰り返す。
- の操作を、全ての点との角度を計算するまで行う。
コード
長くなったので、GitHubに上げてあります。
「Nearest Neighbour法のみ」、「CHI 法のみ」、「Nearest Neighbour 法+2-opt 法」、「CHI 法+2-opt 法」の
いずれかについて計算し、matplotlabで結果を表示できるようにしてあります。
なおTSPの問題となるデータは、TSPLIBというサイトから頂いてきます（同サイトで最適解の確認もできます）。
参考文献
坂上知英, 吉澤慎, 太田義勝，大山口通夫：巡回セールスマン問題の近似アルゴリズムに
ついて. Research reports of the Faculty of Engineering, Mie University, 25, pp.81-96,(2000)
星野貴弘, 浜松芳夫:巡回セールスマン問題に対するヒューリスティック解法. 研究報告
高度交通システム(ITS), 2011(3), pp.1-4, 2011
関根渓:INTRODUCTION TO ALGORITHMS,http://www-ikn.ist.hokudai.ac.jp/ksekine/slides/convexhull.pdf
