祇園祭を最速で巡ろう

# はじめに

日本三大祭りの一つである「祇園祭」の季節が今年もやってきました。祇園祭は京都の八坂神社の例祭で、死者の霊魂が厄災をもたらさないように都の外へ送るための祭りです。その歴史は長く平安時代に創始された祭りです。

祇園祭の目玉の一つに、山や鉾と言われる大きな山車が京都の中心部を巡る「山鉾巡行」があり、山鉾を見るために毎年多くの人が集まるイベントです。山鉾巡行は17日と24日の2回で行われ、それぞれ「前祭(さきまつり)」と「後祭(あとまつり)」と呼ばれています。前祭では23基、後祭では11基の山鉾が巡行します。

しかし、山鉾が見られるのは山鉾巡行の時だけでなく、その前3日間の宵山と言われる期間にも、各町内で見ることができます。この期間中は、それぞれの山鉾にゆかりのお守りや手ぬぐいを買えたり、山鉾に登ることができます。また、それぞれの山鉾で、御朱印を集めるという楽しみ方もあります。

山鉾は、下の地図のように京都の四条烏丸を中心にそれぞれの町に点在していて、前祭の宵山の夕刻には周辺が歩行者天国となり、歩いて巡ることができます。山鉾同士はそれなりに近い距離にありますが、全てを歩いて巡るとある程度時間がかかります。

そこで、この記事では、御朱印を全て制覇したい人やできるだけ山鉾を時間いっぱいみたい人、蒸し暑い夏の京都をあまり歩きたくない人に向けて、できるだけ効率よく山鉾を巡る方法を調べてみようと思います。

