W_{q} = \frac{ρ}{1 - ρ} S, π_{n} = (1 - ρ) ρ^{n}

シミュレーションで見る

スーパーのレジはなぜ一列に並ぶほうが早いのか

Why a single checkout line is faster

同じ客で待ち時間は18.0分、4.5分、3.9分。並び方しか違わない。

一本の列は、空いたレジの前で客が待つ時間をなくす。ただ、短い列を選ぶ客との差は14%で、会計が1%遅れると消える。等比級数で式を導き、同じ客を3つの店に通して読む。

種類: シミュレーションで見る
公式: 3 本
人物: アグナー・クラルプ・アーラン、デイヴィッド・ケンドール、ジョン・リトル、ジョン・キングマン
作成日: 2026-11-01
更新日: 2026-11-01
執筆・監修: 佐々木航

マルコフ連鎖ネイピア数 e 等比級数(ゼノンのパラドックス)

場面

18.0分、4.5分、3.9分

レジが4台ある店に、1分に平均1.8人の客が来る。会計は1人平均2分かかる。同じ客を同じ順に、並び方だけが違う3つの店に通してみる。

レジごとの列をでたらめに選ぶ店では、会計が始まるまでの平均待ち時間は18.0分だった。いちばん短い列を選ぶ店では4.5分。全員が一本の列に並び、空いたレジへ順に進むフォーク並びの店では3.9分である。

一本の列が早いのは、空いたレジの前で誰も待たないからだ。

教科書でよく比べるのは、18.0分と3.9分である。4.6倍の差になる。けれども、買い物かごを持った人は、列をでたらめに選んだりしない。隣の列を見て、短いほうに並ぶ。その店と一本の列の差は14%、時間にして33秒しかない。しかも一本の列にしたせいで会計が1%遅くなれば、この33秒は消えてしまう。

スーパーのレジは、本当に一列にするべきなのか。答えは、レジがどれだけ埋まっているかで変わる。

考え方

レジが遊び、客が待つ

3つの店で、レジの余裕は同じである。1分に1.8人が来て、1人に2分かかるので、4台のうち平均3.6台が動き、0.4台が空いている。動いている割合0.9を利用率と呼び、 $ρ$ （ロー）と書く。1分に来る客の数を $λ$ （ラムダ）、平均の会計時間を $S$ 、台数を $c$ とすれば $ρ = λ S / c$ だ。

違うのは、空いたレジがどこにあるかである。

客が店に着いた瞬間を調べると、空いたレジがあるのに別の列で誰かが待っていた割合は、でたらめに選ぶ店で34%、短い列を選ぶ店で12%だった。一本の列では、これは起こりようがない。レジが空けば、列の先頭にいる客がそこへ進むからである。

同じ計算で、あとから来た客に先を越された客の割合も数えた。でたらめに選ぶ店で70%、短い列を選ぶ店でも44%にのぼる。隣の列のほうが早く進むように感じるのは、気のせいではなかったわけだ。¹

では、3.6台ぶんの仕事に4台を用意しているのに、なぜ待ち時間は何分にも伸びるのか。原因はばらつきにあり、その効き方は式に書ける。

式

1台の店を等比級数で解く

でたらめに列を選ぶ店から解く。この店は、レジ1台の店を $c$ 個並べたものにあたるからだ。来る間隔と会計時間は指数分布に従うとする。 $μ = 1/ S$ は、1人のレジ係が1分に会計できる客の数である。

時間 $t$ を $n$ 等分する。短い1区間に客が来る確率を $λ t / n$ とすると、次の客までの時間 $T$ が $t$ を超える確率はネイピア数 $e$ の形になる。これが指数分布である。
$P (T > t) = n \to \infty lim (1 - \frac{λ t}{n})^{n} = e^{- λ t}$
すでに $s$ 分来なかったとしても、この先の待ち方は変わらない。指数分布のこの性質を無記憶性という。
$P (T > s + t ∣ T > s) = \frac{e ^{- λ (s + t)}}{e ^{- λ s}} = e^{- λ t}$
会計時間も同じ性質をもつので、次に起きることは今の人数 $n$ だけで決まる。店の人数はマルコフ連鎖である。人数が $n$ から $n + 1$ へ上がる回数と下がる回数は多くても1回しか違わないから、長い目で見て次の釣り合いが立つ。
$λ π_{n} = μ π_{n + 1}$
$ρ = λ / μ$ とおくと、人数 $n$ でいる割合 $π_{n}$ は等比数列になる。
$π_{n} = π_{0} ρ^{n}$
割合を全部足すと1である。等比級数の和を使うと $π_{0}$ が決まる。 $ρ < 1$ が条件だ。
$n = 0 \sum \infty π_{0} ρ^{n} = \frac{π _{0}}{1 - ρ} = 1 \Rightarrow π_{n} = (1 - ρ) ρ^{n}$
店にいる平均の人数 $L$ は、等比級数を $ρ$ で微分して求まる。
$L = n = 0 \sum \infty n (1 - ρ) ρ^{n} = (1 - ρ) ρ \frac{d}{d ρ} \frac{1}{1 - ρ} = \frac{ρ}{1 - ρ}$
リトルの法則で、人数を時間に換える。 $W$ は1人が店にいる平均時間である。
$L = λW \Rightarrow W = \frac{L}{λ} = \frac{S}{1 - ρ}$
会計時間 $S$ を引くと、平均待ち時間になる。
$W_{q} = W - S = \frac{ρ}{1 - ρ} S$

