エレベーター

エレベーター 誰もが、いつまでたっても来ないエレベーターを待つというフラストレーションを共有したことがあるでしょう。「ボタンを押したのに、なぜ来ないんだ？」とあなたは尋ねます。エレベーターという身近なものでさえ、見た目以上に複雑なのです。 この記事では、エレベーターの謎を解き明かしていきます。あなたがボタンを押す方法と、エレベーターがあなたをどう動かすか。 43211x5x25x 1台のエレベーター 最も単純なエレベーターアルゴリズムはSCANと呼ばれ、1961年に特許が取得されました。エレベーターはロビーから始まり、最上階まで行き、そこで反転して戻ってきます。途中で誰かの乗り降りを扱います。 ほとんどの場合、実際には最上階に行く必要はありません。もしエレベーターが要求された階までしか行かずに反転する場合、そのアルゴリズムはLOOKアルゴリズムと呼ばれます。これはほとんどの人が知っていて期待しているアルゴリズムです。 43211x5x25x 5つの呼び出しを追加 複数台のエレベーター ここからが謎の始まりです。もしエレベーターが複数台ある場合、どの車が誰をピックアップするかをどのように調整するのでしょうか？ 最も基本的なシステムでは、中央スケジューラがあり、各エレベーターがどの階に停止するかを指示します。新しいリクエストが入ると、最も近いエレベーターに割り当てられます。しかし、後述するように、もっと良い方法があります。 43211x5x25x 長い待ち時間 エレベーターアルゴリズムの良さを実際にどのように測定するのでしょうか？明らかな指標は、エレベーターが到着するまでの待ち時間です。 非常に単純な測定方法は、「30秒以内にエレベーターが到着する頻度は？」あるいは「90秒以内にエレベーターが到着する頻度は？」です。 -wait < 30s -wait < 90s 6543211x5x25x flow14/min reset 統計的応用 より厳密には、待ち時間の分布を見たいのです。数千回の乗車にわたる待ち時間をプロットすると、以下のヒストグラムが得られます。 654321010sp50—p90—25x100x500x flow14/min reset p90が2分というのは、90%の乗客が2分以下でエレベーターを待つことを意味します。p50が1分というのは、半数の乗客が1分以内にエレベーターが到着することを意味します。 人々は通常、自分が待つ平均時間を覚えていません。彼らは、エレベーターが永遠にかかったと感じた時間を記憶に留めます。それがp90のケースです。 朝のラッシュ すべての乗客トラフィックが同じではありません。大きな企業オフィスビルを想像してみてください。朝は、ほとんどすべてのトラフィックがロビーから上層階への移動で占められています。 夕方になると、全員がビルを出るため、これは逆転します。昼食時のラッシュは両方の要素が混在し、残りのトラフィックはしばしば階から階への移動です。 Morning Lunch Evening Interfloor -wait < 30s -wait < 90s 6543215x25x100x flow14/min reset 待ち時間の分布は、時間帯やエレベーターが直面しているトラフィックパターンによって劇的に変化します。朝のラッシュは、待ち時間の統計が最も悪いことで悪名高いです。 より賢いエレベーター LOOKエレベーターアルゴリズムを分析する際、乗客がどのように車に割り当てられるかをLOOKED（ハハ）しました。私たちは最も近い車に各リクエストを単純に割り当てましたが、もっとうまくやれると言いました。 もし最も近い車が満員だったらどうなるでしょうか？OtisのRSR（Relative System Response）アルゴリズムを使えば、より賢くなれます。RSRは、各車が乗客をピックアップするのにどれだけ適しているかをスコアリングします。スコアが低いほど良いです。 RSRピックアップスコア Score = ETA to pickup + onboard load penalty + same-direction anti-bunching penalty - direction-match bonus - idle-nearby bonus - low-load bonus アンチバンチング 別の車がすでに同じ階に同じ方向に向かっている場合、その車をペナルティ対象とします。 アイドル近接 呼び出し元から2階以内のアイドル状態の車にボーナスを与えます。 RSRは5秒ごとに再最適化も行います。エレベーターAでピックアップされる予定だった乗客も、エレベーターAが遅延に遭遇した場合、エレベーターBに再ルーティングされる可能性があります。この再最適化は、トラフィックフローを合理化する鍵となります。 以下のグラフィックでは、もし3階からの呼び出しボタンがちょうどその瞬間に押された場合、各エレベーターが最適な選択肢であるときに点灯します。エレベーターが移動するにつれてこれは常に変化し、オプティマイザーが動作している様子を示しています。 4321ABCDAScore 1 LOOK vs RSR エレベーター分析ツールキットを装備して、LOOKとRSRのパフォーマンスをベンチマークし、よりスマートなエレベーターアルゴリズムが実際に待ち時間をどれだけ改善するかを見てみましょう。 LOOK -wait < 30s -wait < 90s 10987654321 RSR -wait < 30s -wait < 90s 10987654321 1x25x250x flow8/min reset 興味深いことに、フローレートが高くなるにつれて、LOOKはRSRを上回り始めます。エレベーターが常に満員で、すべての階に停止する場合、追加のルールはそれほど重要ではありません。 また、LOOKは、エレベーターバンクあたりのエレベーターが少ない小規模なビルでもRSRを上回る傾向があります。時には物事をシンプルに保つ方が良いのです。 追跡できるもう一つの指標は、旅程時間、つまり目的の階に到着するまでにエレベーター内で実際に待っている時間です。RSRとLOOKはここでも異なる特性を持っていますが、それはこの記事の範囲外です。 デスティネーションディスパッチ すべてエレベーターにボタンがあるわけではありません。最新の高級エレベーターには、各階にキオスクがあり、エレベーターが到着する前に目的地を指定できます。その後、キオスクはどのエレベーターを待つべきかを示します。 これはデスティネーションディスパッチと呼ばれます。一見すると、それは素晴らしいように思えます。エレベーターオプティマイザーは、誰がどこへ行くかを知っているので、待ち時間を減らすためにそれを利用できるはずですよね？ RSR -wait < 30s -wait < 90s 87654321 Destination Dispatch -wait < 30s -wait < 90s 87654321 71x25x250x flow8/min reset 実際には、これらの派手なキオスクは、従来の昔ながらの上げ下げボタンよりも、待ち時間においては一般的に劣ることが判明しました。キオスクが勝つエッジケース（8台以上のエレベーターバンクを持つ非常に高いビル）も確かにありますが、ほとんどの場合、シンプルな上げ下げボタンが最高です。 この直感に反する結果は、すべて5秒ごとにシステムが各エレベーターの経路を再最適化する再バランシングステップのおかげです。キオスクは硬直性を強制し、指定されたエレベーターに乗らなければなりません。 エレベーターを呼んでから30秒後の世界の状況は非常に異なっているかもしれませんが、システムは適応できません。柔軟性の喪失は、オプティマイザーにとって追加の情報に見合うものではないことが判明しました。 フルシミュレーション ここに、すべてのボタンとノブを操作できるシミュレーションがあります。自由に遊んでください！ Morning Lunch Evening Interfloor -wait < 30s -wait < 90s 87654321 floors8 cars4 flow18/min 1x25x100x Look RSR Destination Dispatch reset histogram 結論 この記事はエレベーターアルゴリズムの表面をかすめたにすぎません。次にエレベーターを待っているときに、個人的に受け取らないようにしてみてください。エレベーターはあなたの声を聞いていますが、考えることがたくさんあるのです。