【待ち行列|M/M/1モデル】5つの定理の証明方法と物流への適用事例

2022年11月27日

Photo by Wolfgang Hasselmann on Unsplash

【円安の今こそチャンス!】

親日国カンボジアであなたの会社の商品を販売してみませんか?

食品/飲料ヘルスケアコスメ流通のスモールスタートを管理人がサポートします。

Royal Palace in Phnom Penh (2015)

物流業界にこそ有用な「待ち行列理論」

管理人は製造業界から物流業界に転職しましたが、当初は物流業界の生産性の低さに衝撃を受けました。

製造業では、あらかじめ決まった製品を生産するため、生産機器の能力や作業者の人数を無駄なく設計できます。

また、生産計画も前もって決められているため、作業シフトも無駄なく組めます。

 

ところが物流業では、これらの条件が両方とも満たせないことがほとんどです。

メーカー系の物流会社であれば、取り扱う製品の種類が限定されるためまだマシですが、流通業界では取り扱いSKUは膨大な数になりますし、消費者向けの物流においては荷姿の種類は無限です。

荷姿により作業効率が異なることは容易に想像できますね。

また、数日または数週間前から生産量が決まっているメーカーと違い、物流ではその日にならないと物量が決まらないことがほとんどです。

そのため、過去データに基づく予測が重要になります。

 

この予測に「待ち行列理論」は大きな効力を発揮します。

もともと病院やコールセンター等での窓口の数を合理的に決める目的で使われることが多いのですが、物流センターの設計や作業員数の計画等、物流でも広く適用可能です。

そこで、まずは基本となるM/M/1モデルについて見ていきましょう。

 

M/M/1モデルとは?

簡単にいうと、窓口が一つしかない行列のモデルです。

M/M/1の最後の1が窓口の数を表します。

では残りのM/Mは何かというと、単位時間当たりに行列に加わる人数も、単位時間当たりに窓口で処理する人数もポアソン分布に従うという意味です。

マルコフ過程の略で、過去の実績に依らず毎回ランダムな値を取るということですので、ポアソン分布に従うというのと同じ意味と考えて問題ありません。

 

ポアソン分布については本サイトでも何回か取り上げていますが、ポアソン分布を理解できる記事として最もアクセスの多い記事がこちらです。

イチローの安打数がポアソン分布にならず正規分布になる理由を考察してみた

このようにポアソン分布に従うと仮定すれば、例えば行列に加わる人数が平均して1分間に2人である場合、

1分間に1人が加わる確率=27%

1分間に2人が加わる確率=27%

1分間に3人が加わる確率=18%

になります。

 

1つしかない窓口で処理される人数も、同様のポアソン分布に従うと考えます。

この時、

単位時間当たりに行列に加わる人数:λ

単位時間当たりに窓口で処理される人数:μ

利用率(=μに対するλの割合):ρ(=λ/μ)

と定義すると、

M/M/1モデルの行列は次のような性質を持つことが数学的に導かれます。

 

定理1)系内にいる人数(行列と窓口にいる人数の合計)がj人である確率Πjは

Πj=ρj(1-ρ)

 

定理2)系内にいる人数の期待値(平均)Lは

L=ρ/(1-ρ)

 

定理3)行列に並んでいる人数の期待値(平均)Lqは

Lq=ρ2/(1-ρ)

 

定理4)系内に滞在する時間の期待値(平均)Wは

W=1/(μ―λ)

 

定理5)行列に滞在する(並ぶ)時間の期待値(平均)Wqは

Wq=ρ/(μ-λ)

 

この定理は非常に便利です。

以下、どのようにこの定理が導かれるのかを見ていきます。

微分の知識は一切不要です。

 

M/M/1モデル定理の証明方法

定理1)系内にいる人数がj人である確率

テーマパークへ行って、人気アトラクションに乗ることを想像してみましょう。

朝一で行って、そのアトラクション目がけて走って行けば、並ばずに乗れるかもしれません。

しかし、一般的に朝一から徐々に行列は伸びていき、ある時点からほぼ一定の行列の長さに落ち着くでしょう。

これを定常状態といいます。

そして、定常状態における系内の人数(行列に並んでいる人とアトラクションに乗っている人の合計人数)をjとします。

到着率(単位時間当たりに行列に加わる人数)λと、離脱率(単位時間当たりに行列から離脱する人数=単位時間当たりにアトラクションで処理される人数)μを合わせて描くと、次のようになります。

 

定常状態では系内の人数は一定ですので、

j人の状態から離脱する人数=j人の状態に到着する人数

が成り立つと考えられます。

j人の状態から単位時間当たりに離脱する人数は、j人の状態からj+1人の状態に単位時間当たりに到着する人数とj人の状態からj-1人の状態に単位時間当たりに離脱する人数の和です。

下図でいうと赤字の部分です。

 

前章で、系内にいる人数(行列と窓口にいる人数の合計)がj人である確率はΠjと定義しましたが、これを使うとj人から単位時間当たりに離脱する人数の期待値

Πjλ+Πjμ

で計算できます。

 

同様にj人の状態に流入する人数の期待値は

Πj-1λ+Πj+1μ

で計算できます。

 

定常状態ということは流入=流出ですので、

Πjλ+Πjμ=Πj-1λ+Πj+1μ

が成り立つはずですね。

 

この漸化式を解くために、0人の状態での流入と流出を考えてみましょう。

 

この2つが釣り合うはずなので、

Π0λ=Π1μ

が成り立ちます。

次に1人の状態での流入と流出を考えましょう。

 

Π1λ+Π1μ=Π0λ+Π2μ

