HN 日本語サマリー

← 一覧へ戻る
プログラミング

エレベーター

Elevators (john.fun)

1516 pointsby Jrh0203382 コメント

要約

エレベーターの待ち時間やアルゴリズムについて解説した記事です。単純なSCANやLOOKアルゴリズムから、複数のエレベーターを協調させるシステム、待ち時間を測定する指標、そしてより高度なOtis RSRアルゴリズムやDestination Dispatchシステムについて、その利点と欠点を比較しながら説明しています。最終的には、シンプルなアルゴリズムが特定の状況でより優れている場合もあることを示唆しています。

全文翻訳

エレベーター

エレベーターがなかなか来ないという、誰もが経験したことのあるフラストレーション。「ボタンを押したのに、なぜ来ないんだ?」とあなたは問うでしょう。エレベーターという身近な存在ですが、その仕組みは見た目以上に遥かに複雑です。

この記事では、エレベーターの謎を解き明かしていきます。あなたがボタンを押す方法、そしてエレベーターがあなたをどう動かすのか。

4321

1台のエレベーター

最もシンプルなエレベーターアルゴリズムはSCANと呼ばれ、1961年に特許が取得されました。エレベーターはロビーから出発し、最上階まで到達してから反転して戻ってきます。その途中、乗客を乗せたり降ろしたりします。

ほとんどの場合、実際には最上階に行く必要はありません。もしエレベーターが要求された階までしか行かずに反転する場合、そのアルゴリズムはLOOKアルゴリズムと呼ばれます。これはほとんどの人が知っていて期待するアルゴリズムです。

4321

複数台のエレベーター

ここからが謎の始まりです。複数台のエレベーターがある場合、どの車が誰をピックアップするかをどのように調整するのでしょうか?

最も基本的なシステムでは、中央のスケジューラが各エレベーターにどの階に停止するかを指示します。新しいリクエストが入ると、最も近いエレベーターに割り当てられます。しかし、後述するように、これよりも良い方法があります。

4321

長い待ち時間

エレベーターアルゴリズムの良さをどのように測定するのでしょうか?明白な指標は、エレベーターを待つ時間です。

非常に簡単な測定方法は、「エレベーターが30秒以内に到着する頻度は?」や「エレベーターが90秒以内に到着する頻度は?」といったものです。

待ち時間 < 30秒

待ち時間 < 90秒

654321

flow14/min

応用統計

より厳密には、待ち時間の分布を調べたいのです。数千回の乗車にわたる待ち時間をプロットすると、以下のヒストグラムが得られます。

654321

010秒

p50—p90—

flow14/min

p90が2分というのは、90%の時間で利用者はエレベーターを2分以下で待つことを意味します。p50が1分というのは、半分の時間でエレベーターが1分以内に到着することを意味します。

人々は通常、自分が待った平均時間を覚えていません。彼らは、エレベーターが永遠にかかったと感じた時間、つまりp90のケースに固執します。

朝のラッシュ

すべての乗客トラフィックが同じではありません。大きな企業のオフィスビルを想像してみてください。朝は、ほとんどすべてのトラフィックがロビーから上層階への移動で占められます。

夕方には、全員がビルを出るため、これが逆転します。昼食時のラッシュは両方の要素が混ざり合い、残りのトラフィックはしばしば階から階への移動です。

待ち時間 < 30秒

待ち時間 < 90秒

654321

flow14/min

待ち時間の分布は、一日の時間帯やエレベーターが直面するトラフィックパターンによって劇的に変化します。朝のラッシュは、最悪の待ち時間統計で悪名高いです。

よりスマートなエレベーター

LOOKエレベーターアルゴリズムを分析する際、ライダーがどのように車に割り当てられるかを(ha ha)LOOK(見た)しました。私たちは、各リクエストを最も近い車に単純に割り当てましたが、もっとうまくやれると言いました。

もし最も近い車が満員だったらどうなるでしょうか?OtisのRSR(Relative System Response)アルゴリズムを使えば、より賢くなることができます。RSRは、各車が乗客を迎えに行くのにどれだけ適しているかをスコアリングします。スコアが低いほど良いです。

