Webブラウザで見る 待ち行列 シミュレーション 藤本　衡

想定する話の内容 「うちの4年生に分かる」 何となく簡単に試せる待ち行列シミュレーション 偏差値50前後 ひょっとすると高校で数Ⅲをやってない 確率は2～3年前に受講 内容の半分くらいは分かってない 卒業研究の解析手法で待ち行列が候補になってる 何となく簡単に試せる待ち行列シミュレーション JavaScriptで書いてみました ネット接続してれば今試せます（たぶん） 2016/6/18 待ち行列チュートリアル

シミュレーションとは？ 実際の現象を簡略化し数学的に表現＝モデル （コンピュータ）シミュレーション コンピュータ上でのモデル表現 条件を変えて繰り返し実験可能 モデルに確率的な要因が含まれるか？ →モンテカルロ・シミュレーション モデルの状態は時間変化するか？ 連続型（タイムスライス）シミュレーション 離散型（イベント）シミュレーション 2016/6/18 待ち行列チュートリアル

シミュレーションにおける変数 外生変数 内生変数 条件変数：あらかじめ与えられる条件 制御変数：変更可能な要因 目的変数：評価基準 状態変数 外生変数の関数として表現される 状態変数 2016/6/18 待ち行列チュートリアル

混雑現象のモデル化 様々な混雑や滞留 全てを共通のモデルで表現できればうれしい →待ち行列 人の混雑 モノの混雑 情報の混雑 小売店、銀行、飲食店、娯楽施設、歩道 モノの混雑 輸送機関、生産ライン 情報の混雑 プロセス、トランザクション 電話回線・チャネル パケット 全てを共通のモデルで表現できればうれしい →待ち行列 2016/6/18 待ち行列チュートリアル

待ち行列モデル 到着過程 窓口 （サーバ） 待ち室（バッファ） 2016/6/18 待ち行列チュートリアル

待ち行列モデル 客：人でも車でもパケットでもよい 到着間隔分布 客がどのような間隔で到着するか 多くの場合はランダム 平均到着間隔 𝜆 −1 同時に来る客の人数 単独 集団（バルク、バッチ） 状態依存性 到着が混み具合に影響されるか 有限呼源（潜在的な客数が有限） 到着過程 窓口 （サーバ） 待ち室（バッファ） 2016/6/18 待ち行列チュートリアル

待ち行列モデル バッファサイズ 現実には有限 制限を設けない（無限と考える）ことも多い サービス規律 待ち客をどのような順序で窓口に入れるか 到着過程 窓口 （サーバ） 待ち室（バッファ） 2016/6/18 待ち行列チュートリアル

待ち行列モデル 窓口：レジでも工作機械でもCPUでもよい 窓口数 1, 複数（有限）, 無限 窓口でのサービス時間分布 多くの場合はランダム 平均サービス時間 𝜇 −1 同時に処理する客の数 単独か、集団（バルク、バッチ）か 状態依存性 サービス時間が混み具合に影響されるか サービス能力 同一か、異なるか 到着過程 窓口 （サーバ） 待ち室（バッファ） 2016/6/18 待ち行列チュートリアル

離散型シミュレーションとしての待ち行列 連続型の方が直感的な気もするが 待ち行列で起きるイベント 到着（客数が増える） サービス終了＝退去（客数が減る） そのほか（割り込み、窓口休憩、etc.）→今は無視 2016/6/18 待ち行列チュートリアル

イベントの発生と処理 窓口の客は残りサービス時間のタイマーを持つ 次の客の到着までの残り時間タイマー 最も小さいタイマーの値が次のイベントまでの時間間隔 到着なら客数増、退去なら客数減 他のタイマーの値を差し引く 待ち客がいれば対応するタイマーの値を再生成 待ち客がいなければタイマーを無視 9.62 4.19 5.43 8.54 7.81 2.38 6.20 0.77 2016/6/18 待ち行列チュートリアル

