待ち行列理論 その４

渋滞学というある種の待ち行列理論の応用について説明をしようと思う。

渋滞学とは

上記リンク先の本では渋滞を「ある条件下で動作する排除体積効果を持つ個体からなる集団がある密度を超えたときに発生する状態」としている。これはつまり「ある条件を基に動作する個体が各々重なる(複数の個体が同一空間を占有する)ことなく存在する集団においてある一定の密度(臨界密度)を超える密度になった時に発生する特異な現象のこと」となる。おそらくまだ何を言っているのかわからないと思うので車を例にして説明する。その前提として個体＝車、集団＝車のみからなる一列であることに注意する。すると渋滞とは「前方が開いているときに前方に進むルールの下で進車がある交通密度を超えたときに発生する現象で、多くの車が前方に進むのが難しくなったり法定速度より著しく遅い速度でしか走ることができなかったりといったような特異的な状況」のことである。
今後この車の例を基に話をする。車以外の渋滞で渋滞学が扱うことのできる渋滞を知りたいならググるかAmazonで渋滞学を購入して読んでほしい。

車の渋滞の簡単なシミュレーション

今回は一番簡単なシミュレーションとしてセルオートマトンを使おうと思う。セルオートマトンは、2次元であるルールだとライフゲームと呼ばれるが、今回は一次元でそのルールは「一つ前が空いていれば進む」というルールにする。セルオートマトンについてはWikipedia参照のこと。

シミュレーション用のPythonプログラム

まず最初にコードを載せる。

trafic.py

# -*- coding: utf-8 -*-

# 一次元セルオートマトンによる渋滞の状態変化
import random
import copy

MAX = 45
SIM_TIME = 5
P = 0.6

# 状態0は車なしの空きスペース
# 状態1は車両を表す
trafic = [0 for i in range(MAX)]


def list2string(l):
    string = ""
    for state in l:
        if state == 0:
            s = "□ "
        elif state == 1:
            s = "■ "
        string += s
    return string


def setRandom(l, p):
    for i, state in enumerate(l):
        if p < random.random():
            l[i] = 0
        else:
            l[i] = 1


def nextTime(l):
    temp = copy.deepcopy(l)
    for i, state in enumerate(l):
        if state == 0:
            # 左端なら
            if i == 0:
                temp[i] = 0
            # それ以外のとき後方チェック
            elif l[i-1] == 0:
                temp[i] = 0
            else:
                temp[i] = 1

        elif state == 1:
            # 右端なら
            if i == len(l)-1:
                temp[i] = 0
            # それ以外のとき前方チェック
            elif l[i+1] == 0:
                temp[i] = 0
            else:
                temp[i] = 1
    return temp

if __name__ == "__main__":
    # 実行部分
    setRandom(trafic, P)
    print(list2string(trafic))

    for i in range(SIM_TIME):
        # 情報を更新
        trafic = nextTime(trafic)
        # 情報を文字にして描画
        print(list2string(trafic))

コードの解説をします。

最初に定義された変数と定数を説明します。
MAXという変数は後に定義するtraficの最大の大きさ、つまり車が並ぶ最大の長さを表しています。
次のSIM_TIMEはシミュレーションを行う時間の長さで、Pは交通密度です。
そしてtraficというリストは車がある(1)ない(0)の二種類の状態のみを取るリストで最初は初期化として0に統一しています。

次に定義された関数を説明します。
最初のlist2string関数は引数として与えられた0と1のみの状態を持つリストに対して□と■を対応させて文字に変換して文字を返す関数です。
setRandom関数は二つ目の引数の値を境にして車があるないをセットしていく関数です。
nextTime関数はその時点での車の状態に応じて進めるかどうかを調べて次の状態を返す関数です。場合分けはコメントを見るとわかると思います。

最後は実行部分です。
ここは特に説明する必要はなくコメントで十分だと思います。
このコードを書き換えて環状の道路にしたり、車がすべていなくなった時にループから抜けるとしてもいいかもしれません。

シミュレーションの結果のまとめと説明

Pの値をいくつか変えて実行してみるとPが0.5を境にして挙動が大きく変わるかと思います。(乱数を使っているので大きく変わらないこともあるかもしれませんが。)

変化する理由を考えてみます。
そもそも車が動くためには前方が開いていることが必要不可欠です。そこで車の前方が開いている状態をどの車でも満たすようにしてとにかく詰めてみます。そうするとその状態は車のあるなしが交互に出てくる状態となっているはずです。もちろんこの状態では渋滞など起きることなくスムーズに進むことができると思います。
しかしそこに車を一台入れてみるとどうでしょうか。どこに車を入れても渋滞が発生すると思います。
このときの0.5という値をその交通の臨界密度といいます。臨界密度を超えていなければ長い時間をかければ渋滞が一部でできたとしても必ず解消されます。しかし超えているといつまでたっても解消されません。
実はこの結果は現実でも臨界密度の値は違いますが成り立つことがわかっています。その為、渋滞が頻発するところではこの臨界密度という考え方を考慮して渋滞の解消が行われています。

最後に

ここで述べた説明のさらに詳しい説明は最初に挙げた渋滞学という本にも載っています。他にも「好ましい渋滞」など興味深い渋滞も出てくるのでぜひ読んでほしいです。