![imgae_map.gif](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2748627/a0aa454d-791b-e49e-8369-98d5db61c999.gif)
[祇園祭 山鉾マップ](http://www.gionmatsuri.or.jp/yamahoko/map.html)より


# データ

山鉾は各町内が出していて、毎年決まった場所で見ることができます。それぞれの場所は簡単に調べることができるので、ぜひググってみてください。今回は、それぞれの山鉾の座標データがほしいため、祇園祭山鉾連合会のサイトにある[こちら](http://www.gionmatsuri.or.jp/yamahoko/map.html)の地図を使います。ピンの位置の座標をCSVとして出力できるので、そちらを加工して使いたいと思います。

需要があるか分かりませんが、おそらく誰も作っていないデータなので、一応載せておきます。

<details><summary>山鉾の座標データセット</summary>
綾傘鉾までの23基が前祭、北観音山以降の11基が後祭になります。

```text:yamaboko.txt
長刀鉾 35.003698 135.760975
函谷鉾 35.003706 135.759001
菊水鉾 35.003979 135.758164
月鉾 35.003627 135.757145
鶏鉾 35.002661 135.758153
放下鉾 35.003979 135.756705
岩戸山 35.000428 135.756758
船鉾 35.001404 135.756758
山伏山 35.005824 135.75811
孟宗山 35.004102 135.759623
太子山 35.001123 135.753733
郭巨山 35.003698 135.755943
保昌山 34.999857 135.761189
油天神山 35.001509 135.753701
四条傘鉾 35.003698 135.754302
蟷螂山 35.003909 135.755128
伯牙山 35.002441 135.756007
木賊山 35.001246 135.754141
霰天神山 35.004893 135.75766
白楽天山 35.001378 135.758175
芦刈山 35.002432 135.754763
占出山 35.004928 135.758861
綾傘鉾 35.002441 135.757627
北観音山 35.006571 135.756705
南観音山 35.005411 135.756694
橋弁慶山 35.006106 135.758883
役行者山 35.009489 135.7581
鯉山 35.00658 135.758142
八幡山 35.007547 135.756716
鈴鹿山 35.009594 135.759580
黒主山 35.00774 135.758153
浄妙山 35.007301 135.759119
大船鉾 35.003023 135.756656
鷹山 35.0084912 135.7572921
```

</details>

# 手法（後祭編）

本記事の目的は、すべての山鉾を最速で巡る方法を調べることです。祭り期間中は、場所によって大きく混雑具合が変わりますが、今回はできる限り歩く時間(距離)を短くなるような巡り方を考えていきます。そのため、全ての鉾をどのような順序で見ていくかが重要になってきます。

これを決める問題として、「巡回セールスマン問題」という有名な問題があります。この名前は、セールスマンがどの順序で家を回るのがよいかを決める問題に由来していて、現代では配送順序を最適化する問題などに応用されています。非常に有名で昔から検討されている問題であるため、厳密解や近似解を求める方法が多くあります。

ここでは、基数が少ない後祭について「bitDP」という厳密解を求める手法を使って計算します。全ての順序を計算するためには、$11!$回の計算が必要そうに思われますが、bitDPは同じ最適解を$2^{11} \times 11^2$回の計算で求めることができ、コンピューターであれば現実的な時間で計算できます。

この手法を用いて、現実に即した3つのシチュエーションについて、最短距離で巡ることができる順序を求めていこうと思います。

1. すべての山鉾1回ずつ巡る
2. 地下鉄四条駅から出発して、全ての山鉾を巡って四条駅に戻ってくる
3. 地下鉄烏丸御池駅から出発して、全ての山鉾を巡って烏丸御池駅に戻ってくる

1番は、自転車や市営バスで適当に移動できるような、京都市の人を考えた場合です。2･3番は、観光客を意識した場合で、2番は京都駅や阪急線から来る人、3番は河原町など東西線などを利用して来る人を考えています。

# 実装

巡回セールスマン問題を解くには、山鉾間や山鉾と駅間の徒歩の時間が必要になります。今回はOpenrouteserviceのAPIを使って、座標から所要時間を取得します。このAPIには、`distance_matrix`というものがあり、複数の座標を送ると、それぞれの2点間の所要時間を行列として返してくれます。徒歩の速度は時速5kmと一定されているようで、単純に道のりを速度で割った値が返ってきているようです。

bitDPの実装については、以下の記事が参考になると思います。ここでの問題では、最短時間だけでなく、その順序も知りたいので、そちらも合わせて計算できるように修正しています。

* [ビットDP(bit DP)の考え方 ~集合に対する動的計画法~](https://algo-logic.info/bit-dp/)
* [PythonでbitDPを使い巡回セールスマン問題を解く](https://qiita.com/Ll_e_ki/items/fa475f5bb224ada9be97)

<details><summary>コード(準備中)</summary>
</details>

# 結果（後祭編）

地図のうち前半ルートは青色、後半ルートは赤色で示しています。無向グラフを仮定しているので、巡る向きに違いはなく、1番からスタートしても、最後の番号からスタートしても所要時間は変わりません。

## 1. すべての山鉾1回ずつ巡る

```text:result1.txt
1.鈴鹿山  -> 2.役行者山  -> 3.鷹山  -> 4.黒主山  -> 5.浄妙山  -> 6.橋弁慶山 
-> 7.鯉山  -> 8.八幡山  -> 9.北観音山  -> 10.南観音山  -> 11.大船鉾 
```

![atomatsuri1.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2748627/8630cf24-5860-0b9a-6b52-b4c4bc0cb76f.png)
青色は1~6番のルート、赤色は6~11番のルートを示しています。巡る向きに違いはないので、11番から見ていっても同じ距離になります。

所要時間は1287.64秒で、合計距離は1.78kmでした。経路はおおよそ北から順に見ていく形で、特に密集している六角通りと蛸薬師通りの間を一筆書きの要領で順序良く回っているように見えます。また、巡航で最後尾の大船鉾が一番最後になりました。

## 2. 地下鉄四条駅から出発して、全ての山鉾を巡って四条駅に戻ってくる

```text:result2.txt
1.四条駅  -> 2.橋弁慶山  -> 3.鯉山  -> 4.黒主山  -> 
5.浄妙山  -> 6.鈴鹿山  -> 7.役行者山  -> 8.鷹山  ->
9.八幡山  -> 10.北観音山  -> 11.南観音山  -> 12.大船鉾  -> 13.四条駅 
```

![atomatsuri2.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2748627/55565f2c-a344-34cb-d22a-b8fcb6b84138.png)

所要時間は1894.85秒で、合計距離は2.63kmでした。烏丸通と新町通を中心に1周するような順序になっています。かなりきれいな一筆書きルートになっていて、実際同じような順路を取る人は多いと思います。

## 3. 地下鉄烏丸御池駅から出発して、全ての山鉾を巡って烏丸御池駅に戻ってくる

```text:result3.txt
1.烏丸御池駅  -> 2.役行者山  -> 3.鷹山  -> 4.八幡山  -> 
5.北観音山  -> 6.南観音山  -> 7.大船鉾  -> 8.橋弁慶山  -> 
9.鯉山  -> 10.黒主山  -> 11.浄妙山  -> 12.鈴鹿山  -> 13.烏丸御池駅  
```

![atomatsuri3.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2748627/25d6f4e9-f9dc-cd90-0726-a19aabe80216.png)

所要時間は1826.89秒で、合計距離は2.54kmでした。こちらは烏丸通と室町通を使ってに回る順序になっています。こちらもきれいな1周ルートに見えます。烏丸駅はもっと南にも出口があるので、地上を歩く時間はさらに短縮できそうな気もします。また、四条駅ルートより少し短くなるのも意外でした。

# 手法（前祭編）

前祭でも同様のルートを調べていきましょう。しかし、前祭では山鉾が23基と多く、bitDPでは現実的な時間で計算するのが難しくなってきます。Google Colaboratoryで同じコードを実行すると、配列を生成する段階でコードが止まってしまうので、やはり同じ手法で実行するのは難しそうです。

そこで、「PuLP」というpythonのライブラリを用いて計算しようと思います。PuLPは、pythonで線形最適化問題を解いてくれるライブラリです。「線形」とついているのは、特に一次関数で表現される制約条件のもとでの最適化を行ってくれるというもので、非常に高速に解を計算してくれます。

巡回セールスマン問題を一次関数のみの問題として表現して、線形計画問題として解く方法は、昔から多く研究されています。

定式化やPuLPによるコードは以下の記事を参考にしてください。

* [巡回セールスマン問題から始まる数理最適化](https://qiita.com/panchovie/items/6509fb54e3d53f4766aa)
* [PuLP による数理最適化超入門 巡回セールスマン問題](http://www.nct9.ne.jp/m_hiroi/light/pulp04.html)

前祭でも3つのシチュエーションについて計算しようと思います。

# 結果（前祭編）

地図のうち前半ルートは青色、後半ルートは赤色で示しています。巡る向きに違いはないので、1番からスタートしても、最後の番号からスタートしても所要時間は変わりません。

## 1. すべての山鉾1回ずつ巡る

```text:result4.txt
1.岩戸山 -> 2.船鉾 -> 3.白楽天山 -> 4.鶏鉾 -> 5.綾傘鉾 -> 
6.伯牙山 -> 7.芦刈山 -> 8.木賊山 -> 9.太子山 -> 10.油天神山 -> 
11.四条傘鉾 -> 12.蟷螂山 -> 13.郭巨山 -> 14.月鉾 -> 15.放下鉾 -> 
16.霰天神山 -> 17.占出山 -> 18.山伏山 -> 19.菊水鉾 -> 
20.函谷鉾 -> 21.孟宗山 -> 22.長刀鉾 -> 23.保昌山 -> 
```

![atomatsuri4.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2748627/c5da39ed-2ff4-2178-ff41-fbe9ed3e15d2.png)

所要時間は2373.0秒(~40分)で、合計距離は約3.3kmになります。南西から時計回りに回るようなルートとなっています。保昌山だけは距離があるので、やはり最初か最後になるルートが効率がよいようです。また、スタートとゴールを適切に選ばないと、50分を超える場合もあります。

## 2. 地下鉄四条駅から出発して、全ての山鉾を巡って四条駅に戻ってくる

```text:result5.txt
1.四条駅 -> 2.長刀鉾 -> 3.孟宗山 -> 4.函谷鉾 -> 5.菊水鉾 -> 
6.山伏山 -> 7.占出山 -> 8.霰天神山 -> 9.放下鉾 -> 10.月鉾 -> 
11.郭巨山 -> 12.蟷螂山 -> 13.四条傘鉾 -> 14.油天神山 -> 15.太子山 -> 
16.木賊山 -> 17.芦刈山 -> 18.伯牙山 -> 19.綾傘鉾 -> 20.鶏鉾 -> 
21.白楽天山  -> 22.船鉾  -> 23.岩戸山  -> 24.保昌山  -> 25.四条駅
```

![atomatsuri5.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2748627/d55bd56e-de2a-488d-db5c-38e8570b8757.png)

所要時間は2888.8秒(~48分)で、合計距離は約4kmになります。前祭でもきれいな1周のルートが出たので感動しました。前祭は固まった配置ですが、それでも1時間近くかかるそうです。

## 3. 地下鉄烏丸御池駅から出発して、全ての山鉾を巡って烏丸御池駅に戻ってくる

```text:result5.txt
1.烏丸御池駅 -> 2.山伏山 -> 3.菊水鉾 -> 4.函谷鉾 -> 5.孟宗山 -> 
6.長刀鉾 -> 7.保昌山 -> 8.岩戸山 -> 9.船鉾 -> 10.白楽天山 -> 
11.鶏鉾 -> 12.綾傘鉾 -> 13.伯牙山 -> 14.芦刈山 -> 15.木賊山 -> 
16.太子山 -> 17.油天神山 -> 18.四条傘鉾 -> 19.蟷螂山 -> 20.郭巨山 -> 
21.月鉾 -> 22.放下鉾 -> 23.霰天神山 -> 24.占出山 -> 25.烏丸御池駅 
```

![atomatsuri6.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2748627/da66b53e-d38f-be4b-47df-42de67b69819.png)

所要時間は3590.4秒(~60分)で、合計距離は約5kmになります。ルートのベースは他の2つシチュエーションと同じ感じで、北側の烏丸御池駅にうまくつながるそうに並べてあります。烏丸御池駅が遠い分所要時間がかかっています。

# まとめ

全山鉾を巡るための最短時間は、前祭で40分、後祭りで21分になりました。実は、軽い長距離走程度の距離があることが分かりました。祇園祭全山鉾RTAに挑戦する方は是非参考にしてください。大変混雑すると思うので、熱中症などには気をつけて、祇園祭を楽しんでもらったらよいと思います。

ただ、個人的には、提灯が灯る山鉾を眺めたり、四条通に響く祇園囃子を聞いたりなど、夏の京都の独特の雰囲気をゆっくり楽しむのがおすすめです。