が成り立つはずです。

この式を前の式も使って変形すると、Π2を求める式は

Π2=Π0λ2/μ2

となります。

そして、これをΠjを求める式にまで一般化すると、

Πj=Π0λj/μj

=Π0ρj

となることが容易に導けます。

 

ここで、

Π0+Π1+Π2+・・・=1

であることに注意すると、

Π0+Π0ρ+Π0ρ2+・・・=1

つまり、

Π0(1+ρ+ρ2+・・・)=1

と書けます。

 

ここでカッコの中の式を

S=1+ρ+ρ2+・・・

と定義します。

この両辺にρを掛けると、

ρS=ρ+ρ2+ρ3+・・・

となりますが、この式を前式から引くと

S-ρS=1

となり、更に変形すると

S=1/(1-ρ)

となります。

 

つまり、

Π0(1+ρ+ρ2+・・・)=1

Π0×1/(1-ρ)=1

すなわち、

Π0=1-ρ

となることが導けます。

 

従って

Πj=Π0ρj

ですので、

Πj=ρj(1-ρ)

であることが導けました。

 

定理2)系内にいる人数の期待値

次に系内にいる人数の期待値がL=ρ/(1-ρ)で計算できることを証明します。

これは、

系内の人数が0人である確率×0+系内の人数が1人である確率×1+系内の人数が2人である確率×2+・・・

で計算できます。

系内の人数がj人である確率が

Πj=ρj(1-ρ)

ですので、

L=Π0×0+Π1×1+Π2×2+・・・

=(1-ρ)×0+ρ(1-ρ)×1+ρ2(1-ρ)×2+・・・

=(1-ρ)(ρ+2ρ2+3ρ3+・・・)

と書けます。

 

ここで

z=ρ+2ρ2+3ρ3+・・・

と置きます。

この両辺にρを掛けると、

ρz=ρ2+2ρ3+3ρ4+・・・

となります。

この式を前式から引くと、

z―ρz=ρ+ρ2+ρ3+・・・

変形すると、

z(1-ρ)=1/(1-ρ)―1=ρ/(1-ρ)

つまり、

z=ρ/(1-ρ)2

となります。

 

このzをLを求める式に戻すと、

L=(1-ρ)z

=(1-ρ)ρ/(1-ρ)2

=ρ/(1-ρ)

となります。

 

定理3)行列にいる人数の期待値

Lは系内にいる人数の期待値ですが。Lqは行列に並んでいる人数の期待値です。

M/M/1モデルでは窓口が1つしかない想定ですので、系内にいる人数がj人なら、行列に並んでいる人数はj-1人です。

なぜなら、j人のうち1人は窓口にいるからです。

従って、行列にいる人数の期待値Lqは次のように計算できます。

Lq=Π1×(1-1)+Π2×(2-1)+Π3×(3-1)+・・・

=Π1×1+Π2×2+Π3×3+・・・-Π1-Π2-Π3-・・・

=L-(1-Π0

=ρ/(1-ρ)-(1-1+ρ)

=ρ2/(1-ρ)

 

定理4)系内に滞在する時間の期待値

Wとは系内に滞在する時間の期待値(平均)のことです。

これを計算するには、リトルの法則を使います。

【リトルの法則とは?】リーンな物流にカイゼンするための使い方

 

この法則によると

W=L/λ

ですので、

W=λ/(μ-λ)/λ

=1/(μ-λ)

であることが簡単に導けます。

 

定理5)行列に滞在する時間の期待値

Wqは行列に滞在する時間の期待値(平均)ですが、これもリトルの法則により次のように簡単に導けます。

Wq=Lq/λ

=λ2/μ(μ-λ)/λ

=λ/μ(μ-λ)

=ρ/(μ-λ)

 

M/M/1モデルで荷卸しの待ち時間を求めてみる

物流センターに貨物を納入するトラックの待ち時間はトラック輸送業界にとっては生産性を下げる要因になり、物流センターの近隣住民にとっても迷惑です。

最近ではこれをDXによって変革しようという動きが広がっています。

【待ち行列理論の使い方】トラック予約受付システムを導入すると何が変わるのか?

 

このトラックの待ち時間を「待ち行列理論」で推定してみましょう。

今回はM/M/1モデルを適用しますので、トラックバースが1か所しかない単純なケースを想定します。

 

このモデルを適用するために必要な情報はλμです。

このケースのλとμは次のようになります。

λ:単位時間当たりに到着するトラックの平均台数

μ:単位時間当たりに荷卸しできる平均台数

 

これらの平均台数を求めるには過去データを使います。

例えば、ある物流センターでは平均して1時間に2台のトラックが到着し、荷卸しは1時間で平均3台分処理できているというデータが得られたとしましょう。

この場合のトラックの平均待ち時間を計算してみます。

 

トラックが荷卸しするまでの待ち時間ですから、Wqを求めることになります。

Wqを求める公式は

Wq=ρ/(μ-λ)

でした。

λ=2、μ=3、ρ=λ/μ=2/3なので、

Wq=2/3×(3-2)

=2/3時間

=40分

となります。

 

トラックが2台/時で来るのに対し、荷卸しスピードは3台/時と1.5倍も速いのに、平均40分も待つことになります。

意外と長いですね。

この待ち時間を減らすには、トラックバースの数を増やすか、トラックの到着率や荷卸しスピードの分散を減らすための改善が必要になります。

 

ところがトラックバースを増やして複数個所になると、今回もM/M/1モデルでは計算できません。

そのような複数窓口の待ち行列を分析するモデルがM/M/Cモデルです。

【Excelで解く待ち行列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…