交通渋滞の近似

確率論の一分野である待ち行列理論において、重交通近似（重交通極限定理[1]または拡散近似と呼ばれることもある）とは、モデルのパラメータにいくつかの制限条件を課した上で、待ち行列モデルと拡散過程を適合させることである。このような最初の結果はジョン・キングマンによって発表され、彼はM/M/1待ち行列の利用パラメータが1に近い場合、待ち行列長過程のスケール版を反射ブラウン運動によって正確に近似できることを示した。[2]

交通渋滞

重交通近似は、典型的には、時刻tにおけるシステム内の顧客数を記述するプロセスX ( t )に対して示される。これは、モデルパラメータの限界値の下でモデルを検討することによって得られるため、結果が有限であるためには、モデルを係数nで再スケールする必要がある。nは[3]で示される。490 

X ^ n ( t ) = X ( n t ) − E ( X ( n t ) ) n {\displaystyle {\hat {X}}_{n}(t)={\frac {X(nt)-\mathbb {E} (X(nt))}{\sqrt {n}}}}

そしてこの過程の限界はn  → ∞と考えられる。

一般に、このような近似が考慮される環境には 3 つのクラスがあります。

  1. サーバーの数は固定で、トラフィック強度（利用率）は（下から）1に増加します。キュー長の近似は反射ブラウン運動です。[4] [5] [6]
  2. トラフィック強度は一定で、サーバ数と到着率が無限大に増加する。この場合、キュー長の制限は正規分布に収束する。[7] [8] [9]
  3. βは固定値であり、
β = ( 1 − ρ ) s {\displaystyle \beta =(1-\rho ){\sqrt {s}}}
ここで、ρはトラフィック強度、sはサーバ数を表す。トラフィック強度とサーバ数が無限大まで増加した場合、極限過程は上記の結果を組み合わせたものとなる。このケースは、HalfinとWhittによって初めて発表されたもので、Halfin–Whittレジーム[1] [10] [11]または品質・効率駆動型（QED）レジーム[12]として知られている。

G/G/1キューの結果

定理1. [13]でインデックス付けされたG/G/1キューのシーケンスを考える。 キューについて、ランダムな到着間隔を 、 ランダムなサービス時間を とすると、交通量と と とで表す。定常状態における顧客のキューでの待ち時間を とすると 、 j {\displaystyle j}
j {\displaystyle j} T j {\displaystyle T_{j}} S j {\displaystyle S_{j}} ρ j = λ j μ j {\displaystyle \rho _{j}={\frac {\lambda _{j}}{\mu _{j}}}} 1 λ j = E ( T j ) {\displaystyle {\frac {1}{\lambda _{j}}}=E(T_{j})} 1 μ j = E ( S j ) {\displaystyle {\frac {1}{\mu _{j}}}=E(S_{j})} W q , j {\displaystyle W_{q,j}} α j = − E [ S j − T j ] {\displaystyle \alpha _{j}=-E[S_{j}-T_{j}]} β j 2 = var ⁡ [ S j − T j ] ; {\displaystyle \beta _{j}^{2}=\operatorname {var} [S_{j}-T_{j}];}

、、およびと仮定すると、 T j → d T {\displaystyle T_{j}{\xrightarrow {d}}T} S j → d S {\displaystyle S_{j}{\xrightarrow {d}}S} ρ j → 1 {\displaystyle \rho _{j}\rightarrow 1}

2 α j β j 2 W q , j → d exp ⁡ ( 1 ) {\displaystyle {\frac {2\alpha _{j}}{\beta _{j}^{2}}}W_{q,j}{\xrightarrow {d}}\exp(1)}

ただし、次の条件を満たすこととする。

（ア） Var ⁡ [ S − T ] > 0 {\displaystyle \operatorname {Var} [S-T]>0}

(b) ある に対して、およびは両方とも、すべての に対してある定数より小さくなります。 δ > 0 {\displaystyle \delta >0} E [ S j 2 + δ ] {\displaystyle E[S_{j}^{2+\delta }]} E [ T j 2 + δ ] {\displaystyle E[T_{j}^{2+\delta }]} C {\displaystyle C} j {\displaystyle j}

ヒューリスティックな議論

  • 待ち時間

を n 番目のサービス時間と n 番目の到着間隔時間の差とします。をn 番目の顧客の待ち行列での待ち時間とします。 U ( n ) = S ( n ) − T ( n ) {\displaystyle U^{(n)}=S^{(n)}-T^{(n)}} W q ( n ) {\displaystyle W_{q}^{(n)}}

定義によれば次のようになります。

W q ( n ) = max ( W q ( n − 1 ) + U ( n − 1 ) , 0 ) {\displaystyle W_{q}^{(n)}=\max(W_{q}^{(n-1)}+U^{(n-1)},0)}

再帰計算の後、次のようになります。

