ブライスのパラドックス(Braess’ Paradox)!経路を増やしたのに渋滞する!?

テクノロジー

皆さんこんにちは!

今回は、ブライスのパラドックスという、交通工学などのネットワークの問題におけるパラドックスについて紹介します!

ブライスのパラドックスとはどんなパラドックスか?

ブライスのパラドックスは、

交通網のようなものを考え、ある出発地から目的地にいくつかの車が移動するとき、道を新たに作り、利用できる経路を増やしたのにも関わらず、目的地に到着する時間が増加してしまう

というものです。

不思議ですよね。道が増えれば選択できる経路が増えるので、目的地までの所要時間は減り、混雑は緩和されそうな気がします。

反対に言えば、ブライスのパラドックスが起きる、つまり、道を増やせばより渋滞するときがあるなら、余計な道路を封鎖すれば、渋滞はむしろ緩和される場合があるということです。

このブライスのパラドックスを詳しく説明していきますが、その前に、利用者均衡流という考え方を定義しておく必要があります。

利用者均衡流という考え方

ブライスのパラドックスの説明の前に、利用者均衡流について説明します。

下のように、出発地Sから目的地Gに車が移動する状況を考えます。

この道を通る車が多くなってくると、渋滞が発生し、目的地まで行く時間が増加します。

ここで、新たな道を作ったとします。すると、以下の図のように、少し遠回りしてでも、空いている道を使ったほうが早く目的地まで行けるので、遠回りの道を使う車が出てきます。

ただし、各車両の運転手は、すべての道の混雑状況を把握しているものとします。

そして、新しい、遠回りの道もそれなりに込んでくると、以下の図のように、2つの道の目的地までの所要時間が等しくなります。

こうなってくると、車はどちらの道に切り替えても、所要時間を短縮することはできません。

この各経路の目的地までの所要時間がすべて等しくなった状態を、利用者均衡(利用者均衡配分、ユーザー最適化)といいます。

以上では簡単に説明しましたが、もっと厳密に言えば、利用者均衡の条件はWardropの第一原理という名前で、以下のように与えられています。

それぞれのドライバーは自分にとって最も時間の短い経路を選択する。 その結果、存在する経路のうち、利用される経路の所要時間は皆等しく、利用されない経路の旅行時間よりも小さいか、せいぜい等しい状態になる。

これは、上で説明したものと同じ意味です。

ブライスのパラドックスの簡単な例

では、ブライスのパラドックスの説明をしていきます。

以下のようなネットワークを考えます。これは、道路や交差点をモデル化したものだと思ってください。

a~dの記号のついた矢印をリンクと呼びます。道路だと思ってください。①が出発地で、④が目的地です。②、③は交差点や、曲がりかどだと思ってください。道路の形状が変わる位置です。①、②、③、④のことをノードと呼びます。

各リンク(道路)の横に書いてあるのが、コスト関数と呼ばれる、各リンクを通過するのにかかる時間です。また、f_a, f_b, f_c, f_d を各リンクを通る車両の台数とします(一般に、流量と呼ばれる)。

例えば、リンクaを通過するのにかかる時間は 10f_a で、通過する車両の数に比例する、つまり、リンクaを通る車が多くなればなるほど、このリンクを通過するのにかかる時間がかかるようになっています。

さて、このネットワークに、出発地①から車を6台流すことにしましょう(この車両の台数を需要といいます)。④が目的地です。

下のように、ノード①→②→④のような経路と、①→③→④のような経路が考えられます(赤色の矢印)。

先ほど説明した利用者均衡の考え方を使えば、この2つの経路を通過する車の数はそれぞれ3台ずつになります。実際、 ①→②→④ の経路の所要時間は、リンクaを通過するのに10×3、リンクcを追加するのに3+50かかるので、合計で83で、一方で ①→③→④ の経路も同様に所要時間は83となっており、利用者均衡となっていることが分ります。

(□の中の数字は車両の台数)

さて、次に、以下のように②→③につながる道を増やしてみましょう。直感的には、道が増えたので、出発地から目的地まで所要時間は減るはずです。

この新たなリンクeのコスト関数を f_e+10 としましょう。

先ほどと同じように、①から6台の車を出発させます。

この場合、以下のように3つの経路が考えられます。

Wardropの第一原理より、使わている各経路の所要時間が等しくなるように車両は流れるので、どの経路にも2台ずつ車が通ることになります。各経路の所要時間を計算してみてください。すべて、同じになっているはずです。例えば、 ①→②→④ の経路では、10×(2+2)+(2+50) = 92となり、他の経路も同様に所要時間が92になります。

以上で見られたように、リンクeがないときには所要時間が83だったにもかかわらず、渋滞を緩和させようとしてリンクeを付け加えたら、所要時間が92に増えてしまいました。

この直感に反した現象を、ブライスのパラドックスといいます。

『道を増やしたらより渋滞してしまった』を言い換えれば、『道を減らしたら渋滞が減る』ということも起きる可能性があり、これを実際に現実社会に利用した例があります。

ただし、ここでは例として、ブライスのパラドックスが起きるようにリンクのコスト関数を設定しました。つまり、いつでもパラドックスが起きるわけではなく、コスト関数や、出発する車両の台数(需要)、ネットワークの構造などによって起きる起きないが変化します。

ブライスのパラドックスの現実例

交通工学的には、ブライスのパラドックスの現実例として、ドイツのStuttgartやニューヨーク、韓国のソウルの道路で実際に観測されています。

ブライスのパラドックスは、こういった交通工学の分野以外でも見られます。以上でネットワークを考えてブライスのパラドックスを起こしたことからわかるように、ネットワーク系の問題であれば、パラドックスが起きる可能性があるのです。

たとえば、回路の問題でもブライスのパラドックスは起きます。車両を電流と見立て、所要時間を電圧とみればよいのです。同様に、水路でも起きるでしょう。

回路におけるブライスのパラドックスについては、例えばこのような論文があります。

インターネットのネットワーク問題でも、活用されていそうです。

力学的にも、こんな動画があります。

Braess' Paradox: A Physical Demonstration

コメント

タイトルとURLをコピーしました