factorioはまだロケットが打ち上がっていませんが、一旦飽きが来ました（苦笑） コロナ騒ぎで再注目を浴びたPlague Inc.というゲームもやってみました。じっくり系のゲームではなく、テーブルゲームのようなゲームサイクルの感覚でした。
ちょっと前に教えてもらった、STATIONflowというゲームも気になっています。地下鉄の駅を作り、発生する乗客の流れを満足させていくゲームのようです。
各エージェントが視野を持っていて、案内サインを見つけてそれぞれ行動を決定するという、なかなか凝った作りになっています。
続きの話はゲームと関係なくなってくるので、暇で暇で仕方がなくパソコンを閉じても他にやることが本当に無い方だけお読み下さい。
交通流ネットワークの2つの切り口
交通流ネットワークの見方には、大きく2つのアプローチがあります。 ひとつはネットワークを「静的」なものとして捉え、一定の交通フローが定常的に存在する（または、1回きりの流れが発生する）ような状態を考える切り口。もう一つは、時々刻々と流れが変化していく「動的」なものとして捉える切り口です。
「静的」なモデルでは渋滞の再現が難しいなど解析できることに限りがあるため、近年では「動的」な切り口での話が多いと思います。STATIONflowもリアルタイムにエージェントがその時の周囲の状態に合わせて行動するというものなので、「動的」な交通流シミュレーションになっています。
ところが静的モデルも結構面白い話題があるので、自分の勉強がてら紹介したいと思います。前から興味があったのでいい機会ですｗ
静的モデルの基本
こういう系で最も分かりやすい基本的なものは、「最大流問題」ではないでしょうか。
あなた＝奉行は、江戸から上田にできるだけたくさんの物資を運ばなくてはなりません。各街道（隣接した2地点間）の人足には限りがあるので中山道だけではなく別の裏街道を使ったルートも検討することになっていますが、物資を溢れさせずに運びきれる量はいくらで、どの道にどれだけ通すのがよいでしょうか。
グラフ理論の言葉では、各地点を頂点（ノード）、街道を枝（エッジ）といいます。そして江戸-熊谷-高崎-軽井沢-小諸-上田 が中山道のルートですね。このような一連の経路のことをパスといいます。
図には書いていませんが、各枝には、人足に応じて運べる物資の上限が決まっているものとします。
本筋とは逸れますが草津を通って草軽交通のルートで軽井沢に出るルートがあったり、菅平のほうを回って直接上田に出るルートもあるのがマニアックですねｗ 果たしてそのルートを使ってどれだけ輸送量を増やせるのやら（笑）
交通流ネットワークの利用者均衡条件
もう少し交通流っぽい状況を考えてみましょう。交通流の場合は、シンプルな問題と違って、
- ネットワーク内にいろいろな種類のODペア（起終点=Origin→Destinationの組み合わせのこと）の流れが発生する
- 流量が先に決まっている
- 混雑すると余計に時間（≒コスト）がかかる
- 多少遠回りでも空いている道なら、早く着くので通る人が現れる
そこで、 誰もが「比べたら一番早く着く経路」を選ぶ ときに全体としてどのような流れが出来上がるか、を考えます。 このとき、例えば江戸-上田間で、中山道経由と川越街道経由の流れができたとして、「どちらの経路も結局所要時間は同じ」で「他の経路の所要時間よりも短いか、せいぜい等しい」ということが結果的に成り立ちます。なぜなら、仮にどちらかのルートのほうが早かったとしたら、より時間の掛かるルートから人が流れてきて混雑度が増し、２つのルートの所要時間が等しくなるように均衡するからです。
この均衡状態が成り立つことをはWardropの第１原則（利用者均衡条件）といいます。
新しい道ができたのに遅くなる？
直感的には納得しづらいですが、Wardropの第１原則に基づいて調べると、「道を増やすと全体の所要時間の合計が悪化する」事態が起きることがあります。この現象は「Braessのパラドクス」と名前までついています。調べるとWikipediaにも記事がありますが、平易なものでは「高校数学の美しい物語」が分かりやすいです。
極端な例ではありますが、Wikipediaによると、「うまくない道路」を閉鎖して交通を改善した例があるそうです。
交通流ネットワークのシステム最適化
Braessのパラドクスから、利用者それぞれが自分のことだけを考えて通る道を選んでいては、利用者一人ひとりも損をするようなケースがあることが分かります。逆に言えば、社会全体として所要時間を最小化するには、別の通り方（通し方）があるということです。
このとき、先ほどと同様に、仮に中山道経由と川越街道経由の流れが決まったとして、「どちらの経路の限界所要時間も同じ」で、「それ以外の使われていない経路の限界所要時間よりも短いかせいぜい等しい」という均衡条件が成り立ちます。こちらはWardropの第２原則と呼ばれます。限界所要時間って何よ？というと、「流量を１増やしたときに余分に増える所要時間」のことです。
仮に、限界所要時間がアンバランスな状態があったとしたら、お上の目線で考えて、「限界所要時間の大きい経路」の流量を減らして「限界所要時間の少ない経路」に振り替えれば、全体の所要時間合計を短縮できてしまいます。「全体の所要時間が最小」ということは、振り替えて所要時間合計を短縮できるような経路がないということなので、先ほどの均衡条件が成り立っていることが言えます。
（ここでいう限界というのは、経済学方面で、英語のmarginalに充てられている訳語です。）
システム最適フローを求めることはちょうど、リンクコスト＝各枝の交通量に対して全体に発生している費用が下に凸の多品種最小費用流問題を解くことになります。（つまり、増えれば増えるほど混雑に対応する余分なコストがかかる状態を表します。）（よね？ちょっと自信がない…） ふつうの最小費用流問題問題に比べると解くのに手間がかかります。
静的な解析の限界
こんどはmarginalの意味ではなく、limitationsですかね。
- Wardropの第２原則（全体最適化）は、理論的に考えることはできるものの、実現についてハードルが高い。
- 第１原則も、各交通利用者がネットワーク上の交通量や混み具合について完全に知っていることを仮定しており、この仮定は現実に成り立っているとは言い難い。 （最近は高性能のカーナビが、リアルタイムの渋滞情報に基づいて経路を計算してくれますが…。）
- 現実には、ある程度以上の交通需要がドバっと発生すると、詰まってしまって動かなくなり、渋滞が他の道に伝播する現象が起きるが、再現できていない
などの限界があります。