W q ( n ) = max ( U ( 1 ) + ⋯ + U ( n − 1 ) , U ( 2 ) + ⋯ + U ( n − 1 ) , … , U ( n − 1 ) , 0 ) {\displaystyle W_{q}^{(n)}=\max(U^{(1)}+\cdots +U^{(n-1)},U^{(2)}+\cdots +U^{(n-1)},\ldots ,U^{(n-1)},0)}
  • ランダムウォーク

とします。ここで はiid です。 および を定義します。 P ( k ) = ∑ i = 1 k U ( n − i ) {\displaystyle P^{(k)}=\sum _{i=1}^{k}U^{(n-i)}} U ( i ) {\displaystyle U^{(i)}} α = − E [ U ( i ) ] {\displaystyle \alpha =-E[U^{(i)}]} β 2 = var ⁡ [ U ( i ) ] {\displaystyle \beta ^{2}=\operatorname {var} [U^{(i)}]}

そして、

E [ P ( k ) ] = − k α {\displaystyle E[P^{(k)}]=-k\alpha }
var ⁡ [ P ( k ) ] = k β 2 {\displaystyle \operatorname {var} [P^{(k)}]=k\beta ^{2}}
W q ( n ) = max n − 1 ≥ k ≥ 0 P ( k ) ; {\displaystyle W_{q}^{(n)}=\max _{n-1\geq k\geq 0}P^{(k)};}

を極限まで取ると が得られます。 W q ( ∞ ) = sup k ≥ 0 P ( k ) {\displaystyle W_{q}^{(\infty )}=\sup _{k\geq 0}P^{(k)}} n {\displaystyle n}

したがって、n 番目の顧客のキューの待ち時間は、負のドリフトを持つ ランダム ウォークの最大値です。 W q ( n ) {\displaystyle W_{q}^{(n)}}

  • ブラウン運動近似

ジャンプのサイズが 0 に近づき、ジャンプ間の時間も 0 に近づくと、 ランダム ウォークはブラウン運動で近似できます。

となり、独立かつ定常な増分を持つ。交通量が1に近づき、に向かうとき、関数中心極限定理に従って、 を連続値 に置き換えた後、 となる。[14] ：110 このように、 番目の顧客の待ち時間は、負のドリフトを持つ ブラウン運動の上限で近似できる。 P ( 0 ) = 0 {\displaystyle P^{(0)}=0} P ( k ) {\displaystyle P^{(k)}} ρ {\displaystyle \rho } k {\displaystyle k} ∞ {\displaystyle \infty } P ( t )   ∼   N ( − α t , β 2 t ) {\displaystyle P^{(t)}\ \sim \ \mathbb {N} (-\alpha t,\beta ^{2}t)} k {\displaystyle k} t {\displaystyle t} n {\displaystyle n}

  • ブラウン運動の上限

定理2. [15] : 130 を 原点からドリフトと標準偏差を持つブラウン運動とし、 X {\displaystyle X} μ {\displaystyle \mu } σ {\displaystyle \sigma } M t = sup 0 ≤ s ≤ t X ( s ) {\displaystyle M_{t}=\sup _{0\leq s\leq t}X(s)}

もし μ ≤ 0 {\displaystyle \mu \leq 0}

lim t → ∞ P ( M t > x ) = exp ⁡ ( 2 μ x / σ 2 ) , x ≥ 0 ; {\displaystyle \lim _{t\rightarrow \infty }P(M_{t}>x)=\exp(2\mu x/\sigma ^{2}),x\geq 0;}

さもないと

lim t → ∞ P ( M t ≥ x ) = 1 , x ≥ 0. {\displaystyle \lim _{t\rightarrow \infty }P(M_{t}\geq x)=1,x\geq 0.}

結論

W q ( ∞ ) ∼ exp ⁡ ( 2 α β 2 ) {\displaystyle W_{q}^{(\infty )}\thicksim \exp \left({\frac {2\alpha }{\beta ^{2}}}\right)} 交通渋滞時

このように、重交通極限定理（定理1）はヒューリスティックに論証される。正式な証明は通常、特性関数を用いた異なるアプローチに従う。[4] [16]

例

到着率、サービス時間の平均、サービス時間の分散のM/G/1待ち行列を考えます。定常状態における待ち行列の平均待ち時間はいくらですか？ λ {\displaystyle \lambda } E [ S ] = 1 μ {\displaystyle E[S]={\frac {1}{\mu }}} var ⁡ [ S ] = σ B 2 {\displaystyle \operatorname {var} [S]=\sigma _{B}^{2}}

定常状態におけるキュー内の正確な平均待ち時間は次のように求められます。

W q = ρ 2 + λ 2 σ B 2 2 λ ( 1 − ρ ) {\displaystyle W_{q}={\frac {\rho ^{2}+\lambda ^{2}\sigma _{B}^{2}}{2\lambda (1-\rho )}}}

対応する交通渋滞の近似値:

W q ( H ) = λ ( 1 λ 2 + σ B 2 ) 2 ( 1 − ρ ) . {\displaystyle W_{q}^{(H)}={\frac {\lambda ({\frac {1}{\lambda ^{2}}}+\sigma _{B}^{2})}{2(1-\rho )}}.}

