100名城・続100名城スタンプラリーを効率的に回るルートを自動で計算してみたい（1/n）：前提条件の整理
とっっても久しぶりの投稿になってしまいました。
最近の興味として、なるべく負担少なく、効率的に100名城・続100名城をめぐりたいという課題認識があります。
今後、グラフ理論とか制約付き最適化とか地理データとか…、いろいろな知識を使ってこの課題を解いてみたいと思っています。
初回の記事（にしようと思っている本記事）では、ここで解く問題の条件や必要なデータなどを整理します。
なにをやろうとしているの？
トピックに関する前提・背景
お城巡りは子供のころからの趣味だったのですが、最近お城のスタンプラリーを始めました。
日本国内に大小含めて数多く存在するお城ですが、日本城郭協会はこの中から「日本100名城」「続日本100名城」を選定しています。
jokaku.jp
jokaku.jp
これらは質の高い文化遺産ということで、多くの人が訪れることを期待し、スタンプラリーが企画されています。
100名城・続100名城それぞれについてスタンプ帳が書籍として販売されており、特に100名城全登城認定者は約4,000名にのぼります。
（※ちなみに日本国内のお城の数は2万とか5万とか、定義によって諸説あるそうです。）
blog.kojodan.jp
今回の問題設定の背景
一方で、定職に就きフルタイムで働き始めたこともあり、まとまった時間がどんどん取りづらくなってきています。
そしてもちろん、お城を尋ねる際の金銭的負担もなるべく抑えたいところです。働き始めても節約は大事です。。。
こういった背景から、特に遠いところにあるお城に関しては1回の旅程でなるべく多くのお城を回って帰ってきたい！という需要があります。
とはいえ、着いたらスタンプだけ押して即帰れば多く回れるよね？という姿勢はいただけません。やっぱりせっかく行くならお城自体も精一杯楽しんで帰ってきたい！
スタンプラリーが目的化しては非常にもったいないので、各お城の滞在時間等も考慮したいところです。
ここで知りたいのは、じゃあどのお城とどのお城をまとめて行くのが効率的なのか？ということです。
100名城・続100名城のマップや経路検索アプリ、各お城の開城時間とにらめっこしながらルートを考えてもいいのですが、
個人的にはちょっと雑でもいいからルートプランを自動的にはじき出す方法ないかな？ということを思いついたのが、この記事の発端です。
なお、このアイデアを会社の自己紹介で共有したら興味を持ってもらったのが、この記事執筆のきっかけだったりします。お城好き、やっぱり多いですね！
問題の解き方を考えよう
ざっくりと何がしたいのかを説明したところで、実際にどうするかを考えていきたいと思います。
こういう方法探索のときは、大まかに「どういう問題を解きたいのか？」と「実際にどうやって解くか？」に分けて考えることにしています。
What to Answer：解きたい問題の定式化に関する案出し
では実際、どのような問題を解けばいいのでしょうか？
直観的に思いつくのは、制約付き最適化問題を解く、という問題設定の立て付けです。すなわち：
いくつかの条件を守ったうえで、○○を最大化したい OR △△を最小化したい
という形式にしたいところです。
例えば、以下のいくつかの例が考えられます：
例①：
全200城をすべて回るときの旅程数／旅行日数を最小化したい。ただし、以下の条件を守る：
- 1回あたりの旅程は1泊以下
- 各お城の滞在時間は1.5時間
- 各お城にはスタンプ押印可能時間に必ず到着する
など…
例②：
回れるお城の数を最大化したい。ただし、以下の条件を守る：
- 交通手段は18きっぷ1枚（5日間）＋路線バス＋徒歩のみとする
- 自宅出発は最寄り駅始発電車以降とする
- 日没後の新規登城は禁止！（1日中スタンプが押せるお城だとしても、真夜中に行ったりしない）
など…
例②だと、近郊のお城でも車でしか行けないようなお城は対象に入らないとか、興味深い結果が出そうです。
他にも、18きっぷはかならず毎旅程でもとをとるとか、18きっぷでの原価率を最大化するとかやっても面白そうですよね。
最適化は以上の定式化さえすれば、様々な数学的手法があるので何かしらの方法で解決できそう…。という見込みです。
このあたりの問題設定の仕方によって利用するMethodも違ってきそうです。今後、いろいろな問題について解いていきたいと思っているので、今回はあまり決め打ちしないことにします。
ただ、どんな問題設定でも共通して守りたい項目がいくつかあります！
①各お城の滞在時間を1～1.5時間以上確保する！
前述の通りですが、スタンプだけ大急ぎで押して帰る！というのは非常にもったいないです！やはりお城自体を楽しむ時間はある程度は必須です。
日本城郭協会もこんなメッセージを出しています。あたりまえでしょうが！と思ってしまいますが笑：
ところでスタンプラリーはスタンプを押すだけが目的ではなく、100名城を足で訪ねた記念としてスタンプがたまるものであって欲しい、と日本城郭協会は期待しています。急いで回って早くスタンプがたまれば良いという性格のものではありません。スタンプさえ押せれば良い、という姿勢は本末転倒です。
（出典：スタンプラリー | 公益財団法人日本城郭協会）
効率的に回りたい、でもお城は楽しんで帰りたい！これは間違いなく必須要件です。1~1.5時間で足りるかはいったん置いておくとして…ですが。
②各お城には、スタンプ押印可能時間内に到着する
とはいえ、スタンプを押して回るのも楽しみの一つです。目的の一つでもあります。
ですが、大半のお城はスタンプの押印可能時間が決まっています。例えば、全国のお城のうち僕が最も好きなお城（のうちの一つ）である二本松城については、
「二本松歴史資料館」（参考：二本松歴史資料館 | 二本松市観光連盟）内にスタンプが設置されていて、開館時間内（9時から17時）に訪れる必要があります*1。
もちろん、スタンプを時間外に押させてもらうようにごねるのも言語道断です。そんな人もいるんですね…。
近年、城郭管理者からスタンプラリー参加者のマナーに対する苦情が寄せられています。あくまでもこのスタンプラリーはそれぞれのお城の好意でスタンプを置いていただいていますので、特に以下のような行為は絶対におやめください。
※スタンプの設置時間・場所はそれぞれのお城のご都合にお任せしています。時間外に訪れてスタンプの押印を強要したり、有料区域でしか押印できないことへの苦情をお城にしないようにしてください。必ず訪問前に休館日・設置時間・設置場所を確認するようにしてください。
※お城によっては寺社などの宗教施設が城址であることがあります。このような場合はその宗教施設のご厚意でスタンプを設置していただいていますので、神聖な区域に対する敬意をもって見学をお願いします。
※スタンプ帳を直接お城や関係施設へ郵送してスタンプの押印を求める行為も厳禁です。このような場合は押印をお断りいただくように各施設にお願いしております。
（出典：スタンプラリー | 公益財団法人日本城郭協会）
How to Answer：必要な手法・データの検討
何を解くかを少し考えたところで、どういうセッティングでも使えそうな数理手法とか、それに必要なデータ構造とかを考えることにします。
先ほど考えた共通の制約条件を考慮すると、以下のようなデータや、それらをHandleする手法は必須になりそうです。
交通ネットワーク構造を示したデータ
公共交通機関・最寄り駅からお城までなど、お城にたどり着くまでの経路を示すネットワーク構造は情報として必須になりそうです。
交通網を表す際の数理的情報として真っ先に思いつくのは、グラフ形式でしょうか。
棒や折れ線・散布図など、一般的にいう「グラフ」ではなく、グラフ理論の対象を指します。こういう、点と点が線で結びついているアレです：
まだ僕もちゃんと勉強したことがないので、聞きかじった単語をまとめる感じですが、以下のことを考慮に入れる必要がありそうです。
- 無向グラフ：交通網はどっちからどっちに通ってもよいので、向きの情報はなくて大丈夫そうです。
- 多重グラフ：グラフの各辺は1回しか通れないというSettingが基本なので、「通っていった道を戻って帰ってくる」を許容するためには、同じ区間に2本の辺を描くことになります。この構造を多重グラフと呼ぶらしいです。
- 重みづけ：それぞれの辺には移動時間がどれだけかかるか、お城を示す点には到達することで加えるスコアを設定しておくことが考えられます。
- 閉路（サイクル）家の最寄り駅から出たら、回って同じ駅に帰ってくるのが1回の旅程になります。一筆書きができ、一周して同じ場所に戻ってくるようなグラフを閉路というそうです。条件を満たす（いくつかの）閉路を発見するのが今回の目標といえそうです。
※なお、以上の整理のために始めてグラフ理論の本を読みました。
仁平・西尾『グラフ理論 序説』は初心者でも雰囲気をつかめて、かつなんちゃって学術入門書によくある面白事例集にとどまらない感じが個人的に読みやすかったです。
グラフ理論で有名な問題と言えば、巡回セールスマン問題があります。
あれは全ての点を回って帰ってくる閉路のうち、一番コスト合計が少ないものを発見する問題ですが、今回の問題は一度にすべて回ってくる必要はない＋点に時間の制約条件が設定されている点が少々異なる気がします。*2
各お城のスタンプ押印可能時間
前述の条件②に対応するところです。この情報は網羅的に調査したうえで、ネットワーク構造の各お城ノードに対応させる必要がありそうです。
まとめ
いろいろ整理した結果、今回は
無向多重グラフ構造をとる交通網ネットワーク情報を用いて、制約条件を満たす最適経路を導く
ことが目標といえると思います。
問題設定・理論および要素技術について、全体的にまだ詰める要素が多いですが、初回としては問題を整理して今後のガイドとして残しておこうと思います。
挫折しないようにがんばります。
