【待ち行列｜M/M/1モデル】５つの定理の証明方法と物流への適用事例
物流業界にこそ有用な「待ち行列理論」
管理人は製造業界から物流業界に転職しましたが、当初は物流業界の生産性の低さに衝撃を受けました。
製造業では、あらかじめ決まった製品を生産するため、生産機器の能力や作業者の人数を無駄なく設計できます。
また、生産計画も前もって決められているため、作業シフトも無駄なく組めます。
ところが物流業では、これらの条件が両方とも満たせないことがほとんどです。
メーカー系の物流会社であれば、取り扱う製品の種類が限定されるためまだマシですが、流通業界では取り扱いSKUは膨大な数になりますし、消費者向けの物流においては荷姿の種類は無限です。
荷姿により作業効率が異なることは容易に想像できますね。
また、数日または数週間前から生産量が決まっているメーカーと違い、物流ではその日にならないと物量が決まらないことがほとんどです。
そのため、過去データに基づく予測が重要になります。
この予測に「待ち行列理論」は大きな効力を発揮します。
もともと病院やコールセンター等での窓口の数を合理的に決める目的で使われることが多いのですが、物流センターの設計や作業員数の計画等、物流でも広く適用可能です。
そこで、まずは基本となるM/M/1モデルについて見ていきましょう。
M/M/1モデルとは？
簡単にいうと、窓口が一つしかない行列のモデルです。
M/M/1の最後の１が窓口の数を表します。
では残りのM/Mは何かというと、単位時間当たりに行列に加わる人数も、単位時間当たりに窓口で処理する人数もポアソン分布に従うという意味です。
Ｍはマルコフ過程の略で、過去の実績に依らず毎回ランダムな値を取るということですので、ポアソン分布に従うというのと同じ意味と考えて問題ありません。
ポアソン分布については本サイトでも何回か取り上げていますが、ポアソン分布を理解できる記事として最もアクセスの多い記事がこちらです。
このようにポアソン分布に従うと仮定すれば、例えば行列に加わる人数が平均して１分間に２人である場合、
１分間に１人が加わる確率＝２７％
１分間に２人が加わる確率＝２７％
１分間に３人が加わる確率＝１８％
になります。
１つしかない窓口で処理される人数も、同様のポアソン分布に従うと考えます。
この時、
単位時間当たりに行列に加わる人数：λ
単位時間当たりに窓口で処理される人数：μ
利用率（＝μに対するλの割合）：ρ（＝λ／μ）
と定義すると、
M/M/1モデルの行列は次のような性質を持つことが数学的に導かれます。
定理１）系内にいる人数（行列と窓口にいる人数の合計）がｊ人である確率Πjは
Πj＝ρj（１－ρ）
定理２）系内にいる人数の期待値（平均）Lは
L＝ρ／（１－ρ）
定理３）行列に並んでいる人数の期待値（平均）Lqは
Lq＝ρ2／（１－ρ）
定理４）系内に滞在する時間の期待値（平均）Wは
W＝１／（μ―λ）
定理５）行列に滞在する（並ぶ）時間の期待値（平均）Wqは
Wq＝ρ／（μ－λ）
この定理は非常に便利です。
以下、どのようにこの定理が導かれるのかを見ていきます。
微分の知識は一切不要です。
M/M/1モデル定理の証明方法
定理１）系内にいる人数がｊ人である確率
テーマパークへ行って、人気アトラクションに乗ることを想像してみましょう。
朝一で行って、そのアトラクション目がけて走って行けば、並ばずに乗れるかもしれません。
しかし、一般的に朝一から徐々に行列は伸びていき、ある時点からほぼ一定の行列の長さに落ち着くでしょう。
これを定常状態といいます。
そして、定常状態における系内の人数（行列に並んでいる人とアトラクションに乗っている人の合計人数）をjとします。
到着率（単位時間当たりに行列に加わる人数）λと、離脱率（単位時間当たりに行列から離脱する人数＝単位時間当たりにアトラクションで処理される人数）μを合わせて描くと、次のようになります。
定常状態では系内の人数は一定ですので、
j人の状態から離脱する人数＝j人の状態に到着する人数
が成り立つと考えられます。
j人の状態から単位時間当たりに離脱する人数は、j人の状態からj+1人の状態に単位時間当たりに到着する人数とj人の状態からj-1人の状態に単位時間当たりに離脱する人数の和です。
下図でいうと赤字の部分です。
前章で、系内にいる人数（行列と窓口にいる人数の合計）がｊ人である確率はΠjと定義しましたが、これを使うとj人から単位時間当たりに離脱する人数の期待値は
Πjλ＋Πjμ
で計算できます。
同様にj人の状態に流入する人数の期待値は
Πj-1λ＋Πj+1μ
で計算できます。
定常状態ということは流入＝流出ですので、
Πjλ＋Πjμ＝Πj-1λ＋Πj+1μ
が成り立つはずですね。
この漸化式を解くために、０人の状態での流入と流出を考えてみましょう。
この２つが釣り合うはずなので、
Π0λ＝Π1μ
が成り立ちます。
次に１人の状態での流入と流出を考えましょう。
Π1λ＋Π1μ＝Π0λ＋Π2μ
が成り立つはずです。
この式を前の式も使って変形すると、Π2を求める式は
Π2＝Π0λ2／μ2
となります。
そして、これをΠjを求める式にまで一般化すると、
Πj＝Π0λj／μj
＝Π0ρj
となることが容易に導けます。
ここで、
Π0＋Π1＋Π2＋・・・＝１
であることに注意すると、
Π0＋Π0ρ＋Π0ρ2＋・・・＝１
つまり、
Π0（１＋ρ＋ρ2＋・・・）＝１
と書けます。
ここでカッコの中の式を
S＝１＋ρ＋ρ2＋・・・
と定義します。
この両辺にρを掛けると、
ρS＝ρ＋ρ2＋ρ3＋・・・
となりますが、この式を前式から引くと
S－ρS＝1
となり、更に変形すると
S＝１／（１－ρ）
となります。
つまり、
Π0（１＋ρ＋ρ2＋・・・）＝１
は
Π0×１／（１－ρ）＝１
すなわち、
Π0＝１－ρ
となることが導けます。
従って
Πj＝Π0ρj
ですので、
Πj＝ρj（１－ρ）
であることが導けました。
定理２）系内にいる人数の期待値
次に系内にいる人数の期待値がL＝ρ／（１－ρ）で計算できることを証明します。
これは、
系内の人数が０人である確率×０＋系内の人数が１人である確率×１＋系内の人数が２人である確率×２＋・・・
で計算できます。
系内の人数がj人である確率が
Πj＝ρj（１－ρ）
ですので、
L＝Π0×０＋Π1×１＋Π2×２＋・・・
＝（１－ρ）×０＋ρ（１－ρ）×１＋ρ2（１－ρ）×２＋・・・
＝（１－ρ）（ρ＋２ρ2＋３ρ3＋・・・）
と書けます。
ここで
ｚ＝ρ＋２ρ2＋３ρ3＋・・・
と置きます。
この両辺にρを掛けると、
ρｚ＝ρ2＋２ρ3＋３ρ4＋・・・
となります。
この式を前式から引くと、
ｚ―ρｚ＝ρ＋ρ2＋ρ3＋・・・
変形すると、
ｚ（１－ρ）＝１／（１－ρ）―１＝ρ／（１－ρ）
つまり、
ｚ＝ρ／（１－ρ）2
となります。
このｚをＬを求める式に戻すと、
Ｌ＝（１－ρ）ｚ
＝（１－ρ）ρ／（１－ρ）2
＝ρ／（１－ρ）
となります。
定理３）行列にいる人数の期待値
Lは系内にいる人数の期待値ですが。Lqは行列に並んでいる人数の期待値です。
M/M/1モデルでは窓口が１つしかない想定ですので、系内にいる人数がj人なら、行列に並んでいる人数はj-1人です。
なぜなら、j人のうち1人は窓口にいるからです。
従って、行列にいる人数の期待値Lqは次のように計算できます。
Lq＝Π1×（１－１）＋Π2×（２－１）＋Π3×（３－１）＋・・・
＝Π1×１＋Π2×２＋Π3×３＋・・・－Π1－Π2－Π3－・・・
＝L－（１－Π0）
＝ρ／（１－ρ）－（１－１＋ρ）
＝ρ2／（１－ρ）
定理４）系内に滞在する時間の期待値
Wとは系内に滞在する時間の期待値（平均）のことです。
これを計算するには、リトルの法則を使います。
この法則によると
W＝L／λ
ですので、
W＝λ／（μ－λ）／λ
＝１／（μ－λ）
であることが簡単に導けます。
定理５）行列に滞在する時間の期待値
Wqは行列に滞在する時間の期待値（平均）ですが、これもリトルの法則により次のように簡単に導けます。
Wq＝Lq／λ
＝λ2／μ（μ－λ）／λ
＝λ／μ（μ－λ）
＝ρ／（μ－λ）
M/M/1モデルで荷卸しの待ち時間を求めてみる
物流センターに貨物を納入するトラックの待ち時間はトラック輸送業界にとっては生産性を下げる要因になり、物流センターの近隣住民にとっても迷惑です。
最近ではこれをDXによって変革しようという動きが広がっています。
このトラックの待ち時間を「待ち行列理論」で推定してみましょう。
今回はM/M/1モデルを適用しますので、トラックバースが１か所しかない単純なケースを想定します。
このモデルを適用するために必要な情報はλとμです。
このケースのλとμは次のようになります。
λ：単位時間当たりに到着するトラックの平均台数
μ：単位時間当たりに荷卸しできる平均台数
これらの平均台数を求めるには過去データを使います。
例えば、ある物流センターでは平均して１時間に２台のトラックが到着し、荷卸しは１時間で平均３台分処理できているというデータが得られたとしましょう。
この場合のトラックの平均待ち時間を計算してみます。
トラックが荷卸しするまでの待ち時間ですから、Wqを求めることになります。
Wqを求める公式は
Wq＝ρ／（μ－λ）
でした。
λ＝２、μ＝３、ρ＝λ／μ＝２／３なので、
Wq＝２／３×（３－２）
＝２／３時間
＝４０分
となります。
トラックが２台／時で来るのに対し、荷卸しスピードは３台／時と１.５倍も速いのに、平均４０分も待つことになります。
意外と長いですね。
この待ち時間を減らすには、トラックバースの数を増やすか、トラックの到着率や荷卸しスピードの分散を減らすための改善が必要になります。
ところがトラックバースを増やして複数個所になると、今回もM/M/1モデルでは計算できません。
そのような複数窓口の待ち行列を分析するモデルがM/M/Cモデルです。
Udemyの関連講座
Optimization with Excel: Operations Research without Coding
Optimization with Gurobi, CBC, IPOPT. Linear programming, nonlinear, genetic algorithm. Using Excel, without coding
Assignment and Transportation Problem Operations Research 01
The Hungarian Assignment Problem and Transportation Problem
Optimization with Python: Solve Operations Research Problems
Solve optimization problems with CPLEX, Gurobi, Pyomo… using linear programming, nonlinear, evolutionary algorithms…