待ち行列のシミュレーション 外生変数 内生変数 到着間隔分布：条件変数 サービス時間分布：条件変数 窓口数、バッファサイズ：条件変数 パラメータ：変更可能？（制御変数） サービス時間分布：条件変数 窓口数、バッファサイズ：条件変数 内生変数 系内客数：状態変数 タイマー：状態変数 到着までの残り時間 各窓口にいる客の残りサービス時間 目的変数…いろいろ 2016/6/18 待ち行列チュートリアル

系内客数の時間変化（窓口1） 系内 客数 時間 客1の サービス 時間 客2の サービス 時間 客3の サービス 時間 客1の 到着間隔 客4の 到着間隔 2016/6/18 待ち行列チュートリアル

到着間隔分布/サービス時間分布/窓口数/システム容量/潜在的客数/サービス規律 ケンドールの記号 到着間隔分布/サービス時間分布/窓口数/システム容量/潜在的客数/サービス規律 例：M/M/1 M: 到着間隔が指数分布に従う確率変数 M: サービス時間も指数分布に従う確率変数 確率変数はすべて互いに独立 窓口は1つ システム容量、潜在的客数は無限 先着順 （本当はM/M/1/∞/∞/FCFSと書くところ） 2016/6/18 待ち行列チュートリアル

系内客数分布 客数に関する評価指標を得るのに便利 系内客数𝑖ごとに積算用変数 𝑡 𝑖 を持つ 次のイベントを起こす最小タイマー値を 𝑡 𝑖 に加算 𝑡 𝑖 をシミュレーションの 総時間で割れば 時間割合 𝜋 𝑖 が得られる 累積 時間 系内 客数 𝑡 0 𝑡 1 𝑡 2 𝑡 3 時間 系内 客数 2016/6/18 待ち行列チュートリアル

客数に関する評価指標の例 平均系内客数 𝐿= 𝑖=0 ∞ ( 𝑖×𝜋 𝑖 ) 平均待ち行列長（窓口数𝑠の場合） 𝐿 𝑞 = 𝑖=1 ∞ (𝑖× 𝜋 𝑠+𝑖 ) =𝐿− 𝜆 𝜇 2016/6/18 待ち行列チュートリアル

待ち時間/滞在時間 平均待ち時間 𝑊 𝑞 を知りたい 𝑘番目の到着客にタイマー 𝑊 𝑘 を持たせる方法 𝑊 𝑘 =max{ 𝑊 𝑘−1 + 𝑆 𝑘−1 − 𝑇 𝑘 , 0}（窓口1つの場合） 𝑆 𝑘 : 𝑘番目の客のサービス時間 𝑇 𝑘 : (𝑘−1)番目の客と𝑘番目の客の到着間隔 𝑊 𝑘 の平均を求めればよい 客の数だけ変数が必要 現代では問題ない？ 平均を求めたいなら積算用変数に足した後捨てればよい 2016/6/18 待ち行列チュートリアル

リトルの公式（Little’s Law） 𝐿 𝑞 =𝜆 𝑊 𝑞 𝐿=𝜆𝑊 平均待ち時間 𝑊 𝑞 は平均待ち行列長から得られる 平均系内滞在時間𝑊と平均系内客数𝐿も同様 つまり、平均だけなら待ち時間分布は不要 𝐿 𝑞 =𝜆 𝑊 𝑞 𝜆: 到着率（平均到着間隔の逆数） 𝐿=𝜆𝑊 2016/6/18 待ち行列チュートリアル

M/M/1のシミュレーション 外生変数 内生変数 到着間隔分布：指数分布（条件） サービス時間分布：指数（条件） パラメータ：変更可能？（制御） サービス時間分布：指数（条件） 窓口数1、バッファサイズ∞：条件 内生変数 系内客数：状態変数 イベントタイマー イベントごとに再設定＝残余時間を記録する必要が無い 指数分布の無記憶性 2016/6/18 待ち行列チュートリアル