RSRピックアップスコア

スコア = ピックアップまでのETA + 乗車中の負荷ペナルティ + 同方向アンチバンチングペナルティ - 方向一致ボーナス - アイドル近傍ボーナス - 低負荷ボーナス

アンチバンチング

他の車がすでに同じ階に同じ方向に向かっている場合、その車をペナルティ対象とします。

アイドル近傍

呼び出し元から2フロア以内のアイドル状態の車にボーナスを与えます。

RSRはまた、5秒ごとに再最適化を行います。エレベーターAが遅延に遭遇した場合、エレベーターAによってピックアップされる予定だった乗客は、エレベーターBに再ルーティングされる可能性があります。この再最適化は、トラフィックフローを合理化する上で鍵となることがわかっています。

以下のグラフィックでは、各エレベーターは、その瞬間に3階からの呼び出しに応答するのに最適な選択肢である場合に点灯します。これはエレベーターが移動するにつれて常に変化し、最適化の動きを示しています。

4321ABCDAScore 1

LOOK vs RSR

エレベーター分析ツールキットを装備して、LOOKとRSRのパフォーマンスをベンチマークし、よりスマートなエレベーターアルゴリズムが待ち時間をどれだけ改善するかを見てみましょう。

LOOK

-待ち時間 < 30秒

-待ち時間 < 90秒

10987654321

RSR

-待ち時間 < 30秒

-待ち時間 < 90秒

10987654321

flow8/min

興味深いことに、フローレートが高くなるにつれて、LOOKはRSRを上回り始めます。エレベーターが常に満員で、すべての階に停車する場合、追加のルールはそれほど重要ではなくなります。

LOOKはまた、エレベーターバンクあたりのエレベーターが少ない小規模なビルでもRSRを上回る傾向があります。時には、単純さを保つ方が良いのです。

追跡できるもう一つの指標は、ジャーニータイム、つまりエレベーターに乗ってから目的の階に到着するまでの実際の待ち時間です。RSRとLOOKはここでも異なる特性を持っていますが、それはこの記事の範囲を超えています。

デスティネーションディスパッチ

すべてのエレベーターにボタンがあるわけではありません。最新の高級エレベーターの中には、各階にキオスクがあり、エレベーターが到着する前に目的の階を指定できるものがあります。キオスクは、どのエレベーターを待つべきかを示してくれます。

これはデスティネーションディスパッチと呼ばれます。一見すると、それは素晴らしいように思えます。エレベーターの最適化プログラムは、誰がどこへ行くのかを完全に把握しているので、待ち時間を減らすためにこれを利用できるはずですよね?

RSR

-待ち時間 < 30秒

-待ち時間 < 90秒

87654321

デスティネーションディスパッチ

-待ち時間 < 30秒

-待ち時間 < 90秒

876543217

flow8/min

実際には、これらの派手なキオスクは、従来の「アップ・ダウン」ボタンよりも待ち時間において一般的に劣っています。キオスクが有利になるエッジケース(8台以上のエレベーターバンクを持つ非常に高いビル)も確かにありますが、ほとんどの場合、シンプルなアップ・ダウンボタンが優位です。

この直感に反する結果は、すべて、5秒ごとにシステムが各エレベーターの経路を再最適化するリバランスのステップのおかげです。キオスクは硬直性を強制します。あなたは割り当てられたエレベーターに乗らなければなりません。

エレベーターを呼び出してから30秒後の世界の状況は大きく異なるかもしれませんが、システムは適応できません。柔軟性の喪失は、最適化プログラムにとって追加情報に見合う価値がないことが判明しました。

完全シミュレーション

ここでは、すべてのボタンとノブを操作できるシミュレーションがあります。自由に試してみてください!

待ち時間 < 30秒

待ち時間 < 90秒

87654321

floors8cars4flow18/min

結論

この記事はエレベーターアルゴリズムの表面をかすめたにすぎません。次にエレベーターを待っているときに、個人的に受け止めないようにしてください。エレベーターはあなたの声を聞いていますが、考えることがたくさんあるのです。