待ち行列理論によるコールセンターのモデル化 (1/3) (original) (raw)

はじめに

待ち行列理論とは、オペレーションズ・リサーチにおける分野の一つで、コールセンターやサーバー等の応答性能を評価する際に代表的に使われる方法論である。

今回は、待ち行列理論を使ってコールセンターをモデル化する方法を調査したので、その理論と分析方法の実践を3回にわたって解説したい。

一般的な待ち行列理論

コールセンターのモデルは、4つの変数で特徴づけられる。ここでは、次の設定を考えてみよう。

入電時刻：単位時間あたり $λ$ 回、(ポアソン過程に従って)ランダムにかけてくる
応答時間：平均 $T_s$ の指数分布に従う
担当者の数： $C$
回線数： $N$

（当然だが、回線数よりも担当者が多いと意味がないので、 $C \leq N$ である。）

以下の例では、担当者が2人・回線数が3人であり、3回目の入電があったタイミングでは、1人目の担当者がまだ対応中であるため、対応できるようになるまで待ち時間（保留）が発生する。

待ち行列理論を用いることで、この待ち時間の平均的な長さや、応答率（入電したタイミングで一発で担当者に繋がる確率）といったサービスレベルを定量的に評価することができるのだ。

この設定は、M/M/C/N システム*1と呼ばれ、出生死滅過程(Birth-Death Process) という確率過程を使ってモデル化できる。

この図は、M/M/C/N システムによって記述される、コールセンター内の人数の単位時間あたりの推移を模式的に示したものだ。

上側の矢印は、単位時間あたり $λ$ 回の入電があり、その度にコールセンター内の人数が1人増えることを意味している。

下側の矢印は、担当者が対応完了することで、コールセンター内の人数が1人減ることを示している。ここで、単位時間あたりの減少人数 $μ_n$ を場合分けして計算してみよう。

コールセンター内の人数が担当者の数を超えていない場合 ( $n \le C$ )
コールセンター内の人数が担当者の数を超えている場合 ( $n \gt C$ )

さて、ある時刻 $t$ のコールセンター内の人数が $n$ 人である確率を $p_n(t)$ として、区間 $(t, t+Δt$ ] に着目してこの状況を方程式で表してみよう。

$p_0(t+Δt) = p_0(t)(1-\lambda_0Δt) + p_1(t)\mu_1Δt + o(Δt)$

$p_n(t+Δt) = p_{n-1}(t)\lambda_{n-1}Δt + p_n(t)(1-\lambda_nΔt-\mu_nΔt) + p_{n+1}(t)\mu_{n+1}Δt + o(Δt)$ ( $1\leq n \leq N-1$ )

$p_N(t+Δt) = p_{N-1}(t)\lambda_{N-1}Δt + p_N(t)(1-\mu_NΔt) + o(Δt)$

一番目の式について、時刻 $t+Δt$ において状態が $n=0$ の確率は、次の2つに場合分けできる。

時刻 $t$ において $n=0$ であり、かつ $(t, t+Δt$ ]の間に誰も到着しない確率
→ $p_0(t)(1-\lambda_0Δt)$
時刻 $t$ において $n=1$ であり、かつ $(t, t+Δt$ ]の間にサービスが完了する確率
→ $p_1(t)\mu_1Δt$

残りの2つの式についても、同じ考え方で定式化できる。

これらの式について $Δt→0$ の極限を取り、 $\lim_{t→0}\frac{p_n(t+Δt)-p_n(t)}{Δt} = \frac{dp_n(t)}{dt}$ に注意して微分形式で表すと、

$\frac{dp_0(t)}{dt} = -p_0(t)\lambda_0 + p_1(t)\mu_1$

$\frac{dp_n(t)}{dt} = p_{n-1}(t)\lambda_{n-1} - p_n(t)(\lambda_n+\mu_n) + p_{n+1}(t)\mu_{n+1}$ ( $1\leq n \leq N-1$ )

$\frac{dp_N(t)}{dt} = p_{N-1}(t)\lambda_{N-1} - p_N(t)\mu_N$

となる。

ここで、システムが定常（stationary）であると仮定する。すなわち、 $p_n(t)$ は時間に依存せず、定数 $p_n$ として表せるとする。すると、時間変化は0になるため、左辺が $0$ となり、以下のように整理できる。

$0 = -p_0\lambda_0 + p_1\mu_1$

$0 = p_{n-1}\lambda_{n-1} - p_n(\lambda_n+\mu_n) + p_{n+1}\mu_{n+1}$ ( $1\leq n \leq N-1$ )

$0 = p_{N-1}\lambda_{N-1} - p_N\mu_N$

ここで、これらの式を全ての $n$ について足し合わせると、

$p_{n-1}\lambda_{n-1} = p_n\mu_n$

のように単純化できる。この式は、定常状態における確率の流入フローと流出フローの一致を意味していると解釈できるだろう。

この漸化式を使って、一般項

$p_n = \frac{\lambda_n\lambda_{n-1}\cdots\lambda_0}{\mu_{n-1}\mu_{n-2}\cdots\mu_1}p_0$