（疑似）乱数の作り方 一様乱数𝑈を与える関数は大抵の言語にある 逆関数法: 𝑋= 𝐹 −1 (𝑈) （ 𝐹は必要な分布のCDF） 一様乱数にも良し悪しがあるが… 逆関数法: 𝑋= 𝐹 −1 (𝑈) （ 𝐹は必要な分布のCDF） 例：指数乱数 𝑋= 𝜆 −1 log⁡(1−𝑈) Box-Muller法：正規分布 待ち行列ではあまり出てこない Python3では以下の分布に対応 一様、三角、ベータ、指数、ガンマ、正規、対数正規、 フォンミーゼス、パレート、ワイブル 2016/6/18 待ち行列チュートリアル

実行してみる http://www.rd.dendai.ac.jp/~fujimoto/quesim/ 2016/6/18 待ち行列チュートリアル

JavaScript環境の留意点 あまりバッチ処理向きではない メモリ消費 疑似乱数：Math.random() ローカルファイルの扱いに制限 デモ向き メモリ消費 1000万人くらい到着させるとまずいかも 疑似乱数：Math.random() 生成アルゴリズムは実装（≒ブラウザ）依存 以前はMWC→今はxorshift128+が主流 標準でseedを固定する方法が無い 再現が必要なケースではスクラッチで疑似乱数を実装 2016/6/18 待ち行列チュートリアル

質疑応答あるある 「シミュレーションの試行回数は？」 「シミュレーションでなくても答え出ませんか？」 1回の試行は「たまたま」の1サンプル 精度を上げるには多数のサンプルが必要 「シミュレーションでなくても答え出ませんか？」 M/M/sくらいまでは公式が転がってる 数値解析に慣れていればもう少し複雑なモデルもOK そもそもシミュレーションは効率が悪い＝最後の手段 2016/6/18 待ち行列チュートリアル

サンプル数の問題 大数の法則 100 1−𝛼 %信頼区間 𝑛:大、 𝑆 𝐿 :小であるほど信頼区間が狭い 無限回試行すれば厳密解に収束する（はず） 有限回試行では誤差を考慮する 100 1−𝛼 %信頼区間 区間が真の値を含む確率が1−𝛼 （𝛼=0.05がよく用いられる） 𝑛:大、 𝑆 𝐿 :小であるほど信頼区間が狭い 𝐿 − 𝑡 𝑛−1 𝛼 𝑆 𝐿 𝑛 , 𝐿 + 𝑡 𝑛−1 𝛼 𝑆 𝐿 𝑛 𝐿 : 標本平均, 𝑆 𝐿 : 不偏標準偏差 𝑡 𝑛 𝛼 : 自由度𝑛のt分布の上側 100𝛼 2 %点（𝑛が大なら正規分布で近似可） 2016/6/18 待ち行列チュートリアル

本講演のまとめ 何となく待ち行列の概要 何となくシミュレーションの概要 基本的な振る舞い シミュレーションの留意点 各種確率変数と系内客数の変化の関係 シミュレーションの留意点 使いどころと使い方を誤らないように 2016/6/18 待ち行列チュートリアル

参考文献(1)待ち行列全般 某密林に在庫有＆藤本が読んだことがあるもの 高橋・森村, 「混雑と待ち」, 朝倉書店, 2001. 塩田他, 「待ち行列理論の基礎と応用」, 共立出版, 2014. 宮沢, 「待ち行列の数理とその応用」, 牧野書店, 2013. 紀, 「待ち行列ネットワーク」, 朝倉書店, 2002. 2016/6/18 待ち行列チュートリアル

参考文献(2)シミュレーション 雑誌記事は理工系大学ならたいてい入手可？ 逆瀬川, 「シミュレーションの数理的評価」, オペレーショ ンズ・リサーチ, 46(4), pp.168-173, 2001.（オープン） 高橋勝他, 「シミュレーション工学」, 朝倉書店, 2007. 中川, 「モンテカルロシミュレーション基礎： --推定精度 評価の問題点とその克服--」信学会通信ソサイエティマ ガジン, Vol.2008, No.6, pp.6_11—6_20, 2008.（定額） 大野他, 「Excelで学ぶオペレーションズリサーチ」, 近代 科学社, 2014. 井家他, 「表計算ソフトで待ち行列を再現してみよう」, オ ペレーションズ・リサーチ, Vol.60(9), pp.526-531, 2015. （有料） 2016/6/18 待ち行列チュートリアル