理系リアルタイム

大学院生の情報ブログ

テクノロジー 理系

ブライスのパラドックス(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やニューヨーク、韓国のソウルの道路で実際に観測されています。

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

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

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

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

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

-テクノロジー, 理系

執筆者:


comment

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です

関連記事

【YouTuberの始め方】YouTube動画編集におすすめな初心者向け無料動画ソフトを一覧にしてみる!5選【2019年】

みなさんこんにちは!! YouTube自体は昔からあるものの、最近とくにYouTubeを始めようというひとが多いですよね。 しかし、どうやって始めればいいのかわからない… YouTubeに動画を上げる …

【初心者ブロガー必見】申請から!Googleアドセンス広告をブログに張る方法を簡単に解説!【始め方】

この記事は自分のサイト(ブログなど)を使って広告収入を得たい人に向けたものです。ただし、アフェリエイトとは別の広告収入であるGoogleアドセンスについてです。 みなさんこんにちは!! この記事を見て …

【ネット依存症】ブログを始めてわかった、ネットをあまり気にしない方がいい理由【情報時代の生き残り方】

こんにちは!ATSです!

【Google AdSense】【ブログ】初の申請後、たった5時間でGoogeleアドセンス審査が通ったブログの条件

Googleユーザーのみなさんこんばんは!ATSです!! みなさん、ググってますか?? 世の中で使われてる検索エンジンはGoogleかBingのほぼ2択ですし、Googleエンジンが圧倒してますから、 …

【暗黒物質】ダークマター アクシオン(Dark Matter Axion)について詳しく解説!【上級編】

※この記事はある程度物理の知識がある方を対象に書かれています。物理にあまり精通していない方は、【初級編】ダークマター アクシオンをご覧ください。 今回は、ダークマターと呼ばれる未知の物質を構成する素粒 …

理系リアルタイム 管理人

理系大学院生。

名古屋大学大学院工学研究科。

いつか人工衛星を打ち上げたいと夢見ている。生息地は度々変わるので不明。興味があること→物理/laser/機械学習/backpacker/ドローン/海外移住

理系リアルタイムでは、大学生・大学院院生に知ってもらいたい情報、体験を発信しています!!気になることがあれば、お気軽にご連絡ください。

管理人のTwitter もよろしくお願いします!!