北海道内15箇所にポケモンマンホールが設置されるので最適経路を計算してみた
この記事はFOSS4G Advent Calendar 2019の12月8日の記事です。 昨日の記事は、chomyさんのGDALでGCOM-Cの可視領域のデータからTrue Colorイメージを再構成してみたでした。
FOSS4G Advent Calendar、毎日楽しませて頂いております。 参加表明した時点ではMapboxについて何か書こうかなと思っていたんですが、やってみたいネタを思いついてしまったので路線変更し本記事を執筆するに至ります。ではどうぞ。
はじめに
11月末ごろに、北海道にポケモンマンホールが設置される旨、公式ウェブサイトや各種ニュースサイトで取り上げられました。
１５箇所がそれなりに均等に全道に散らばっており、コンプリートはなかなか大変そうです。私の地元もなんと設置対象となっており、ポケモン好きとして、そしてジオ道へ進む身として、またアドベントカレンダーの良いネタが見つかったという事で、道内全１５箇所を巡る最適経路を計算してみたい！と思いやってみました。
『ポケふた』を位置情報データにする
位置情報を取得
公式サイトで地図情報と座標が取得出来ます。
QGIS上で１５箇所をプロット
マウスでカチカチ…
やったぜ。
CSVファイルに座標を出力
フィールド計算機で、属性に座標（経度・緯度）を追加します。＄xで経度(lon)を、＄yで緯度(lat)を取得可能。
そしてCSVでエクスポート。
['士別市', '44.1759660664951', '142.392400060057'] ['比布町', '43.8750601338394', '142.471656275175'] ['足寄町', '43.2442234401681', '143.546750238874'] ['石狩市', '43.5859009826181', '141.423896468599'] ['恵庭市', '42.8971470864568', '141.585830729499'] ['洞爺湖町', '42.5661295066754', '140.819057243298'] ['森町', '42.1088651156221', '140.572905228496'] ['上ノ国町', '41.8084126507218', '140.095325019279'] ['天塩町', '44.8845377760538', '141.747994037888'] ['稚内市', '45.4170905393652', '141.676181866153'] ['豊富町', '45.1033949651183', '141.778599640962'] ['紋別市', '44.334669948041', '143.37218366193'] ['遠軽町', '44.0218720548609', '143.497163771181'] ['大空町', '43.9155408070508', '144.171387033476'] ['新得町', '43.0826784443182', '142.832912172283']
最適経路計算
計算手法
さてデータの下準備が完了し、ここからが本番です。がしかし、最適経路の計算手法などは全く知らないのでとりあえずGoogleってみました。こういう、多数の地点の巡回ルートの最適化は一般に、巡回セールスマン問題と呼ばれています。
（答えが載ってる…最高…）
という訳でこちらの記事を参考にさせて頂きました。 組合せ最適化 - 典型問題 - 巡回セールスマン問題 - Qiita
コード
import csv import numpy as np from scipy.spatial import distance from ortoolpy import tsp asahikawa_airport = [142.4541427, 43.6708414] shinchitose_airport = [141.6811815, 42.7876057] shinkansen_hokuto = [140.6486832, 41.9046279] start_point = shinkansen_hokuto nodes = [start_point] with open('./pokefuta_coordinates.csv') as f: reader = csv.reader(f) header = next(f) for row in reader: nodes.append([ row[2], row[1] ]) dist = distance.cdist(nodes, nodes) print(tsp(nodes, dist))
pokefuta_coordinates.csvの中身は先ほどのcsvファイルと同じです。 経度・緯度の配列をnodesとして、それぞれの距離を要素数x要素数の行列distをつくり、tsp(traveling salesman problem)に渡すと結果が出力されます。
(12.651143975005297, [0, 10, 9, 8, 3, 5, 7, 6, 4, 14, 2, 13, 12, 11, 1])
最初の値は移動コストです。２つ目の返り値の配列が、移動コストを最小化する場合に通るべき経路を示します。常に1番目のnode（[0]のこと）がスタート地点かつゴール地点に設定されます。先ほどのcsvファイルで言うと士別市がスタート地点となります。この経路を図示すると以下になります。
コード自体は問題なさそうですね、ちゃんと最短経路っぽくなっています。 道民はみんな自家用ヘリコプターで移動するので海上ルートでも問題ありません。まあ車での移動だったとしても、森町と上ノ国町は同時に回るのが効率良いので、今回の分析には影響はないものとします（距離の乖離は大きそうだけれど、巡回の順番には影響がないものとする）。 というのが士別市発ルートですが、皆様のご旅行のプランに合わせていくつかのパターンをご覧ください（記載されている総移動距離は直線距離の総和による概算です）。
旭川空港発ルート
総移動距離：1267km
北海道第２位の都市旭川市、ではなく隣の東神楽町にあり、悪天候をものともしない堅牢さにより驚異の就航率99.7%を誇る我らが旭川空港から、道内１５箇所のマンホール巡りしてみませんか？
新千歳空港発ルート
総移動距離：1237km
ハブ空港として北海道の玄関口でありながら、飛行機に乗らずとも様々なテナントで楽しめる我らが新千歳空港から、１２００ｋｍドライブでマンホール制覇だ！
新幹線北斗駅発ルート
総移動距離：1239km
ついに来たぞ新幹線、東京から４時間くらいで着くらしいのでとりあえず来てみませんか、マンホール巡りしませんか？
終わりに
複数プランを示したものの、結局ルートは環状になったため当然ですが、順番が多少異なるだけでほとんど違いがありませんでした…。今回の記事は思いつきで始めてみましたが、思ったより早く記事に出来ました（トータル４時間くらい）。位置情報データの表示や加工は仕事や趣味で色々やってきましたが、今回の最適化のような分析はあまり経験がなく、実際今回のコードも、便利なライブラリに助けられただけでその計算手法などは全くわからないままです。わからない事だらけですが、ひとまずはこの記事を読まれた方に楽しんで頂けたなら幸いです。