リトルの法則は、図にすると当たり前に見える。横に時間、縦に店の人数をとったグラフの面積は、「客が店で過ごした時間の合計」である。 $D$ 分のあいだに $N$ 人が来たとして、面積を $D$ で割れば $L$ 、 $N$ で割れば $W$ になり、 $N / D$ が $λ$ なので $L = λW$ が出る。客の来方も会計時間の分布も問わない。

手順7の $1/ (1 - ρ)$ が、この話の芯である。利用率が0.5なら店にいる時間は会計の2倍で済むが、0.8で5倍、0.9で10倍、0.95で20倍、0.99で100倍になる。 $ρ \geq 1$ では釣り合いが成り立たず、列は伸び続ける。

冒頭の18.0分は手順8の式で出る。来る客をでたらめに4つに分けても、それぞれの間隔は指数分布のままで、1台あたり1分に0.45人が来る。利用率は0.9のまま変わらず、 $W_{q} = 0.9/0.1 \times 2 = 18$ 分になる。台数を8台に増やして客も倍にしても18分のままで、でたらめに選ぶ限り、店を大きくした得がない。

丸が今の人数で、隣へ1つずつ移っていく。棒はその滞在の割合を数えたもの、点線の枠が手順5の式である。

式

アーランのC式で余裕を束ねる

一本の列でも、釣り合いの考え方は同じである。違うのは下がる速さで、人数が $n$ なら $min (n, c)$ 台が同時に動く。 $a = λ S$ を、平均で動いているレジの台数とする。

上がる回数と下がる回数の釣り合いを書く。
$λ π_{n} = min (n + 1, c) μ π_{n + 1}$
人数が $c$ までは、1つ上がるごとに $a / n$ 倍になる。
$π_{n} = π_{0} \frac{a ^{n}}{n !} (n \leq c)$
人数が $c$ を超えると、公比 $ρ = a / c$ の等比数列に変わる。
$π_{c + k} = π_{c} ρ^{k}$
レジが全部ふさがっている割合は、等比級数で足せる。来た客が待たされる確率 $C$ がこれにあたり、全体の和で割るとアーランのC式になる。
$C = k = 0 \sum \infty π_{c + k} = \frac{\frac{a ^{c}}{c !} \frac{1}{1 - ρ}}{k = 0 \sum c - 1 \frac{a ^{k}}{k !} + \frac{a ^{c}}{c !} \frac{1}{1 - ρ}}$
待っている人数の平均は、前の章の手順6と同じ計算で求まる。
$L_{q} = k = 0 \sum \infty k π_{c + k} = \frac{C ρ}{1 - ρ}$
$L_{q}$ を $λ$ で割ると、平均待ち時間になる。
$W_{q} = \frac{C S}{c ( 1 - ρ )}$

手で計算できる大きさなので、冒頭の店で解いてみる。 $c = 4$ 、 $a = 3.6$ である。手順4の分母の前半は $1 + 3.6 + 6.48 + 7.776 = 18.856$ 。後半は $a^{4} /4! = 6.9984$ を $1 - ρ = 0.1$ で割って69.984になる。だから $C = 69.984/88.84 \approx 0.788$ で、 $W_{q} = 0.788 \times 2/ (4 \times 0.1) \approx 3.94$ 分。これが3.9分の出どころだ。

4.6倍の正体は、待ち時間の分布で裾を見ると分かる。列の人数が等比数列なので、待たされた客の待ち時間は指数分布になり、次の形に書ける。

