より広い道路の建設は、交通状況を悪化させる可能性があります。 通常、この逆直感的で非生産的な結果は次のように説明されます：道路が多いほど、彼らはより大きなショッピングセンターを引き付け、それはより多くの車を引き付けます。 しかし、これはすべてではありません。 1960年代、 ディートリッヒブレイズは、車の数が一定であっても、新しい接続道路の建設により全員の速度が低下する可能性がある理論的な道路構成を発見しました。 逆に、Braesネットワークの1つの道路を閉鎖すると、誰もがより早く家に帰ることができます。 このような現象は非常に奇妙であるため、独自の定義に値する-Braes Paradox。
数年前、 Joel Cohenは、Braesのパラドックスがコンピューティングサイエンスの私のコラムにとって良いトピックになる可能性があると言った。 私はそれを疑った。 Cohen自身の驚くべき記事や、Tim Rafgardenの本 （私がAmerican Scientistのために書いたレビュー）を含め、このパラドックスに関する多くの議論をすでに公開しています 。 ディスカッションに新しいものを追加できるとは思いませんでした。
しかし、最近、私はBraesパラドックスを視覚化するタスクを検討し始めました-平均速度と旅行時間を計算するだけでなく、道路網を走行する個々の車を観察できるように表現します。 レバーとボタンを押してさまざまなルーティングアルゴリズムを試してモデルを実験する機能は、十分な情報と利己的なドライバーが結果として全員を遅くするルートを選択できる理由をより明確に理解することにつながります。
これで、JavaScriptで記述されたBraesのパラドックスに似た何かの実用モデルができました。 私はそれに乗ってみることをお勧めします 。 また、同誌のウェブサイトにHTMLとPDFで掲載されている米国科学者の 「Computing Science」列もあります 。 ソースコードに興味がある場合は、Githubにあります。 ここで、モデルの実装とそれが教えてくれたことについて少しお話したいと思います。
Braesの数学モデルをより機械的で視覚的な環境に適応させることは、予想以上に困難でした。 元の定式化はかなり抽象的であり、特に物理的ではありません。 高速道路の設計よりもグラフ理論に近い。 次の図では、 AおよびBというラベルの付いた幅の広い青い道路は混雑していません。 通過するトラフィックに関係なく、移動時間は常に1時間です。 狭い赤い道路aとbでは、空のときの移動時間はゼロですが、交通量は負荷の増加とともに増加します。 すべての車が1つの赤い道路に集まる場合、その車の運転時間も1時間になります。 ゴールデンルートXは、魔法のように任意の数の車両に瞬時に移動します。
パラドックスの存在は、道路Xの存在に依存します。 ゴールド接続（左図）がない場合、トラフィックはAbルートとaBルートの間で均等に分配され、すべての車が旅行全体で90分を費やします。 接続X （右の図）を開くと、すべてのドライバーはaXbルートを好み、全員が1時間2時間道路で過ごします。
このパラドックスに必要な仮定は、誰もが利己的なルート構築に努め、最速の移動を提供するパスを選択し、移動時間以外のすべての要因を無視することです。 皮肉なことに、他の人が短い旅行をしないように固執し 、ドライバーがaXbルートで交通渋滞を引き起こし 、 AXBは空のままです。 なんで？ ドライバーがAXBに移動することを決定した場合、ドライバーが不在の場合はaXbの負荷がわずかに軽減され、このルートの速度がわずかに向上します。 利己的な願望に続いて、別の道にシフトしたドライバーはaXbに戻るべきです 。 それは膠着状態になります。
無限の速度で移動する車や無限の帯域幅を持つ道路は数学モデルでは非常に適切ですが、シミュレーションでは問題が発生し、高速道路の実際のトラフィックをシミュレートする必要があります。 より現実的なモデルを探して、1997年のClaude M. Pinchinの記事（Braess Paradox：最小クリティカルネットワークでの最大ペナルティ。TransportationResearch A 31（5）：379–388）の図に触発され、以下に示す道路の場所に行きました。
回路のトポロジは元のBraesネットワークと同じですが、ジオメトリが異なるため、オーバーフローと速度の関係も異なります。 目標は、 最初から最後まで、またはOriginからDestinationまでを取得することです。 道路セクションAとBはまだ広く、交通渋滞の影響を受けません。 道路aとbはより直接的で短くなっていますが、同時に狭くなっています。 トラフィックがゼロの場合、 aおよびbのマシンの速度はAおよびBの速度と同じですが、負荷が増加すると速度が低下します。 「黄金の道」の類似物は、マップの中央にある短い橋で、 AとBの速度特性が同じです。 初期設定では、ブリッジはロックされていますが、マウスのクリックで開くことができます。 作業モデルの上のスクリーンショットでは、ブリッジが開いており、それに沿って移動しています。
色付きの点で表された車は、 Originのシステムに入ります。 入国時に、各車は可能なルートの1つを選択します。 ブリッジが閉じている場合、 AbとaBの 2つのオプションしかありません。 橋が開いている場合、ドライバーは短い道路abまたは長いABを選択することもできます。 その後、車は選択されたルートに沿って移動し、 目的地に到達するまで各セグメントの速度制限に従います。
このスキームは、いくつかの重要な点で元のBraesの定式化と異なります。 パラドックスを示していますか？ 言い換えると、橋が開いていて、ドライバーがabとABのルートに沿って移動できる場合、移動時間は長くなりますか？ 広範囲のパラメーター値に対する答えは「はい」であり、これは次の結果から確認できます。
表には、各ルートを選択した車の数と、道路で過ごした平均時間が表示されます。 （時間は、可能な限り最速の旅行の単位で測定されます。トラフィックがゼロの最短パスabに沿って。）ブリッジを開くと、4つのルートすべてで速度が低下します。 AbおよびaBルートのトラフィックは37％減少しましたが、これらのルートの車は旅行を完了するのに9〜15％長い時間が必要でした。 ルートabおよびABはさらに低速でした。
しかし、数値は状況を完全には明らかにしていません。これは、シミュレーションを開始した後に私が最初に気づいたことです。 閉じた橋の場合、総交通量が2つのほぼ等しいフローに分割されるとき、新しい車が交互にAbまたはaBを選択すると仮定できるため、システムは任意の時点で2つのルートのそれぞれに同数の車がある統計的に平衡状態に達します。 しかし、まったく異なることが起こっています！ シミュレーションを実行してこれを確認するのが最善ですが、下のグラフからもモデルの一般的な理解が得られます。
平衡状態に移行する代わりに、システムは約500時間周期で振動します。これは、平均的な自動車がOriginからDestinationに移動するのに要する時間の約半分に相当します。 2つの曲線は、ほぼ180度位相シフトされています。
そのような振動がどこから来るのかを理解するのは簡単です。 各車が道路網に入ると、現在の状態に基づいて予想される最短の移動時間でルートを選択します。 予想される移動時間の主な決定要因は、セグメントaとbを占める車の数であり、道路が満車になると速度が低下します。 しかし、車があまり人気のないルートを選択すると、このルートの占有率も増加し、後続の車にとっては望ましくなくなります。 さらに、車がオーバーフローの影響を受けるセクションに到達する前に、 Abルートに大幅な遅延があります。 ネットワークの遅延と非対称性により、不安定性が発生します。これは、外れ値と過剰な修正が避けられないフィードバックループです。
接続ブリッジが開いている場合、パターンはより複雑になりますが、振動は依然として非常に顕著です：
断続的な2つのフェーズがあるようです。1つはAbとabが支配的（この配色では赤緑のクリスマスフェーズ）で、もう1つはabとAB （黄緑のボーイスカウトフェーズ）が優勢です。 波の周期は規則的ではありませんが、基本的には長くなります。
私はそのような変動を最初に観察したわけではありません。 たとえば、ダニエル・ブシェマと同僚は、 NetLogoの Bralesのような道路ネットワークのシミュレーションを説明する記事で言及しています。 しかし、一般的に、文献のそのような変動と不安定性にはほとんど注意が払われていません。
回路の非対称性は、中央の接続ノードを開くときに振動と逆説的なスローダウンの両方を作成するために非常に重要です。 モデルの対称バージョンを実行することで、これを自分で確認できます。 彼女はかなり退屈だと判明しました。
動的モデルの別のバグ/機能にはコメントが必要です。 元のBraesネットワークでは、接続AとBの容量は無制限です。 実際、このモデルは、交通量に関係なく、これらの道路の移動時間が一定であることを約束しています。 非ゼロ次元の離散マシンを使用した動的モデルでは、この約束を守るのは困難です。 車がルートAbをたどり、セグメントbが完全に詰まっているとします。 Aがbに向かうジャンクションポイントでは、マシンはどこにも行けないため、セグメントAに戻ります。これにより、一定の速度を保証できません。
動的モデルを実装するときに、元のBraesシステムの数学的定式化はあまり役に立たない多くの解決策があることがわかりました。 それらの1つは、「キューの逆浸透」の問題でした。 車が道路上に積み重なるのを許可するのか、それとも目に見えないバッファーを与えて、旅を続けるために静かに順番を待つことができるのか？ 道路上に車の場所がないときに開始ノードに表示される車はどうですか？ それらをキューに入れてドロップし、別の道路に沿って進む車をブロックする必要がありますか？ 別の滑りやすい瞬間は、優先順位と誠実さに関するものです。 道路スキームの中央付近にある2つのノードには、2つの入口と2つの出口があります。 入り口の両方の列にノードの通過を待っている車がある場合、どちらが最初に移動しますか？ このような交通渋滞を処理するための戦略の選択に注意を払わないと、1つのルートが別のルートによって常にブロックされます。
JavaScriptコードを学んだので、私が選択したソリューションを理解できます。 私の答えが絶対に正しいとは言いません。 しかし、さらに重要なことは、多くの実験と代替ソリューションの研究の結果、ほとんどの詳細はそれほど重要ではないことがわかりました。 ブレス効果は非常に安定しており、多くのバージョンのモデルで、わずかに異なる仮定とアルゴリズムで現れます。 このような安定性は、逆説的なトラフィックパターンの証拠を得るために実際のルートをより詳しく調べる必要があることを示しています。