交通渋滞の近似値の相対誤差:

W q ( H ) − W q W q = 1 − ρ 2 ρ 2 + λ 2 σ B 2 {\displaystyle {\frac {W_{q}^{(H)}-W_{q}}{W_{q}}}={\frac {1-\rho ^{2}}{\rho ^{2}+\lambda ^{2}\sigma _{B}^{2}}}}

したがって、 のときは、次の式が成り立ちます。 ρ → 1 {\displaystyle \rho \rightarrow 1}

W q ( H ) − W q W q → 0. {\displaystyle {\frac {W_{q}^{(H)}-W_{q}}{W_{q}}}\rightarrow 0.}
  • セルゲイ・フォスによるG/G/1キュー

参考文献

  1. ^ ab Halfin, S.; Whitt, W. (1981). 「多数の指数関数的サーバーを備えたキューの高トラフィック制限」(PDF) .オペレーションズ・リサーチ. 29 (3): 567. doi :10.1287/opre.29.3.567.
  2. ^ Kingman, JFC (1961年10月). 「高トラフィック時の単一サーバキュー」.ケンブリッジ哲学協会数学紀要. 57 (4): 902. Bibcode :1961PCPS...57..902K. doi :10.1017/S0305004100036094. JSTOR  2984229.
  3. ^ ガウタム、ナタラジャン (2012). 『キューの分析：方法と応用』 CRC Press. ISBN 9781439806586。
  4. ^ ab Kingman, JFC (1962). 「渋滞時の待ち行列について」.王立統計学会誌. シリーズB (方法論) . 24 (2): 383– 392. doi :10.1111/j.2517-6161.1962.tb00465.x. JSTOR  2984229.
  5. ^ Iglehart, Donald L.; Ward, Whitt (1970). 「交通量の多い状況における複数チャネルキュー。II：シーケンス、ネットワーク、バッチ」（PDF） . Advances in Applied Probability . 2 (2): 355– 369. doi :10.2307/1426324. JSTOR  1426324. 2012年11月30日閲覧。
  6. ^ Köllerström, Julian (1974). 「複数サーバを持つキューの重交通理論 I」.応用確率ジャーナル. 11 (3): 544– 552. doi :10.2307/3212698. JSTOR  3212698.
  7. ^ Iglehart, Donald L. (1965). 「多数サーバ待ち行列と修理人問題に対する限界拡散近似」.応用確率ジャーナル. 2 (2): 429– 441. doi :10.2307/3212203. JSTOR  3212203.
  8. ^ Borovkov, AA (1967). 「多チャネルシステムにおけるサービスプロセスの極限法則について」.シベリア数学ジャーナル. 8 (5): 746– 763. doi :10.1007/BF01040651.
  9. ^ イグルハート, ドナルド L. (1973). 「待ち行列理論における弱収束」.応用確率論の進歩. 5 (3): 570– 594. doi :10.2307/1425835. JSTOR  1425835.
  10. ^ Puhalskii, AA; Reiman, MI (2000). 「Halfin-Whitt 法におけるマルチクラス GI/PH/N キュー」.応用確率論の進歩. 32 (2): 564. doi :10.1239/aap/1013540179.
  11. ^ Reed, J. (2009). 「Halfin–Whitt 法における G/GI/N キュー」.応用確率年報. 19 (6): 2211– 2269. arXiv : 0912.2837 . doi :10.1214/09-AAP609.
  12. ^ Whitt, W. (2004). 「放棄を考慮した多数サーバキューの効率主導型高トラフィック近似」(PDF) . Management Science . 50 (10): 1449– 1461. CiteSeerX 10.1.1.139.750 . doi :10.1287/mnsc.1040.0279. JSTOR  30046186. 
  13. ^ Gross, D.; Shortie, JF; Thompson, JM; Harris, CM (2013). 「境界と近似」.待ち行列理論の基礎. pp.  329– 368. doi :10.1002/9781118625651.ch7. ISBN 9781118625651。
  14. ^ Chen, H.; Yao, DD (2001). 「技術的要件」.待ち行列ネットワークの基礎. 確率モデルと応用確率. 第46巻. pp.  97– 124. doi :10.1007/978-1-4757-5301-1_5. ISBN 978-1-4419-2896-2。
  15. ^ Chen, H.; Yao, DD (2001). 「シングルステーションキュー」.キューイングネットワークの基礎. 確率モデルと応用確率論. 第46巻. pp.  125– 158. doi :10.1007/978-1-4757-5301-1_6. ISBN 978-1-4419-2896-2。
  16. ^ Asmussen, SR (2003). 「GI/G/1の定常特性」.応用確率論とキュー. 確率モデルと応用確率論. 第51巻. pp.  266– 301. doi :10.1007/0-387-21525-5_10. ISBN 978-0-387-00211-8。
Retrieved from "https://en.wikipedia.org/w/index.php?title=Heavy_traffic_approximation&oldid=1277724428"