P (W_{q} > t) = C e^{- (c μ - λ) t}

肩に乗った $c μ - λ$ は、1分あたりの余裕である。でたらめに選ぶ店では、レジ1台ごとに切り分けられた余裕 $0.5 - 0.45 = 0.05$ 人しか使えない。一本の列なら、4台ぶんを束ねた $2 - 1.8 = 0.2$ 人を使える。

だから、裾は4倍の速さで細る。

10分を超えて待つ客は55%から11%に、20分を超えて待つ客は33%から1.4%に減る。平均の差より、長く待たされる人の減り方のほうがはるかに大きい。

シミュレーション

ρが0.9を超えるところを見る

同じ客を3つの店に同時に通している。店の絵では四角がレジ、丸が客で、空いたレジの前で誰かが待っていると枠が脈打つ。棒グラフは待ち時間の分布で、左端の斜線の棒は待たずに済んだ客、右端の斜線の棒は目盛りの外まで待った客、三角が平均である。乱数の種を固定しているので、つまみが同じなら平均の数字も同じになる。

客の来る速さを1.6人から1.9人へ、2割足らず増やしてみる。一本の列は式の値で平均1.5分から8.9分へ、6倍に伸びる。「ばらつき」を「間隔も会計時間も一定」にすると、利用率0.9でも短い列と一本の列の待ち時間は0になる。待ち行列を作っているのは客の多さよりも、ばらつきのほうだと分かる。「10人に1人が大きなかご」は、11分の客が1割で残りが1分という店である。会計の平均は2分のままなのに、待ち時間はそれぞれ30.9分、7.3分、6.6分に伸びる。

考え方

短い列を選ぶ店に式はない

実際の店にいちばん近いのは2番目の店だが、この店の待ち時間には厳密な式がない。

レジが2台の場合は、1961年にジョン・キングマンが解いた。3台以上は近似の式と数値計算に頼るしかないと、グプタらの2007年の論文がまとめている。1977年にウェイン・ウィンストンは、レジの速さが同じで会計時間が指数分布に従い、列を移れないなら、会計を終えた客の数で測って短い列に並ぶのが最良だと示した。ただ、会計時間のばらつきがもっと大きいと、最良からは遠くなることも知られている。

筆者が計算すると、4台で利用率0.9の平均は4.48分になった。²一本の列との比は、台数が多いほど、また空いているほど大きくなる。

利用率0.9のとき、2台で1.05倍、4台で1.14倍、8台で1.29倍
4台のとき、利用率0.5で1.8倍、0.8で1.3倍、0.9で1.14倍、0.95で1.07倍

もっとも、利用率0.5の1.8倍は0.32分と0.17分の差で、9秒しか違わない。

残りの差はどこから来るのか。

客に見えるのが人数だけだからである。全員が、どの列も残りの会計が何分かを見通して、いちばん早く空くレジの列に並ぶとしたらどうなるか。一本の列では、先頭の客が最初に空いたレジへ進む。見通せる客は同じレジを、並ぶ時点で選んでいるだけである。来た順に同じレジが割り当てられるので、どの客の待ち時間も、一本の列とぴたりと一致する。つまり4.5分と3.9分の差の33秒は、前の人のかごの中身が分からないことの代金だと言ってよい。

意外なことに、待たずに会計へ進める客は、短い列の店のほうが多い。一本の列では21%、短い列では25%になる。空いたレジと待つ客が同時にいる時間が残るぶん、来た瞬間に空きを見つけられる客が増えるからだろう。それでも、平均と裾の細さでは一本の列が勝つ。20分を超えて待つ客は、短い列で2.5%、一本の列で1.4%だった。

図

点線が破線を追い越す

利用率と平均待ち時間のグラフ。4台の店で、でたらめに選ぶ曲線が最も上にあり、短い列を選ぶ曲線と一本の列の曲線はほとんど重なる。一本の列で会計が6.86%遅いと、利用率0.68あたりから短い列より悪くなり、0.9では12.8分に達する。

太い実線と破線の隙間は、どの利用率でもわずかである。6.86%遅い一本の列を表す点線は、利用率0.68までその隙間を通り、そこから破線を追い越して跳ね上がる。

考え方

6.86%の重さ

ここまでの計算には、一本の列でもレジ係の速さは変わらないという仮定があった。実際の店では、そうならなかった例がある。