を得る。

ここで、確率の正規化条件 $\sum_{n=0}^N p_n = 1$ より、初項は

$p_0 = (\sum_{n=0}^N\frac{\lambda_n\lambda_{n-1}\cdots\lambda_0}{\mu_{n-1}\mu_{n-2}\cdots\mu_1})^{-1}$

と表せる。

さて、今回の設定では

$\lambda_n = \lambda$

$\mu_n = \frac{\min(n, C)}{T_s}$

であったことを思い出し、 $p_n$ を書き直すと、

$p_n = \frac{(\lambda T_s)^n}{n!}p_0$ $(n \le C)$

$p_n = \frac{(\lambda T_s)^n}{C^{n-C}C!}p_0$ $(n \gt C)$

( $p_0 = (\sum_{n=0}^{C-1} \frac{(\lambda T_s)^n}{n!} + \sum_{n=C}^{N} \frac{(\lambda T_s)^n}{C^{n-C}C!})^{-1}$ )

が得られる。

コールセンターへの適応例

さて、先ほど導出した離散確率分布 $p_n$ を用いて、コールセンターの設計で考慮すべき様々なKPIを導出できる。

呼損率

$n = N$ のとき、コールセンターの回線は満杯であるため、このタイミングで架電しても繋がらない。

そこで、 $p_N$ をコールセンターが満杯の確率 = 繋がらない確率 = 呼損率として定義しよう。

$p_N = \frac{(\lambda T_s)^N}{C^{N-C}C!}p_0$

待ち時間

たとえコールセンターにつながったとしても、即座に担当者が応答するとは限られず、待たされる場合もある。そこで、待ち時間 $T_w$ の確率分布を考えよう。

$T_w \lt t$ となる確率は、

$P(T_w \gt t) = \sum_{n=C}^{N-1} P(T_w \gt t | n) P(n | n \lt N)$

と分解できる。

これは、コールセンターに繋がった ( $n \lt N$ ) という条件のもとで、 $t$ 以上待たされる確率を、コールセンター内の人数 $n$ 別に足し上げたものである。

$P(n | n \lt N) = \frac{P(n, n \lt N)}{P(n \lt N)} = \frac{P(n)}{P(n \lt N)} = \frac{p_n}{1 - p_N}$

であり、またサービスの応答時間は指数分布に従うことから、

$P(T_w \gt t | n) = \sum_{i=0}^{n-C} \frac{(\frac{Ct}{T_s})^i}{i!}\exp(-\frac{Ct}{T_s})$

とかける。

（待ち時間が時刻 $t$ 以上 = 時刻 $t$ 以内に処理される人数が $n-C$ 人以下 = 時刻 $t$ 以内に0人処理 + 1人処理 + ... + $n-C$ 人処理と考えるとよい）

よって、

$P(T_w \le t) = 1-P(T_w \gt t) = 1-\sum_{n=C}^{N-1} \sum_{i=0}^{n-C} \frac{p_n}{1 - p_N} \frac{(\frac{Ct}{T_s})^i}{i!}\exp(-\frac{Ct}{T_s})$

という累積分布関数を得る。*2

この数式を使うことで、「応答時間80/20のルール (20秒以内に担当者につながる確率が80%以上) のような一定のサービスレベルを担保するためには、担当者の人数 $n$ を何人以上にしたらよいか？」といった設計上の問題に答えることできる。

また、期待値と累積分布関数の関係から、待ち時間の期待値を求めることができる。

$E(T_w) = \int_{t=0}^{\infty}(1-P(T_w \le t))dt = \int_{t=0}^{\infty}P(T_w \gt t)dt$

この積分は次の式に帰着されるが、これはガンマ分布の定義に基づき、 $i+1$ 階のガンマ関数と考えて求積する。

$\int_{t=0}^{\infty}\frac{(\frac{Ct}{T_s})^i}{i!}\exp(-\frac{Ct}{T_s})dt = \frac{T_s}{C}$

以上より、待ち時間の期待値について

$E(T_w) = \sum_{n=C}^{N-1}\frac{p_n}{1-p_N}\frac{T_s}{C}(n-C+1)$

を得る。（ $p_n$ を書き下すと更に煩雑になるため、これ以上の展開はしない。）

一発で担当者につながる確率

先ほど導いた累積分布関数で $t=0$ と代入することで、待ち時間が $0$ 以下、つまり「待たされない確率 = 一発で担当者に繋がる確率」を求めることができる。

$P(T_w = 0) = 1-P(T_w \gt 0) = 1-\sum_{n=C}^{N-1} \frac{p_n}{1 - p_N}=\sum_{n=0}^{C-1} \frac{p_n}{1 - p_N}$

考えてみれば当たり前だが、これはコールセンターに入れたという条件( $n \lt N$ )のもとで、コールセンター内の人数が担当者の数より少なく( $n \lt C$ )、担当者が余っている確率と等しい。

次回は、これらのKPIをより簡略した設定で具体的に計算してみる。また、実データを用いた解析も予定している。

data-shark.hatenablog.com