待 ち 行 列 ( 食 堂 シミュレーション) Excel による OR 演 習 藤 田 勝 康 著 ( 日 科 技 連 )より サービスが 提 供 される 窓 口 で 順 番 を 待 っている お 客 の 列 を 待 ち 行 列 という. 待 ち 行 列 シミュレ ーションとは, 待 ち 行 列 の 最 大 長 や 平 均 待 ち 時 間 な どを 予 測 するためのシミュレーションである. たとえばある 学 生 食 堂 を 考 えてみる.メニューは カレー,ラーメン,そば, 定 食 の 4 種 類 で, 窓 口 は 1 つ. 昼 休 みの 1 時 間 のうちに 平 均 100 人 の 学 生 が 食 堂 を 利 用 する.メニューごとのサービス( 調 理 ) 時 間 と 注 文 の 割 合 は 次 の 表 のようになっている. メニュー サービス 時 間 ( 分 ) 割 合 カレー 0.5 0.15 ラーメン 3 0.20 定 食 2 0.25 そば 1 0.40 さてこの 食 堂 において, 昼 休 み 中 の 待 ち 行 列 の 最 大 長 や 1 人 あたりの 平 均 待 ち 時 間 はどれくらいにな るだろう? この 問 題 を 待 ち 行 列 シミュレーション で 解 いてみた 結 果 が 下 図 (ワークシート)である. 待 ち 行 列 シミュレーションも 乱 数 を 利 用 するモ ンテカルロ 法 の 一 つである.この 問 題 では, 客 の 到 着 時 刻 と 注 文 するメニューを 乱 数 で 決 定 している. 到 着 時 刻 シミュレーションでは 先 ず, 到 着 と 名 づけられた 列 (B13:B42)に 発 生 させた 0-1 の 一 様 乱 数 (こ こで Excel の 分 析 ツールを 使 用 しての 乱 数 を 発 生 さ せている)から,お 客 一 人 ひとりの 到 着 時 刻 ( 経 過 時 間 )を 決 定 する.だが,その 前 に 待 ち 行 列 シミュ レーションで 多 用 される 指 数 分 布 について 説 明 し ておこう. この 問 題 のように, 客 がランダムに 到 着 する 場 合, 前 の 客 から 次 の 客 までの 到 着 時 間 間 隔 (t)は 指 数 分 布 に 従 うことがわかっている( 人 数 はポアソン 分 - 24 -
布 ). x = e μ t である.つまり,H13:H42 への 返 値 は,$C$6:$E$9 の 2 行 目 の 値 (D6:D9)すなわち 調 理 時 間 から 選 ば れる. 図 では C13 の 乱 数 が 0.10068056 であるから H13 はカレーの 調 理 時 間 の 0.5 分 となる. ここで x はある 時 間 の 間 に 客 が 到 着 する 確 率 (0-1), μ は 単 位 時 間 当 たりに 到 着 する 平 均 の 人 数 (この 問 題 では 100 人 /60 分 )である. 上 式 を 到 着 時 間 間 隔 (t)について 変 形 すると 下 式 のようになる. t = 1 ln( x) μ すなわち 0-1 の 乱 数 を 上 式 の x に 代 入 すれば, 前 の 客 が 到 着 してから 次 の 客 が 到 着 するまでの 時 間 間 隔 (t)を 計 算 できる. 例 示 したワークシートでは,B13:B42 の 乱 数 をう けて 到 着 時 間 と 名 づけた E13:E42 で 到 着 時 間 間 隔 を 計 算 している.たとえば E13 に 入 っている 式 は =-0.6*LN(B13).ここで 0.6 は μ の 逆 数 で 60 分 /100 人 である. 次 に,これら 到 着 時 間 間 隔 の 累 積 値 が 経 過 時 間 と 名 づけた F13:F42 の 到 着 時 刻 となる.たとえば, F13 だけは, 最 初 だから =E13 であるが,F14 には =F13+E14 の 式 が 入 っている.すなわち F14 の 客 の 到 着 時 刻 は, 前 の 客 の 到 着 時 刻 (F13)に, 前 の 客 から 今 の 客 までの 到 着 時 間 間 隔 (E14)を 加 えた 値 となる.F15 以 降 のセルに 入 っているのは, F14 をコピーペーストした 式 である. サービス 注 文 調 理 時 間 続 いて, 到 着 した 客 が 何 を 注 文 するか (D13:D42)については,Excel の VLOOKUP 関 数 を 使 って,サービスと 名 づけた C13:C42 の 別 組 の 一 様 乱 数 (0-1)( 分 析 ツールで 生 成 )から 決 定 する.たとえば 先 頭 の D13 に 入 っているのは =VLOOKUP (C13,$C$6: $E$9,3) という 式 である. 式 の 意 味 としては, 第 1 引 数 C13 の 値 ( 乱 数 )を 第 2 引 数 である 表 ($C$6:$E$9)( 全 体 参 照 となっていることに 注 意 )の 区 分 ($C$6:$C$9)に 照 らし 合 わせて, 第 3 引 数 の 3,すなわち 表 の 3 列 目 の 値 (E6:E9)のうち 相 当 する 区 分 の 値 を 返 すと いうものだ. 0 C6 < 0. 15 ならカレーが, 0.15 C6 < 0.35 ならラーメン, 0.35 C6 < 0. 60 なら 定 食, 0.60 C6 ならば,そばの 文 字 列 が D13 に 返 される. 図 では C13 の 乱 数 が 0.10068056 であるか ら D13 はカレーとなる. また 調 理 時 間 H13:H42 も 同 様 である.たとえば H13 に 入 っ て い る の は =VLOOKUP(C13,$C$6:$E$9,2) で, 注 文 の D13 との 違 いは, 第 3 引 数 の 3 が 2 に 替 わっているだけ サービス 開 始 終 了 時 刻 さて, 注 文 を 受 けてのサービス 開 始 時 刻 を 計 算 し ている 列 が G13:G42 である.G13 の 場 合 は, 最 初 の 客 であるからサービス 開 始 時 刻 は 当 然 =F13 で,1 人 目 の 客 の 到 着 時 刻 に 等 しい.またサービス の 終 了 時 刻 は,たとえば I13 なら, 開 始 時 刻 に 調 理 時 間 (H13)を 加 えた =G13+H13 となる.しか し 問 題 は 2 人 目 の 客 (G14) 以 降 のサービス 開 始 時 刻 である. 仮 に 2 人 目 の 客 が 到 着 しても, 前 の 客 に 対 するサービスが 終 了 していなければ,そのサービ スが 終 了 するまで,2 人 目 の 客 に 対 するサービスは 開 始 できない.これを 表 現 するために,たとえば G14 には =IF(F14>I13,F14,I13) という 式 が 入 っ ている.これは 経 過 時 間 (F14)とサービス 終 了 時 刻 (I13)とを 比 べて,F14>I13(2 人 目 の 到 着 時 刻 が 1 人 目 のサービス 終 了 後 )なら 2 人 目 の 到 着 客 に 対 するサービスを 客 の 到 着 と 同 時 に,そうでなけれ ば(2 人 目 が 到 着 した 時 にまだ 1 人 目 のサービスが 終 了 していなければ)1 人 目 のサービス 終 了 と 同 時 に 開 始 するという 意 味 である. 待 ち 時 間 空 き 時 間 したがって 客 の 待 ち 時 間 を 求 める 式 は,たとえば J13 なら =IF(G13-F13>=0,G13-F13,0),K13 の 窓 口 の 空 き 時 間 を 求 める 式 なら =IF(G13-F13<0, -G13+F13,0) となる.これらの 式 が 意 味 するとこ ろは,サービスの 開 始 時 刻 (G13)が 客 の 到 着 時 刻 ( 経 過 時 間 F13)より 遅 ければ, 当 然,その 遅 れ (G13-F13)が 客 の 待 ち 時 間 となり, 逆 に,サービ スの 開 始 時 刻 (G13)が 客 の 到 着 時 刻 ( 経 過 時 間 F13)より 早 ければ,その 間 の 時 間 (F13-G13)が 窓 口 の 空 き 時 間 になるということである. 待 ち 人 数 最 後 が 待 ち 人 数,すなわち 待 ち 行 列 の 長 さ (L13:L42)の 計 算 である.この 計 算 には Excel の FREQUECY 関 数 を 用 いる.たとえば L13 には = FREQUENCY(F13:$F$42,G13) という 式 が 入 っ ている(ここでは F13 と G13 が 相 対 参 照 で,$F$42 だけが 絶 対 参 照 となっている 点 に 注 意 しよう).こ の 式 は,1 人 目 (F13)から 最 後 30 人 目 ($F$42) までの 到 着 時 刻 ( 経 過 時 間 )の 内, 最 初 のサービス 開 始 時 刻 (G13)までに(あるいは 同 時 に) 到 着 し た 客 が 何 人 いるかという 値 を 返 している. 念 のた めに 次 の L14 も 見 てみよう.このセルには =FREQUENCY (F14:$F$42,G14) という 式 が 入 っており(L13 をコピーペーストしたもの),2-25 -
人 目 の 到 着 時 刻 (F14)から 30 人 目 ($F$42)まで のすべての 到 着 時 刻 と 2 人 目 の 客 に 対 するサービス 開 始 時 刻 (G14)を 比 べて, 待 ち 行 列 の 人 数 を 計 算 している.ワークシートの 例 では,2 人 目 のサービ ス 開 始 時 刻 にはすでに 3 人 目 の 客 が 到 着 しているが, 1 人 目 のサービスは 終 了 しているため, 待 ち 行 列 の 人 数 は 差 し 引 き 2 人 である. ワークシートの 例 では 待 ち 行 列 が 昼 休 み 開 始 26 分 後 に 最 長 で 15 人 となる.また,J44 に 示 すよう に, 待 ち 時 間 の 平 均 は 約 12.4 分, 待 ち 行 列 の 長 さ (L44)は 平 均 で 約 7 人 となる. 最 後 の 30 人 目 の 人 はカレーを 受 け 取 るまでに 約 25 分 も 並 んでいな ければならない. 注 意 として, 例 では,30 分 経 過 したあたりから, 行 列 人 数 が 減 っているように 見 える.が,これはあ くまで 30 人 しか 客 が 来 なかったからである.もと もとは 1 時 間 で 100 人 がくるという 想 定 であったこ とを 思 い 出 してみよう.その 意 味 で,このシミュレ ーションの 設 定 条 件 にはやや 無 理 がある. ちなみにこの 例 で, 窓 口 の 混 雑 を 緩 和 するために 窓 口 をラーメンとそばの 麺 物 と,カレーと 定 食 の 飯 物 の 2 箇 所 にわけてみた 場 合 のシミュレーション 結 果 を 下 に 示 す. シミュレーションのやり 方 としては 特 に 先 の 例 と 変 わっているところはない.30 人 の 2 組 の 乱 数 はそのままに, 注 文 するメニューによって, 麺 物 か 飯 物 の 2 つの 窓 口 に 分 かれて 並 ぶと 考 えたものであ る. 図 からわかるように, 窓 口 を 2 つに 分 けること で, 平 均 の 待 ち 時 間 はそれぞれ 約 9 分 と 4 分, 行 列 の 最 大 長 は 10 人 と 6 人, 平 均 行 列 長 さは 約 5 人 と 4 人 に 減 っており,ある 程 度 の 混 雑 の 緩 和 はできた ことがわかる.ただし, 以 上 はたった 30 組 の 乱 数 による 1 回 きりの 結 果 である. 厳 密 なシミュレーシ ョンのためには,より 多 くのケースを 試 行 して,そ の 平 均 を 求 める 必 要 がある. - 26 -
4.ベスト メートを 探 して 確 率 論 の 有 名 な 問 題 として 持 参 金 問 題 あるい は 秘 書 問 題 美 人 コンテスト 問 題 と 呼 ばれる 問 題 がある. 持 参 金 問 題 には,アラブの 王 様 が 登 場 する. 王 は あるとき 自 分 に 仕 える 大 臣 の 賢 さを 試 したいと 思 い 立 つ.たまたま 大 臣 はそのころ 妻 を 探 していた. そこで 王 は 国 中 から 100 人 の 女 性 を 集 め, 大 臣 の 前 に 一 列 に 並 ばせ, 大 臣 を 試 すことにした. 大 臣 はこ の 100 人 の 中 から 持 参 金 が 一 番 多 い 女 性 を 選 ばな ければならない.もし 正 しく 選 べれば, 大 臣 はその 女 性 と 結 婚 でき, 大 臣 の 地 位 にも 留 まることができ る.しかし 失 敗 すれば, 結 婚 できないばかりでなく, 大 臣 の 地 位 まで 失 ってしまう. 大 臣 には, 一 列 に 並 んだ 女 性 の 一 人 ひとりに 対 し て 持 参 金 の 額 を 尋 ねることが 許 されている.ただし, 持 参 金 額 を 聞 いたその 場 でその 女 性 を 選 ぶかどう かを 決 めなければならない. 選 ばないのなら,その 女 性 をパスして 次 の 女 性 に 持 参 金 の 額 を 聞 く.しか し, 一 度 パスした 女 性 を 選 ぶことは 許 されていない. 大 臣 は 持 参 金 の 最 高 額 についても 何 も 知 らされて いない.どのような 戦 略 を 用 いれば, 一 番 持 参 金 の 高 い 女 性 を 選 べる 確 率 を 一 番 高 くできるだろうか. この 持 参 金 問 題 については, 多 くの 研 究 がなされ ており 37%ルール 1 という 方 法 が 最 良 の 戦 略 だと わかっている. 37%ルール とはつぎのような 戦 略 だ. 最 初 の 37 人 (つまり 37%)の 女 性 は 持 参 金 額 を 聞 くだけにす る.ただし,その 37 人 の 中 で 最 高 の 持 参 金 額 を 憶 えておく.この 額 を D とおこう. 次 に,38 人 目 か ら 持 参 金 を 聞 く 作 業 を 再 開 して,D を 超 えた 最 初 の 女 性 を 選 ぶというものだ. 理 論 的 には,これによっ て 37%の 確 率 で 一 番 持 参 金 の 高 い 女 性 を 選 ぶこと ができる... 37%ルール は 一 番 持 参 金 の 高 い 女 性 を 選 ぶため には 最 良 の 方 法 である.しかし,この 一 番 とい う 条 件 を 緩 和 すると 37%ルール に 取 って 代 わる 別 の 戦 略 が 浮 上 してくる.この 問 題 をシミュレーシ ョンで 解 いて 見 せたのが Peter M. Todd の "Searching for the next best mate"である. Todd が 詳 細 に 検 討 したのは, 彼 が the Take the Next Best (TNB) mate-choice rule family と 名 づ けたルール 群 である. 37%ルール とよく 似 てい るが, 特 に 37 という 数 字 にこだわるものではない. このルールでは 最 初 の,ある 特 定 の C%( 母 数 N の うち)の 女 性 は 持 参 金 額 を 聞 くだけにしておく.た だし,その 中 で 最 高 の 持 参 金 額 D を 憶 えておく. 次 に,C%を 過 ぎた 女 性 から, 持 参 金 を 聞 く 作 業 を 再 1 持 参 金 額 の 期 待 値 を 最 大 化 することが 目 的 なら,やや 複 雑 とな るが,Quine & Law (1996)の 以 下 のアルゴリズムがある.C = 33 で 58%の 女 性 までは 通 常 の TNB ルールを 適 用,58%を 超 え 78% まではそれまでの 一 番 か 二 番 を,それ 以 降 は 三 番 以 上 を 選 択 する. 開 して, 最 初 に D を 超 えた 女 性 を 選 ぶ"Take the next best mate"というものだ. 37%ルール はこ の TNB ルール 群 の 特 殊 形 という 言 い 方 もできる. ただし,この TNB では,C%を 過 ぎた 女 性 の 中 に 結 局 D を 超 えた 女 性 がいなかった 場 合,とにかく 最 後 の 女 性 を 選 ばなければならないという 掟 がある. Todd は 上 記 の C%を 0%から 90%まで 変 動 させ, 一 つ 一 つのルールに 対 して,ランダムに 生 成 した 10000 組 の 持 参 金 の 数 列 についてシミュレーショ ンを 行 い,その 平 均 値 を 求 めている. 下 図 が Todd の 数 値 実 験 を Excel で 再 現 してみせ た 結 果 である.(ただしこの 場 合 は,N = 100 のケ ースを 1000 回 シミュレーションした 結 果 の 平 均 値 である) Percent of mates in each category 100 90 80 70 60 50 40 30 20 10 0 Top 10% Top 1 Top 25% Bottom 25% 0 20 40 60 80 100 Number of possibilities checked 図 は 横 軸 が C%で, 縦 軸 がその TNB ルールで 目 標 としていた 女 性 ( 持 参 金 )を 選 べた 確 率 を 示 して いる. 図 からわかるように 一 番 (Top 1) 持 参 金 の 大 きな 女 性 を 選 ぶためにはやはり 37%ルール が 最 も 有 効 である.C = 37 で 確 率 は 最 大 の 37%とな る. しかし 目 標 を 緩 和 して,10 番 以 内 (Top 10%)の 女 性 ( 持 参 金 )を 選 ぶとすると C = 12(12 人 )で 確 率 は 最 高 の 77%となる.さらに 目 標 を 緩 和 して 25 番 以 内 (Top 25%)とすると,わずか C = 8(8 人 )で,しかも 90%の 確 率 で 目 標 を 達 成 できる.C の 値 が 小 さいことは,75 番 以 下 (Bottom 25%)の 女 性 ( 持 参 金 )を 選 ぶ 確 率 も 低 くなることからも 有 利 (より 低 リスク)である. また 次 の 図 は 横 軸 が C%で, 縦 軸 がその TNB ル ールで 選 んだ 持 参 金 ( 女 性 )の 平 均 値 (1-100), すなわち 期 待 値 を 示 している. 図 に 示 されるように 持 参 期 待 値 は C = 8 で 最 高 の 89 となる.これは C = 37 37%ルール の 期 待 値 74 を 遥 かに 上 回 る 数 値 である. Todd は N = 1000 のケースについても 同 様 の 検 討 を 行 なっており,その 結 果,C = 3(30 人 )で 10-27 -
番 以 内 の 女 性 ( 持 参 金 )を 95%の 確 率 で,C = 1(10 人 )で 25 番 以 内 を 98%の 確 率 で 選 べることを 見 い だしている(ただし Top 1 の 選 択 では 37%ルール が 最 良 となることは 同 じである.)ちなみに 期 待 値 の 最 高 も C = 3(30 人 )であった. すなわち N = 100 から 1000 の 範 囲 であれば,N に 対 する 割 合 というよりも,とりあえず 絶 対 値 とし て 最 初 の 12 人 くらいの 女 性 の 持 参 金 を 調 べて, 続 いて 現 れる 最 高 の 持 参 金 額 の 女 性 を 選 べば,そこそ この 結 果 は 期 待 できるということである. Average mate value 100 80 60 40 20 0 0 20 40 60 80 100 Number of possibilities checked 参 考 のために 上 記 シミュレーションを 行 なうた めの VBA プログラムを 以 下 に 示 す. 詳 細 は 割 愛 す るが,このプログラムは 次 のような 操 作 を 行 なって いる. 1) 1 から 100(Trial_No)の 値 ( 持 参 金 )をランダ ムに 並 び 替 えた 数 列 を 1000(Simu_No) 組 生 成 し,Mate(Simu_No, Trial_No)の 2 次 元 マトリ ックスに 収 納 すると 同 時 に Sheet3 に 打 ち 出 す. 2) C = 0 から 90 の TNB ルールを 上 記 Simu_No 組 の 数 列 に 適 用,その 結 果 選 ばれた 値 ( 持 参 金 ) と,その 値 が Top 1,Top 10%,Top 25%,Bottom 25%のいずれとなるかを 評 価,その 平 均 値 を Sheet1 に 打 ち 出 す. 3) Sheet1 の 結 果 をグラフ 化 すれば 先 の 2 つの 図 と なる. Sub TNB() Dim i, j, k, l As Integer Dim Top1, dtop1 As Integer Dim ctop25, ctop10, ctop1, cbottom25 As Single Dim Average_Value As Single Const Simu_No = 1000 Const Trial_No = 100 Dim Mate(Simu_No, Trial_No) As Variant Dim dmate(trial_no) As Integer Dim Rand(Trial_No), Dummy As Single Worksheets("Sheet3").Cells(1, 1 + i) = i For k = 1 To Simu_No Rand(i) = Rnd Mate(k, i) = 0 dmate(i) = 0 Worksheets("Sheet3").Cells(1 + k, 1) = k Dummy = 0 Mate(k, i) = 1 For j = 1 To Trial_No If dmate(j) = 0 And Rand(j) > Dummy Then Dummy = Rand(j) Mate(k, i) = j Next j dmate(mate(k, i)) = i Worksheets("Sheet3").Cells(1 + k, 1 + i) = _ Mate(k, i) Next k Worksheets("Sheet1").Cells(3, 2) = "Top 10%" Worksheets("Sheet1").Cells(3, 3) = "Top 25%" Worksheets("Sheet1").Cells(3, 4) = "Top 1" Worksheets("Sheet1").Cells(3, 5) = "Bottom 25%" Worksheets("Sheet1").Cells(3, 6) = "Average mate value" For l = 0 To 90 ctop10 = 0: ctop25 = 0: ctop1 = 0: cbottom25 = 0 Average_Value = 0 T1: For k = 1 To Simu_No dtop1 = 0: Top1 = Mate(k, Trial_No) If l = 0 Then Top1 = Mate(k, 1) GoTo T1: For i = 1 To l If Mate(k, i) > dtop1 Then dtop1 = Mate(k, i) For i = l To Trial_No If Mate(k, i) > dtop1 Then Top1 = Mate(k, i) GoTo T1: If Top1 = 100 Then ctop1 = ctop1 + 1 If Top1 >= 90 Then ctop10 = ctop10 + 1 If Top1 >= 75 Then ctop25 = ctop25 + 1 If Top1 <= 25 Then cbottom25 = cbottom25 + 1 Average_Value = Average_Value + Top1 Next k Worksheets("Sheet1").Cells(4 + l, 1) = l Worksheets("Sheet1").Cells(4 + l, 2) = _ ctop10 / Simu_No * 100 Worksheets("Sheet1").Cells(4 + l, 3) = _ ctop25 / Simu_No * 100 Worksheets("Sheet1").Cells(4 + l, 4) = _ ctop1 / Simu_No * 100 Worksheets("Sheet1").Cells(4 + l, 5) = _ cbottom25 / Simu_No * 100 Worksheets("Sheet1").Cells(4 + l, 6) = _ Average_Value / Simu_No Next l End Sub - 28 -