前回のエントリーで、フランスの最も美しい村データベースサイトにて「データ分析もフル活用したおすすめルート作成シミュレーション機能」ができるといいなと思いつきで書いたのですが、意外と実現可能性が高いような気がしてきました。
先日、最近仕事でよく使っているRという統計解析ソフトを利用した最適化計算についていろいろ調べていたところ、偶然「巡回セールスマン問題」というものに遭遇。
「巡回セールスマン問題（Travelling Salesman Problem, TSP）」とはなにか、Wikipediaより抜粋しますと、
巡回セールスマン問題（じゅんかいセールスマンもんだい、英: traveling salesman problem、TSP）は、都市の集合と各2都市間の移動コスト（たとえば距離）が与えられたとき、全ての都市をちょうど一度ずつ巡り出発地に戻る巡回路の総移動コストが最小のものを求める（セールスマンが所定の複数の都市を1回だけ巡回する場合の最短経路を求める）組合せ最適化問題である。（出所：Wikipedia）
とのこと。たまたま読んでいたとあるRの解説書、最適化関連のセクションの例題としてこの巡回セールスマン問題のアルゴリズムが紹介されていたのです。
計算機科学、アルゴリズム科学の中ではかなり有名な問題のようです。恥ずかしながら私は全く知りませんでした。
そのときふとひらめたいのですが、これってもしかして美しい村巡りの最適ルート作成に使えるんじゃないか、と。
再びWikipediaより。
この問題は、計算複雑性理論においてNP困難と呼ばれる問題のクラスに属する。（出所：Wikipedia）
とのことらしいのですが、
NP困難な問題は、任意の大きさの任意の問題例に対しての多項式時間アルゴリズムが存在しないと考えられているのであって、巡回セールスマン問題の場合、約2000都市以内の比較的小さい問題例に対して、あるいは問題例によっては解が得られないことがあってもよいのであれば、（線形計画法と論理木を組み合わせた）分枝限定法や、（線形計画法と巡回群を組み合わせた）切除平面法により、パーソナルコンピュータでおよそ1日以内で厳密解を得られることが多い。（出所：Wikipedia）
ということでもあるようです。
確かに、この問題を解くためのRやPython、その他の言語でのライブラリー、サンプルコードがネット上でいくらでも見つけることが出来ました。
さらにこれって来週から行う「イタリアの最も美しい村巡り」にも応用ができるんじゃないか、うっかりひらめいてしまいました。
であれば早速実行。はじめにRを試すもネットで見つけたサンプルコードが動かなったので、Pythonに変更。こちらのsolverをDownloadして利用。
図形描写などしなければ、基本的には、“src/greedy_tsp.py”にある”solve_tsp_numpy”という関数のみでOK。必要な外部モジュールもnumpyだけでOK。
手元で用意するデータは、都市間距離行列のみ。（後述しますが僕はGoogle Direction APIを利用して移動時間行列を自作しました。）
とりあえず出来上がったのは、こちら。
ざっくりと作成レシピを書いておくと。
- イタリアの最も美しい村リスト、座標データを用意（サルディーニャ島除く南イタリア48箇所）
- Pythonを適当に書いて、GoogleのDirection APIより2つの村の移動距離、移動時間を取得（JSONファイル）
- 上記で取得した移動時間を並び替えて行列を作る(numPyを適宜利用)
- solve_tsp_numpyに上記行列を入れて、TSP solver実行
- 上記solverで求めた最適順リストに従って村リストを並び替えJSON形式でエクスポート（Pythonはここまで）
- 簡単なhtmlファイルを作成、上記JSONファイルを読み込み、Google Maps APIを利用、訪問対象の村を最適ルート順に番号をつけてマーカー表示
- 最適ルート順に村々を直線で結ぶ（Polylineを利用）
（余裕があったら次回にでも、もう少し丁寧に作成方法書きます。）
これは予想以上にいい！よく見ると、属人的な判断では思いつかないようなルートだったりします。
特に直線がクロスしている箇所、シチリア島における4番目から7番目あたり、あるいは東部かかとあたりの37番目から41番目あたりとか。確かにこの位置関係では、機械的でないと判断が難しいのもうなずけますね。
今回の旅行のスタート地点はこの地図上の「１」の村ではないのですが、途中の番号からはじめても現実的には問題はないでしょう。
イタリアの最も美しい村は230もあるし、今回まわる南イタリアには48箇所ありますから、できるだけ効率よく回るに越したことはないわけです。
改良点はまだまだたくさん（村間は直線でなく実際の経路にする、ウェブサーバー上でも計算できるように仕込むなど）ありますが、これだけでも今回の旅で大いに役立つに違いない！
それにしてもGoogle Map、便利すぎてすごい。
