お知らせ

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

Pythonで待ち行列での待ち時間を調べてみた

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

こんにちは。今回も待ち行列をPythonで扱っていきます。

前回までは,Pythonで待ち行列の様子をシミュレーションするものでしたが,今回はどのくらいお客さんが待つかを調べてみます。

プログラムの変更点

前回は,お客さんが到着して,何か食べ物を注文して,受け取るまでの時間についてシミュレーションしてみました。

これを繰り返して,待ち時間の代表値を取ることにします。

ここで取得する代表値は,最短待ち時間(最小値),平均待ち時間(平均値),最長待ち時間(最大値)です。

それに伴う変数を加えたプログラムは次になります。

import random
import math
import sys

# パラメータを設定する
lam = 4
num = 50
counter = 1
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

for t in range( 0, times ):

    # 初期値を決める
    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] 

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] ) )    

それなりに変更点が多いので,具体的な変更点については割愛します。

実行してみる

来店するお客さんを100人,窓口の数を2個,シミュレーション回数を100万回にして実行してみます。

(Excelでは100万回のシミュレーションなんて,気が遠くなるのでできません)

到着順 最短待ち時間 待ち時間 最長待ち時間
    1        0.00     0.00        0.00
    2        0.00     0.00        0.00
    3        0.00    17.08       59.98
    4        0.00    23.25       59.97
    5        0.00    34.42      117.74
    6        0.00    42.38      117.70
    7        0.00    51.75      169.55
    8        0.00    60.12      173.49
    9        0.00    68.88      219.20
   10        0.00    77.32      222.19
   11        0.00    85.87      266.11
   12        0.00    94.27      268.96
   13        0.00   102.69      313.39
   14        0.00   111.08      316.32
   15        0.00   119.48      366.77
   16        0.00   127.81      360.51
   17        0.00   136.15      379.66
   18        0.00   144.50      398.49
   19        0.00   152.79      404.53
   20        0.00   161.07      449.43
   21        0.00   169.37      443.06
   22        0.00   177.64      461.36
   23        0.00   185.95      481.23
   24        0.00   194.22      504.49
   25        0.00   202.51      507.27
   26        0.00   210.79      545.06
   27        0.00   219.00      539.39
   28        0.00   227.29      555.63
   29        0.00   235.54      569.81
   30        0.00   243.82      600.51
   31        0.00   252.10      610.54
   32        0.00   260.38      612.48
   33        0.00   268.64      628.94
   34        0.00   276.87      655.15
   35        0.00   285.09      669.45
   36        0.00   293.33      669.68
   37        0.00   301.62      696.58
   38        0.00   309.89      707.20
   39        0.00   318.15      727.63
   40        0.00   326.40      750.76
   41        0.00   334.65      767.93
   42        0.00   342.92      796.60
   43        0.00   351.17      790.25
   44        0.00   359.43      820.05
   45        0.00   367.66      835.34
   46        0.00   375.92      824.47
   47        0.00   384.20      842.73
   48        0.00   392.44      876.19
   49        0.00   400.70      876.04
   50        0.00   408.92      880.14
   51        0.00   417.16      903.98
   52        0.00   425.43      931.87
   53        0.00   433.66      931.61
   54        0.00   441.91      975.53
   55        0.00   450.16      950.43
   56        0.00   458.40      985.79
   57        0.00   466.64      986.28
   58        0.00   474.91     1007.52
   59        0.00   483.17     1019.16
   60        0.00   491.44     1041.25
   61        0.00   499.69     1059.38
   62        0.00   507.95     1079.31
   63        0.00   516.18     1096.64
   64        0.00   524.44     1105.52
   65        0.00   532.70     1131.24
   66        0.00   540.92     1147.83
   67        0.00   549.19     1176.30
   68        0.00   557.46     1175.31
   69        0.00   565.72     1163.73
   70        0.00   573.99     1170.38
   71        0.00   582.26     1182.21
   72        0.00   590.50     1198.28
   73        0.00   598.72     1211.49
   74        0.00   606.96     1248.50
   75        0.00   615.20     1259.85
   76        0.00   623.44     1291.41
   77        0.00   631.68     1291.79
   78        0.00   639.90     1305.24
   79        0.00   648.18     1328.13
   80        0.00   656.42     1337.61
   81        0.00   664.70     1335.70
   82        0.00   672.96     1385.51
   83        0.00   681.22     1387.98
   84        0.00   689.50     1403.39
   85        0.00   697.73     1442.64
   86        0.00   705.97     1449.84
   87       12.23   714.22     1482.41
   88        8.76   722.49     1491.20
   89       14.19   730.73     1510.79
   90        4.11   738.98     1532.41
   91       13.51   747.22     1562.78
   92        2.73   755.46     1569.84
   93        4.83   763.71     1579.48
   94        0.00   771.96     1589.59
   95        0.00   780.21     1604.01
   96       14.86   788.45     1634.01
   97       10.42   796.70     1635.60
   98        1.69   804.95     1662.62
   99        0.00   813.23     1669.35
  100       12.68   821.48     1633.08

Sublime Text上で実行させたところ,約7分で結果が表示されました。

100万回のシミュレーションの詳細な記録は取っていませんが,ものすごく待たされる時とまったく待ち時間がない時の差が激しそうです。

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

この記事を書いた人
春日井 優

高校で情報科という教科を担当しています。以前は数学科も担当していました。(今でも数学科の教員免許状は有効です。)プログラムを覚えたのは、「ゲームセンターあらし」という漫画のキャラクターがBASICを解説する「こんにちはマイコン」を読んだことがきっかけでした。

Posted by kasugai