より広い道路の建設は、交通状況を悪化させる可能性があります。 通常、この逆直感的で非生産的な結果は次のように説明されます：道路が多いほど、彼らはより大きなショッピングセンターを引き付け、それはより多くの車を引き付けます。 しかし、これはすべてではありません。 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コードを学んだので、私が選択したソリューションを理解できます。 私の答えが絶対に正しいとは言いません。 しかし、さらに重要なことは、多くの実験と代替ソリューションの研究の結果、ほとんどの詳細はそれほど重要ではないことがわかりました。 ブレス効果は非常に安定しており、多くのバージョンのモデルで、わずかに異なる仮定とアルゴリズムで現れます。 このような安定性は、逆説的なトラフィックパターンの証拠を得るために実際のルートをより詳しく調べる必要があることを示しています。