交通渋滞の近似

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

交通渋滞

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

${\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. βは固定値であり、

${\displaystyle \beta =(1-\rho ){\sqrt {s}}}$

ここで、ρはトラフィック強度、sはサーバ数を表す。トラフィック強度とサーバ数が無限大まで増加した場合、極限過程は上記の結果を組み合わせたものとなる。このケースは、HalfinとWhittによって初めて発表されたもので、Halfin–Whittレジーム^{[1] [10] [11]}または品質・効率駆動型（QED）レジーム^{[12]として知られている。}

G/G/1キューの結果

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

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

${\displaystyle {\frac {2\alpha _{j}}{\beta _{j}^{2}}}W_{q,j}{\xrightarrow {d}}\exp(1)}$

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

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

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

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

• 待ち時間

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

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

${\displaystyle W_{q}^{(n)}=\max(W_{q}^{(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 です。 および を定義します。 ${\displaystyle P^{(k)}=\sum _{i=1}^{k}U^{(n-i)}}$ ${\displaystyle U^{(i)}}$ ${\displaystyle \alpha =-E[U^{(i)}]}$ ${\displaystyle \beta ^{2}=\operatorname {var} [U^{(i)}]}$

そして、

${\displaystyle E[P^{(k)}]=-k\alpha }$

${\displaystyle \operatorname {var} [P^{(k)}]=k\beta ^{2}}$

${\displaystyle W_{q}^{(n)}=\max _{n-1\geq k\geq 0}P^{(k)};}$

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

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

• ブラウン運動近似

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

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

• ブラウン運動の上限

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

もし ${\displaystyle \mu \leq 0}$

${\displaystyle \lim _{t\rightarrow \infty }P(M_{t}>x)=\exp(2\mu x/\sigma ^{2}),x\geq 0;}$

さもないと

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

結論

${\displaystyle W_{q}^{(\infty )}\thicksim \exp \left({\frac {2\alpha }{\beta ^{2}}}\right)}$ 交通渋滞時

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

例

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

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

${\displaystyle W_{q}={\frac {\rho ^{2}+\lambda ^{2}\sigma _{B}^{2}}{2\lambda (1-\rho )}}}$

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

${\displaystyle W_{q}^{(H)}={\frac {\lambda ({\frac {1}{\lambda ^{2}}}+\sigma _{B}^{2})}{2(1-\rho )}}.}$

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

${\displaystyle {\frac {W_{q}^{(H)}-W_{q}}{W_{q}}}={\frac {1-\rho ^{2}}{\rho ^{2}+\lambda ^{2}\sigma _{B}^{2}}}}$

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

${\displaystyle {\frac {W_{q}^{(H)}-W_{q}}{W_{q}}}\rightarrow 0.}$

外部リンク

• セルゲイ・フォスによるG/G/1キュー

参考文献

1. 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. 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"