待ち行列理論

ディズニーランドで、銀行のATMで、スーパーのレジで、高速道路の料金所で、我々は行列を作る。これを待ち行列といい、この問題を解くための理論、すなわち待ち時間を計算して求めたりする方法が学問としてある。

この待ち行列理論は経済産業省主宰の国家試験である情報処理技術者試験のテクニカルエンジニア (ネットワーク) の午前の問題として必ず出ることになっている。

その待ち行列の計算だが、教科書には必ず以下の 「公式」 が出てくる。

(待ち行列) ＝ρ x Ts / (1-ρ)

この公式に数字を当てはめれば待ち行列＝待ち時間が出てくるそうである。ここで、待ち行列を理解する上で、以下の HP が参考になった。

https://www.mirai.ne.jp/~suehiro/am/kihonyougo/queuingtheory.htm

教科書にはいきなり公式がでてくるのだが、なぜその公式になるのか詳しく説明されているのがなかったので、今まで頭に入らなかった。しかし

https://www.geocities.co.jp/Technopolis-Mars/5427/mathtrtop.html

を見てその理由がわかった。高校以上の数学を駆使しないと公式が導き出せないのである。数列と微分を駆使する。私は高校時代、微積分をとっていていつもテストはクラスで3番くらい (1番は京大受かった石垣君、2 番は友だちの青木君、3 番目は私) だったが、lim なんてのは15年前の話だから、もうとっくに忘れた。が、最初から情報処理技術者試験の参考書も 「この公式は数列と微分を使って導き出すことができるものです」 と、ひとこと書いてくれたら良かったのに。いや、つまりすぐに公式を理解することをあきらめて、ただひたすら暗記に徹することができたのに、ということ。参考書は誰にでもわかるようにと中途半端な説明するから余計にわからなくなる。

閑話休題、上の公式のρ (ローと読む) とはなんぞや？実は私はその謎が解けてから行列問題が解けるようになった。

実際に問題を解いてみよう。

(H11ネットワークスペシャリスト午前問 63)

まず上の公式で、ρを求める。ρの求め方は、ズバリ、

という比率を求めるのである。この比率をρと言っている。この考え方に気付いてから行列問題が簡単に思えるようになった (この道のりの長かったこと) 。

つまり、問題によれば 1 人当たり 3 分間隔で ATM を操作しているとすれば、1 時間で 20 人さばけるはずである。1 時間＝ 60 分を 3 分で割れば20だから、つまり 1 時間以内に絶え間なく 20 回 ATM を操作できる。問題の中には、12～13 時の 1 時間の間に 15 人が続々来る、ということだから、この ATM はどれだけ働いてるかというと、

(来客数 15 回) : (本来さばける回数は 20 回) ＝ ρ : 100 (%)

と、比の計算で求められる。これなら小学校の高学年で出てくる算数で解ける。私が今まで見た中で、こういう解き方を書いている参考書はひとつもなかった。参考書の筆者はきっと頭がよく、プライドもあるだろうからこういう書き方は決してしないのだろう。するとρは75%である。つまりこの ATM はお昼時に本来の能力を 100% とすると 75% の力しか発揮していない、ということである。

ここで、勉強していてわかったのだが、この公式ではATMの処理能力を超えて来客することはない、という前提である。現実には高速道路の料金所やディズニーランドの人気アトラクションはそんなことはなく常にフル稼働なので、M/M/1という待ち行列のモデル (前提条件) は非常に甘々であることがわかる。しかし前提条件を甘くしても微分は出てくるのである。実際の社会で起こっている待ち行列問題を解くのは 「すごく難しい」 のであった。高速道路の渋滞がなぜ起こるのか、それは待ち行列理論をきちんと理解して道路/トラフィック設計してないからではないか？と、勘ぐりたくさえなる (もちろん考えて設計していると思うのだが、だとすればETC専用レーンを設けるなんてもってのほかだと思うのだが…？？？) 。

またまた閑話休題、上の公式の Ts は 「平均サービス時間」 と呼ばれ、ここではたとえば ATM にキャッシュカードを入れてから現金を引き出したり残高照会をしたり振り込みをしたりし終えるまでの時間のことを言っている。問題文中からこれは 3 分である。

これでρ＝75%、Ts＝3 (分) となるので、公式にあてはめてみればよい。

(待ち時間) ＝0.75 × 3 (分) / (1 - 0.75) ＝ 9 (分)

ということで、昼休みにこの ATM を使う客の待ち時間は9分であることがわかった。

試験に限って言えば問題のパターンは決まっているのでコツをつかんでしまえば簡単な問題だったのだ。

* * *

※M/M/1の意味は、

であるが、 5. のポアソン分布なんかは大学で習った統計学出てきたものだし、はっきりいって未だよく理解してないが、わからなくてもなんとかなる。