お知らせ

ただいま、シンタックスハイライターの設定を見直しております。
プログラムが見にくくなっているページがありますが、ご容赦ください。

Pythonで待ち行列の長さを調べてみた

モデル化とシミュレーション

こんにちは。まだまだ待ち行列のプログラムに手を加えていくことにします。

前回との変更点

待ち行列の長さを調べられるよう,窓口で注文する時刻をリストで蓄えておきます。

本当はリストの処理をうまくすることで,実行時間を減らせそうに思うのですが,プログラムを書く時間が取れないので処理が遅いまま掲載します。

変更点1 最長の待ち行列の長さを記憶する変数を作った

max_length = 0

変更点2 各お客さんの開始時刻を記憶する変数を作った

    que = [ [] ] * counter

変更点3 お客さんの開始時刻を追加して,自分より前に到着しているのに開始していない人数を数えた

        que[counter_no].append( start_time )

        l = 0
        for q in que[counter_no]:
            if q>arrival_time:
                l += 1
        max_length = l if max_length < l else max_length

変更点4 最長の待ち行列の長さを表示するようにした

print('待ち行列の長さの最長 {}人'.format(max_length))

完成したプログラム

変更の結果,プログラムは次のようになりました。

import random
import math
import sys

# パラメータを設定する
lam = 4
num = 100
counter = 2
menu = [ ('うどん',  0.15, 40 ),
         ('そば' ,  0.1 , 30 ),
         ('ラーメン', 0.2 , 50 ),
         ('カレー',  0.25, 20 ),
         ('定食',  0.3 , 60 ) ]
times = 1000000
wait_total = [ 0 ] * num
min_wait = [ sys.float_info.max ] * num
max_wait = [ 0 ] * num
max_length = 0

for t in range( 0, times ):

    # 初期値を決める
    que = [ [] ] * counter
    arrival_time = 0
    end_time = [ 0 ] * counter

    # お客さんごとにシミュレーションする
    for i in range( 0, num ):
        # お客さんが来る時刻を決める
        r = random.random()
        interval = -60 * math.log( 1 - r ) / lam
        arrival_time += interval

        # お客さんが並ぶ窓口を決める
        counter_no, mi = 0, end_time[0]
        for j, e in enumerate( end_time[1:], 1 ):
            if mi > e:
                counter_no, mi = j, e

        # お客さんが注文するものを決める
        r = random.random()
        probability = 0
        for item in menu:
            if probability > r:
                break
            probability += item[1]

        # 時間を計算する
        start_time = arrival_time if arrival_time > end_time[counter_no] else end_time[counter_no]
        end_time[counter_no] = start_time + item[2]
        wait_time = start_time - arrival_time
        wait_total[i] += wait_time
        min_wait[i] = wait_time if min_wait[i] > wait_time else min_wait[i] 
        max_wait[i] = wait_time if max_wait[i] < wait_time else max_wait[i]
        que[counter_no].append( start_time )

        l = 0
        for q in que[counter_no]:
            if q>arrival_time:
                l += 1
        max_length = l if max_length < l else max_length

print( '到着順 最短待ち時間 待ち時間 最長待ち時間')
for i, w in enumerate(wait_total):
    print( '{:5d}{:12.2f}{:9.2f}{:12.2f}'.format( i+1, min_wait[i], w/times, max_wait[i] ) )

print('待ち行列の長さの最長 {}人'.format(max_length))

実行結果

それでは実行してみます。よせばいいのに100万回もループさせています。手元の環境では20分ほどかかりました。

到着順 最短待ち時間 待ち時間 最長待ち時間
    1        0.00     0.00        0.00
    2        0.00     0.00        0.00
    3        0.00    17.10       59.99
    4        0.00    23.26       59.98
    5        0.00    34.41      117.96
    6        0.00    42.34      118.40
    7        0.00    51.74      172.31
    8        0.00    60.10      173.33
    9        0.00    68.91      221.09
   10        0.00    77.32      224.04
   11        0.00    85.87      263.42
   12        0.00    94.24      273.58
   13        0.00   102.66      301.40
   14        0.00   111.03      306.76
   15        0.00   119.45      345.79
   16        0.00   127.74      349.91
   17        0.00   136.08      374.53
   18        0.00   144.36      393.81
   19        0.00   152.68      408.92
   20        0.00   160.99      420.04
   21        0.00   169.21      445.36
   22        0.00   177.50      467.32
   23        0.00   185.75      480.81
   24        0.00   194.01      478.59
   25        0.00   202.27      507.62
   26        0.00   210.51      532.69
   27        0.00   218.79      533.23
   28        0.00   227.05      589.97
   29        0.00   235.36      577.39
   30        0.00   243.59      612.18
   31        0.00   251.87      608.70
   32        0.00   260.10      638.25
   33        0.00   268.36      648.26
   34        0.00   276.61      671.96
   35        0.00   284.85      672.43
   36        0.00   293.14      695.18
   37        0.00   301.35      693.17
   38        0.00   309.64      719.87
   39        0.00   317.92      736.96
   40        0.00   326.20      756.01
   41        0.00   334.43      772.40
   42        0.00   342.73      774.17
   43        0.00   350.97      784.19
   44        0.00   359.23      795.13
   45        0.00   367.48      813.94
   46        0.00   375.74      832.18
   47        0.00   384.00      835.04
   48        0.00   392.23      842.06
   49        0.00   400.50      854.09
   50        0.00   408.74      873.24
   51        0.00   416.96      873.78
   52        0.00   425.18      901.34
   53        0.00   433.45      916.18
   54        0.00   441.67      956.39
   55        0.00   449.96      948.70
   56        0.00   458.18      964.45
   57        0.00   466.43      964.33
   58        0.00   474.68      990.23
   59        0.00   482.92     1012.98
   60        0.00   491.19     1032.75
   61        0.00   499.43     1018.96
   62        0.00   507.67     1032.00
   63        0.00   515.93     1048.51
   64        0.00   524.18     1056.15
   65        0.00   532.44     1080.94
   66        0.00   540.71     1089.02
   67        0.00   548.99     1117.22
   68        0.00   557.23     1137.96
   69        0.00   565.47     1127.94
   70        0.00   573.75     1154.31
   71        0.00   582.01     1163.66
   72        0.00   590.25     1161.78
   73        0.00   598.49     1168.20
   74        0.00   606.74     1192.85
   75        0.00   614.97     1215.14
   76        0.00   623.20     1229.84
   77        0.00   631.46     1230.87
   78        0.00   639.70     1241.27
   79        0.00   647.95     1277.70
   80        0.00   656.18     1290.26
   81        0.00   664.43     1290.97
   82        0.00   672.71     1306.55
   83        0.00   680.94     1302.79
   84        0.00   689.21     1319.33
   85        0.00   697.44     1310.95
   86        0.00   705.72     1336.19
   87        0.09   713.97     1348.09
   88       16.03   722.27     1345.18
   89       21.58   730.53     1365.67
   90       15.50   738.79     1383.16
   91        0.00   747.08     1389.18
   92        4.56   755.36     1410.90
   93       26.64   763.63     1408.95
   94       11.52   771.88     1439.54
   95        1.00   780.16     1448.79
   96       26.66   788.43     1451.69
   97       22.63   796.70     1466.71
   98       52.23   804.91     1505.80
   99       33.46   813.18     1511.16
  100       35.47   821.41     1521.31
待ち行列の長さの最長 64人

窓口が2個の場合,64人も並んでしまうことがあるようです。

今回はこれでおしまいにします。それではまた。

Posted by kasugai