JR東日本ポケモンスタンプラリー2018の全55駅を効率的に巡る経路を遺伝的アルゴリズムで考えてみました。
Rで実装しています。
プログラムはGitHubに置いていますので、自分で動かしてみたい方はお使いください。
https://github.com/mktkbt/pokemon-rally-2018
おススメのルート
巡回経路（ある駅から出発して、その駅に戻ってくる）を求めているので、途中駅からでも開始できるし、逆回りもできます。
駅を順番に直線で結ぶとこうなります。それなりに効率的なルートになっています。
進化の状況をアニメーションで見れるようにしています。
http://s3-ap-northeast-1.amazonaws.com/poke-rally/map.html
（javascriptの実行を許可して、ANIMATEボタンをクリックしてください）
結果はこちら。
| 駅 | 経路 | 時間(分) | 駅 |
|---|---|---|---|
| 東京 | 東京 (JR山手線) 神田 | 5 | 神田 |
| 神田 | 神田 (JR山手線) 有楽町 | 7.5 | 有楽町 |
| 有楽町 | 有楽町 (JR山手線) 浜松町 | 7.5 | 浜松町 |
| 浜松町 | 浜松町 (JR京浜東北線) 大井町 | 10.5 | 大井町 |
| 大井町 | 大井町 (JR京浜東北線) 蒲田 | 8 | 蒲田 |
| 蒲田 | 蒲田 (JR京浜東北線) 川崎 | 5.5 | 川崎 |
| 川崎 | 川崎 (JR東海道本線(東京～熱海)) 大船 | 26 | 大船 |
| 大船 | 大船 (JR横須賀線) 東戸塚 | 13 | 東戸塚 |
| 東戸塚 | 東戸塚 (JR横須賀線) 横浜 横浜 (JR根岸線) 石川町 |
30 | 石川町 |
| 石川町 | 石川町 (JR根岸線) 桜木町 | 13 | 桜木町 |
| 桜木町 | 桜木町 (JR根岸線) 横浜 | 9 | 横浜 |
| 横浜 | 横浜 (JR横須賀線) 武蔵小杉 | 13 | 武蔵小杉 |
| 武蔵小杉 | 武蔵小杉 (JR横須賀線) 品川 | 13 | 品川 |
| 品川 | 品川 (JR山手線２) 大崎 | 7.5 | 大崎 |
| 大崎 | 大崎 (JR湘南新宿ライン) 恵比寿 | 9 | 恵比寿 |
| 恵比寿 | 恵比寿 (JR山手線) 新宿 | 12.5 | 新宿 |
| 新宿 | 新宿 (JR中央線(快速)) 四ツ谷 | 10 | 四ツ谷 |
| 四ツ谷 | 四ツ谷 (JR中央・総武線) 市ケ谷 | 6 | 市ケ谷 |
| 市ケ谷 | 市ケ谷 (JR中央・総武線) 四ツ谷 四ツ谷 (JR中央線(快速)) 高円寺 |
26 | 高円寺 |
| 高円寺 | 高円寺 (JR中央・総武線) 荻窪 | 9 | 荻窪 |
| 荻窪 | 荻窪 (JR中央・総武線) 吉祥寺 | 9 | 吉祥寺 |
| 吉祥寺 | 吉祥寺 (JR中央線(快速)) 武蔵小金井 | 25 | 武蔵小金井 |
| 武蔵小金井 | 武蔵小金井 (JR中央線(快速)) 八王子 | 40 | 八王子 |
| 八王子 | 八王子 (JR中央線(快速)) 立川 | 20 | 立川 |
| 立川 | 立川 (JR中央線(快速)) 西国分寺 西国分寺 (JR武蔵野線) 武蔵浦和 |
48 | 武蔵浦和 |
| 武蔵浦和 | 武蔵浦和 (JR武蔵野線) 越谷レイクタウン | 25 | 越谷レイクタウン |
| 越谷レイクタウン | 越谷レイクタウン (JR武蔵野線) 新三郷 | 17 | 新三郷 |
| 新三郷 | 新三郷 (JR武蔵野線) 新松戸 新松戸 (JR常磐線(上野～取手)) 取手 取手 (JR常磐線(取手～いわき)) 牛久 |
68 | 牛久 |
| 牛久 | 牛久 (JR常磐線(取手～いわき)) 取手 | 25 | 取手 |
| 取手 | 取手 (JR常磐線(上野～取手)) 柏 | 17 | 柏 |
| 柏 | 柏 (JR常磐線(上野～取手)) 松戸 | 23 | 松戸 |
| 松戸 | 松戸 (JR常磐線(上野～取手)) 亀有 | 11 | 亀有 |
| 亀有 | 亀有 (JR常磐線(上野～取手)) 北千住 | 11 | 北千住 |
| 北千住 | 北千住 (JR常磐線(上野～取手)) 上野 | 17 | 上野 |
| 上野 | 上野 (宇都宮線) 蓮田 | 42 | 蓮田 |
| 蓮田 | 蓮田 (宇都宮線) 大宮 | 22 | 大宮 |
| 大宮 | 大宮 (JR高崎線) 上尾 | 20 | 上尾 |
| 上尾 | 上尾 (JR高崎線) 桶川 | 20 | 桶川 |
| 桶川 | 桶川 (JR高崎線) 大宮 大宮 (JR湘南新宿ライン) 浦和 |
39 | 浦和 |
| 浦和 | 浦和 (JR湘南新宿ライン) 赤羽 | 9 | 赤羽 |
| 赤羽 | 赤羽 (JR湘南新宿ライン) 池袋 | 9 | 池袋 |
| 池袋 | 池袋 (JR山手線) 高田馬場 | 7.5 | 高田馬場 |
| 高田馬場 | 高田馬場 (JR山手線) 大塚 | 10 | 大塚 |
| 大塚 | 大塚 (JR山手線) 巣鴨 | 5 | 巣鴨 |
| 巣鴨 | 巣鴨 (JR山手線) 田端 | 7.5 | 田端 |
| 田端 | 田端 (JR山手線) 日暮里 | 7.5 | 日暮里 |
| 日暮里 | 日暮里 (JR山手線) 秋葉原 | 12.5 | 秋葉原 |
| 秋葉原 | 秋葉原 (JR中央・総武線) 錦糸町 | 12 | 錦糸町 |
| 錦糸町 | 錦糸町 (JR総武本線) 船橋 | 12 | 船橋 |
| 船橋 | 船橋 (JR総武本線) 津田沼 | 6 | 津田沼 |
| 津田沼 | 津田沼 (JR総武本線) 千葉 | 9 | 千葉 |
| 千葉 | 千葉 (JR外房線) 蘇我 | 20 | 蘇我 |
| 蘇我 | 蘇我 (JR京葉線) 稲毛海岸 | 13 | 稲毛海岸 |
| 稲毛海岸 | 稲毛海岸 (JR京葉線) 新浦安 | 37 | 新浦安 |
| 新浦安 | 新浦安 (JR京葉線) 東京 | 33 | 東京 |
１日で巡れる？
移動だけで（スタンプを押すための時間を除いて）15～16時間はかかりそうです。
移動時間は一定の式で求めていますが、かなり大雑把です。
注意：
事前に6駅まわって全駅用のスタンプ帳をもらうのと、全駅制覇のあとで東京駅か池袋駅に行って景品をもらうので、実際は1日だけというわけにはいきません。また、いくつかの駅ではスタンプを押せる時間が限定されている（みどりの窓口に設置されている）ので要注意です。
2017年のスタンプラリー50駅を１日で廻った方がいらっしゃいますが、2018年は5駅増えて55駅になっているので、おそらく難易度が上がっています。
【実践 最短攻略】ポケモンスタンプラリー 2017JRに参加してきたよ！
今からでもまだ間に合う！「ポケモンスタンプラリー2017」を1日で制覇する方法
処理の大まかな流れとその説明
３つのプログラムに分けています。
① 駅間の移動時間を計算する
② 遺伝的アルゴリズムで解を求める
③ 求めた解（経路）を地図上に表示する
駅間の移動時間を計算する
路線情報を取得する
駅や路線の情報は駅データ.jpのサービス（API）を使わせていただきました。
駅データ.jpで取得できるのは、路線や駅の情報だけなので、駅間の移動時間は自分で求める必要があります。
乗り換えなしの移動時間の計算
まず、乗換がない場合の移動時間は以下の方法で求めます
乗車までの待ち時間 ＋ （移動中の駅間時間 × 駅数）
乗車までの待ち時間と移動の駅間時間は路線ごとに適当に決めています。
| 路線 | 乗車までの 待ち時間 |
移動の駅間時間 |
|---|---|---|
| 山手線 | 2.5分 | 2.5分 |
| 東海道線 | 5.0分 | 5.0分 |
| 京浜東北線 | 3.0分 | 2.5分 |
複数の経路がある場合は、時間の最も短いものを採用します。
例えば、東京から新橋まで移動する場合は
山手線だと 2.5分（待ち時間）＋ 2.5分（駅間時間）ｘ 2駅 ＝ 7.5分
東海道線だと 5.0分（待ち時間）＋ 5.0分（駅間時間）ｘ 1駅 ＝ 10.0分
京浜東北線だと 3.0分（待ち時間）＋ 2.5分（駅間時間）ｘ 2駅 ＝ 8.0分
となるので、山手線の7.5分を移動時間としています。
乗り換えありの移動時間の計算
乗換がある場合、乗換駅までの移動時間 ＋ 乗換駅からの移動時間 で求めます
乗換が２回以上の場合もあるので、次のように乗換回数を増やしながら移動時間を求めていきます。
① 乗換駅までの乗換なしの移動時間 ＋ 乗換駅からの乗換なしの移動時間 ← 乗換１回
② 乗換駅までの①で求めた移動時間 ＋ 乗換駅からの乗換なしの移動時間 ← 乗換２回
③ 乗換駅までの②で求めた移動時間 ＋ 乗換駅からの乗換なしの移動時間 ← 乗換３回
④ 以下繰り返し
始点・終点が同じ場合（乗換駅が違う場合）は、移動時間の最も短いものを採用します。
環状路線（山手線）の扱い
駅データ.jpで取得できる情報では、山手線は「大崎始点・品川終点の路線」という定義になっていて、データだけでは大崎と品川が隣り合った駅だということが分かりません。このままだと、大崎・品川間を通過する経路の移動時間が、遠回りの経路になってしまいます。
これを回避するために田端始点・駒込終点の「裏山手線」を定義して対応しています。
遺伝的アルゴリズムで解を求める
遺伝的アルゴリズムでの実行部分はライブラリを呼び出しているだけです。（あっさり）
200個体で約10000世代かけて求めています。突然変異はやや高めです。
局所最適に陥りやすいようで、実行するたびに違った結果（経路）になりますが、時間はほぼ16時間になります。
求めた解（経路）を地図上に表示する
計算結果や計算過程をJavaScriptでGoogleMapに反映するHTMLを書き出しています。
あと、この記事に掲載した経路表をMD形式で出力します。
最後に
私鉄や地下鉄を併用すれば、もう少し時間短縮できる可能性があります。そのうち試してみるかもしれません。
データ（路線データ、対象駅データ）を変えるだけで、様々なスタンプラリーに対応可能なので他のスタンプラリーへの適用も比較的容易そうです。
実装にかかった時間は、前処理（駅間の移動時間の計算）75%、遺伝的アルゴリズムの実行 5%、後処理（地図上への表示） 20% くらい。ほとんどが前処理ですね。遺伝的アルゴリズムの実行部分は単純な巡回セールスマン問題なので、前処理で駅間距離を求めておいてライブラリを呼び出すだけでした。
ちなみに、2013年に同じことを考えていた方がいらっしゃいました。
ポケモンスタンプラリーの最短ルートを模索してみた
その頃は24駅＋スタンプ9時半～16時限定だったのですね。