ワンとジョウは、スーパーで起きた自然実験を2018年に報告している。列の長さの影響を除いて比べると、自分の列を持つレジ係は、列を共有するレジ係より約10.7%速かった。研究者は主な原因を社会的手抜きとみている。仕事を何人かで分け合うと、1人あたりの力を抜きがちになる現象である。列の長さを通じた影響も合わせると、列を共有したときの会計時間は6.86%長くなっていた。

この6.86%を、冒頭の店に当てはめてみる。抄録に店の利用率は書かれていないので、あくまで筆者の試算である。会計が2.14分になると、利用率は0.9から0.962へ上がる。 $1/ (1 - ρ)$ の急なところを登るので、一本の列の待ち時間は3.9分から12.8分へ跳ね上がり、短い列を選ぶ店の4.5分を大きく超える。

短い列の店と待ち時間が並ぶまでに許される遅れは、利用率が高いほど小さい。

利用率0.5なら13%、2分の会計で16秒
利用率0.7なら6%、7秒
利用率0.9なら1%、1.2秒

混んでいるときほど一本の列が得だと思いがちだが、混んでいるときほど遅れに弱い。しかも、遅くなった会計そのものも客の時間である。待ち時間に会計時間を足して比べると、4台の店では、分かれ目は調べた利用率0.3から0.95のあいだで最大でも5.3%ほどだった。この計算の中に、6.86%の遅れを取り戻せる場面はない。

歩く時間も同じように効く。列の先頭からレジまで6秒かかるとすれば、その間レジは空いたままなので、会計が0.1分延びたのと同じことになる。利用率は0.945になり、筆者の計算で待ち時間は約8分に伸びる。柳澤大地らは2008年の論文で、この歩行距離を待ち行列理論に組み込んだ。その解析では、非常に混雑している場合や、歩行時間に対してサービス時間が短い場合には、窓口ごとに並ぶ「並列型」のほうが一本にまとめる「フォーク型」より効率がよくなる。論文はこれを「今までの待ち行列理論ではなかった結果」と書いている。

さらに、客の側の反応もある。ルーらは2013年、小売店の映像と売上のデータから、客は列の長さをよく見ていて、列の進む速さを十分に考慮しないことを見いだした。列を1本に集めると見た目の列が長くなり、売上が下がるおそれがあるという。

歴史

電話会社の計算から店の実験まで

待ち行列の数学は、電話会社で生まれた。1908年、デンマークのアグナー・クラルプ・アーランは、コペンハーゲン電話会社に入って新設の物理技術研究室を率いた。数学協会の集まりで知り合った主任技師ヨハン・イェンセンが、電話の待ち時間という問題に取り組むよう説得したという。アーランは1909年の最初の論文で、でたらめにかかる電話がポアソン分布に従うことを示した。1917年には損失と待ち時間の式を発表し、イギリスの郵政省をはじめ各国の電話会社が使うようになった。MacTutorの伝記によると、会社にいた約20年のあいだ、病気で休んだ日は一度もなかった。1929年1月に腹痛で入院して手術を受け、数日後に51歳で亡くなった。

1953年、デイヴィッド・ケンドールは、待ち行列を「埋め込みマルコフ連鎖」で解析する論文を書いた。来る間隔、会計時間、台数を並べるM/M/cのような書き方も、この論文が元とされる。Mはマルコフの頭文字で、無記憶性を指す。1961年には、クリーブランドのケース工科大学にいたジョン・リトルが、定常で平均が有限という条件のもとで $L = λW$ を5ページの論文で証明した。

「一本がよい」という通説に正面から異議が出たのは、1987年のことだ。Operations Researchの同じ号に、2本の論考が並んだ。マイケル・ロスコフとポール・レックの題は「列をまとめるのがいつも得とは限らない」である。客の反応、列の移動、費用とサービス時間の増加を理由に挙げ、まとめる前と後を比べた公表例がないことも指摘した。リチャード・ラーソンは、客を怒らせるのは待つ長さだけでなく、先に来た人が先に呼ばれないという不公平でもあると論じた。先の44%は、この模型で測った不公平の大きさにあたる。

指摘を裏づけるデータは、その後に出てきた。ワンとジョウの自然実験に加え、シュンコらの2018年の行動実験でも、一本の列は作業者を遅くした。ソンらが2015年に報告した救急部門の分析では、患者を医師ごとに割り当てる方式で、対照群と比べて滞在時間が17%、待ち時間が9%短くなった。列を自分のものと感じるかどうかが、数式の外で効いているようだ。

使いどころ

まず10分、店で数える

