Rで巡回セールスマン問題 With TSP(+RGoogleMap)

とある事情で巡回セールスマン問題（TSP）を試したいと思ってRのヒューリスティックス関数について調べていたら、そもそもTSPというRのパッケージが存在していたので、こいつを使って実際に巡回セールスマン問題を解いてみる。

さて、何をお題に解こうかと思っていたらとある人が、「ローソンのペットボトルのお茶についてくるアニメのおまけを手に入れようとしたら、2、3件の近くのローソンに行ってもそのお茶が見つからないやばい」といっていた。しかし、数を増やすと探索するのは面倒。
あれこれTSPで解けるんじゃね？と思って、みんなの貴重な時間を割かずに済むようにRでローソンの巡回セールスマン問題を解いてみる。
ちなみにTSPのインストールは普通にinstall.packagesでうまくいきました。

以下はこのローソン巡回問題を可視化を含めて解くための手順。

巡回対象となりうるローソンの住所リストを取得
Google Map APIでジオコーディングして、住所を位置情報に変換する。
TSPパッケージでTSPの解を求める。
地図上に経路を可視化する。

１に関しては

ローソン公式サイト：http://store.lawson.co.jp/
コンビニマップ：http://cvs-map.jp/

みたいなサイトから取得すればOK!
ちなみに私は妖精さんに取得して頂きました。妖精さんに感謝！！
ここで取得した住所を含む文字列型ベクトルをR上で保持しておく。

２はGoogle Maps APIのGeocoding APIを使用して、RCurl経由で、１の住所に紐づくGeocodingしたJSONデータをそのまま取得する。
ただし、１の住所情報をGoogleMapAPIに引き渡すときはURLエスケープをかませること。

library(RCurl)
GEOCODE_URL_P<-"http://maps.google.com/maps/api/geocode/json?address="
GEOCODE_URL_A<-"&sensor=false®ion=JP&language=ja"
url<-paste(GEOCODE_URL_P, curlEscape(住所), GEOCODE_URL_A, sep="")
tryCatch(jsondata<-RCurl::getURL(url), error=function(e){})

後はRJSONを使うなりなんなりして、位置情報である緯度と経度をJSONからぶっこ抜けばOK!
緯度と経度はデータフレームにして保持しておく。

３に関してはTSPパッケージのドキュメントに存在するコードを参考に以下の、関数を実装した。
これはTSPパッケージでデフォルトで用意されているTSP解法を全て試して最良解の順路を返してくれる。
こいつに２の緯度と経度からなるデータフレーム(df)を引き渡して実行すればOK!

#TSPパッケージで用意されているTSP解法を全て試して最適な解を見つけて、順路を返す。
getTSPOrder<-function(df){
methods <- c("nearest_insertion", "cheapest_insertion", "farthest_insertion", "arbitrary_insertion", "nn", "repetitive_nn", "2-opt")
tours <- lapply(methods, FUN = function(m) solve_TSP(TSP(dist(df)), method = m))
names(tours) <- methods
tour_lengths <- c(sapply(tours, FUN = attr, "tour_length"))
str(toursseq(tour_lengths)[tour_lengths==min(tour_lengths)])
as.integer(toursseq(tour_lengths)[tour_lengths==min(tour_lengths)])
}

これで指定した緯度経度の最短経路が求まる。
この関数は4の処理で呼び出すので、結果をどこかに保存する必要はない。

で、はまったのが「４．地図上に経路を可視化する。」である。
はまったのは以下の2点。

最初にはまったのは地図のplotである。
RMAP（地図の可視化を行うパッケージ）が私が現在使用しているR2.14.1で対応していなかった。
そこで対策として、２でお世話になったGoogle Maps APIを使用することにした。
幸いGoogle Maps APIを使用するためのパッケージRGoogleMapは2.14.1でも使用可能だったので、地図はGoogleから取得したものをそのまま使用することにする。

次にはまったのは地図上での最短経路の可視化である。
RGoogleMapパッケージにはRから取得したGoogle Static Mapsに線や点、多角形を上書きできる関数がある。
こいつで線を記述すると、線が2重に記述されてしまうバグ？のようなものに遭遇した。
このため経路を可視化できなかった。
そこで対策として、経路やローソンの位置情報の可視化もGoogle Maps APIを使用することにした。
ところがこいつを使用している時に経路が長すぎると、Google Maps APIの使用制限であるHTTPリクエストの文字数2048文字に引っかかってしまう場合があるので、注意が必要。

以下の関数は緯度lonと経度latを含むベクトルを引数で受けてって、orderの順番の経路をGoogle Maps APIの地図で可視化する関数である。

makeTSPmap<-function(lat, lon, order=seq(lat)){
#GoogleMap用のマーカーを作成する。
map_marker<-paste("&markers=color:blue|size:mid|", paste(apply(cbind(lat, lon), 1, function(x){paste(x,collapse=",")}), collapse="|"), sep="")
#GoogleMap用のズームを作成する。
map_zoom<-MaxZoom(range(lat), range(lon))
#GoogleMap用のセンターを作成する。
map_center<-c(mean(lat), mean(lon))
#GoogleMap用のパスを作成する。
map_path<-paste("&path=color:0x0000ff|weight:2|", paste(apply(cbind(lat[order], lon[order]), 1, function(x){paste(x,collapse=",")}), collapse="|"), sep="")
GetMap(center=map_center, maptype="roadmap", marker=map_marker, zoom=map_zoom, path=map_path)
}
#３の関数で最短経路問題を解いて、地図に可視化する。
makeTSPmap(lat=df$lat, lon=df$lon, order=getTSPOrder(df))

今回は2048文字制限にひっかからない範囲でローソン巡回問題を解くために、東京都台東区のローソンに範囲を絞ってTSPを解いて、地図上に可視化した。
結果は以下のとおりである。

これで勝つる！

今後の課題としては

距離の定義を店舗間のユークリッド距離で行っていること
RGoogleMapでの可視化にあたって線が2重に記述される問題

の2つがあげられる。

１に関しては、今回は緯度と経度からユークリッド距離を使ってＴＳＰを解いている。
しかし、実際には人が最短距離としてユークリッド距離でコンビニを巡回することはできない。
道路を歩くなり、チャリで行くことになるので、道路情報を反映した距離を用いたいということ。
これに関しては今後Google Maps APIの仕様をもう少し調べようと思います。

２に関してはRGoogleMapパッケージの仕様を調べてみようと思います。
もしくはRMapの使用法を調べてみてもよいのかも。

また、機会があればTokyo.RでTSPの解法についてもう少し調べて、TSPパッケージの仕様についてご説明できればなーと思います。
そういえば、某Rの大先生も同じ課題を抱えていらっしゃたような気もするので、機会があれば別の土地でやってみよう。

2月25日　追記：日本語が意味不明だったので、文章に修正を加えました。