一本の列にするかどうかは、利用率を数えれば、かなり絞り込める。

店で10分間、来た客の数を数えて10で割る。これが $λ$ である。
会計を20人ほど測り、平均を $S$ とする。開いているレジの台数 $c$ と合わせて、 $ρ = λ S / c$ を計算する。10分で18人、2分、4台なら0.9だ。
0.9に近いなら、並び方より先にレジを開ける。冒頭の店を5台にすると利用率は0.72になり、平均待ち時間は一本の列で0.59分、短い列でも0.89分まで減る。3分以上も縮むので、並び方を変えて得られる33秒とは大きさが違う。
一本の列を試すなら、会計時間も一緒に測る。先頭の客をレジの近くで待たせ、歩く時間を縮めると、遅れの一部は取り戻せるはずだ。

買い物客のほうは、もう答えを持っている。18.0分を4.5分まで縮めているのは、みんなが短い列を選ぶという当たり前の習慣である。残りは、全員がかごの中身まで見通しても33秒しか縮まらない。

シミュレーションで一本の列の遅れを「1%遅い」「3%遅い」と切り替えると、短い列の平均に並び、追い越すところが見える。式の土台はマルコフ連鎖と等比級数の記事に、 $ρ$ がある値を超えると急に流れが悪くなる別の現象は事故も工事もないのに、渋滞はなぜ起きるのかにある。

隣の列に抜かれても、たぶん誰も悪くない。人数しか見えない客が、それぞれ正しい選び方をした結果が4.5分である。

参考文献

A. K. Erlangの経歴と論文はJ. J. O'Connor, E. F. Robertson, "Agner Krarup Erlang", MacTutor History of Mathematics（セント・アンドルーズ大学）による。
W. Whitt, "Homework 1e. Solutions for the Erlang B and C Formulas", IEOR 6707（コロンビア大学、2002年）.
D. G. Kendall, "Stochastic Processes Occurring in the Theory of Queues and their Analysis by the Method of the Imbedded Markov Chain", The Annals of Mathematical Statistics 24 (1953), 338-354.
J. D. C. Little, "A Proof for the Queuing Formula: L = λW", Operations Research 9 (1961), 383-387.
J. F. C. Kingman, "Two Similar Queues in Parallel", The Annals of Mathematical Statistics 32 (1961), 1314-1323.
W. Winston, "Optimality of the shortest line discipline", Journal of Applied Probability 14 (1977), 181-189.
M. H. Rothkopf, P. Rech, "Perspectives on Queues: Combining Queues is Not Always Beneficial", Operations Research 35 (1987), 906-909.
R. C. Larson, "Perspectives on Queues: Social Justice and the Psychology of Queueing", Operations Research 35 (1987), 895-905.
V. Gupta, M. Harchol-Balter, K. Sigman, W. Whitt, "Analysis of join-the-shortest-queue routing for web server farms", Performance Evaluation 64 (2007), 1062-1081.
柳澤大地、友枝明保、木村紋子、西成活裕「歩行距離を考慮した待ち行列理論による待ち行列システムの解析」『日本応用数理学会論文誌』18巻4号（2008年）, 507-534.
Y. Lu, A. Musalem, M. Olivares, A. Schilkrut, "Measuring the Effect of Queues on Customer Purchases", Management Science 59 (2013), 1743-1763.
H. Song, A. L. Tucker, K. L. Murrell, "The Diseconomies of Queue Pooling: An Empirical Investigation of Emergency Department Length of Stay", Management Science 61 (2015), 3032-3053.
M. Shunko, J. Niederhoff, Y. Rosokha, "Humans Are Not Machines: The Behavioral Impact of Queueing Design on Service Time", Management Science 64 (2018), 453-473.
J. Wang, Y.-P. Zhou, "Impact of Queue Configuration on Service Time: Evidence from a Supermarket", Management Science 64 (2018), 3055-3075.

注

同じ客を200万人通した計算で、初めの5万人を除いて数えた（別の実装と別の乱数でも44%）。先を越されたとは、あとから来た客のうち誰かが先に会計を始めたこと。客は一度並んだ列を変えない。 ↩
種を変えて400万人ずつ5回計算した平均で、標準誤差は0.01分。シミュレーションは1つの種で98万人を数えた値（4.49分）を出す。「大きなかご」の店は種によるぶれが大きく、約500万人ずつ8回の平均では29.1分、6.9分、6.2分だった。でたらめに選ぶ店の理論値は29.25分である。 ↩