エレベーターのスケジューリング・アルゴリズム：LOOK、RSR、およびデスティネーション・ディスパッチ

エレベーターの待ち時間は、ホールコールに対して車両を割り当てるために使用されるディスパッチ・アルゴリズムに大きく依存します。LOOKのような単純なアルゴリズムは、特に一般的なオフィスビルにおいて、OtisのRSRやデスティネーション・ディスパッチのようなより複雑なスキームと同等、あるいはそれ以上のパフォーマンスを提供することがよくあります。

1台の車両：SCANとLOOK

SCANの変種であるLOOKアルゴリズムは、エレベーターの動きの基準となる期待値として機能します。ロビーからスタートし、保留中の最高のリクエストがある階まで上昇し、その後反転して下降方向のリクエストに対応し、その過程で乗客を乗降させます。これは、反転する前に常に最上階まで進む元のSCAN（または「elevator」）の特許とは異なります。

複数台の車両と基本的な調整

複数の車両がある場合、中央のスケジューラーが各ホールコールを最も近い空いているエレベーターに割り当てます。この「最も近い車両」ルールは、すでに何人の乗客が乗っているか、あるいは車両が呼び出し手に向かっているか、あるいは遠ざかっているかを無視するため、最も近い車両が満員であったり、間違った方向に進んでいたりする場合、最適ではない割り当てにつながる可能性があります。

パフォーマンスの測定：待ち時間の分布

エンジニアは、乗客は長い待ち時間を記憶しているため、平均値ではなく待ち時間のパーセンタイルを使用してアルゴリズムを評価します。p50が1分であることは、全乗車の半分が1分以下で済むことを意味し、p90が2分であることは、乗車の90%が2分以下であることを意味します。この記事のヒストグラムは、さまざまな流量におけるこれらの指標を示しています。例えば、毎分14件のリクエストの場合、LOOKアルゴリズムのp90は約2分ですが、毎分8件のリクエストの場合、p90は改善されます。

朝のラッシュと交通パターン

ピーク時には交通に強い方向性があります。大規模な企業オフィスでは、朝の交通はロビーから上層階への移動が中心であり、夕方の交通はそれが逆転し、昼食時は両方向が混在します。この非対称性により、エレベーターが移動時間の多くを一方通行のフローの処理に費やすため、朝のラッシュは待ち時間の統計において最悪のケースとなります。

よりスマートなエレベーター：OtisのRSR

RSRは、基本的なETA（到着予定時刻）スコアに、ニュアンスを含んだペナルティとボーナスを追加します：

ETA to pickup – 車両がホールコールに到達するまでの時間。
Onboard load penalty – 現在の乗客数に応じて増加。
Same-direction anti-bunching penalty – 同じ方向に移動している別の車両がすでにターゲットとしている階に車両を送ることを抑制する。
Direction-match bonus – すでに希望の方向に移動している車両に報酬を与える。
Idle-nearby bonus – 呼び出し手の2階以内にいる空いている車両を優先する。
Low-load bonus – 乗客が少ない車両を優先する。システムはこれらのスコアを5秒ごとに再計算するため、遅延が発生した場合、最初にエレベーターAに割り当てられた乗客がエレベーターBにルート変更される可能性があります。

LOOK vs RSR：ベンチマーク結果

記事内のシミュレーション結果では、さまざまな流量においてLOOKとRSRを比較しています：

毎分14件のリクエストでは、LOOKとRSRは「待ち時間30秒未満」および「待ち時間90秒未満」の割合において同等の結果を示します。
毎分8件のリクエストでは、RSRが「待ち時間30秒未満」および「待ち時間90秒未満」の数値でわずかに優れた結果を達成します。
流量が増えると、車両が常に満員で全階に停車する場合、RSRの追加ルールはほとんど利益をもたらさないため、LOOKがRSRを上回り始めます。
また、1バンクあたりの車両数が少ない小規模なビルでは、単純さがオーバーヘッドを軽減するため、LOOKがRSRに勝つ傾向があります。これらの結果は、「単純さが複雑さに勝つことが多い」【@heironimus】というコメントを裏付けています。

デスティネーション・ディスパッチ：トレードオフ

デスティネーション・ディスパッチは、ホールコールボタンを、乗客にどの特定のエレベーターに乗るべきかを伝えるフロア・キオスクに置き換えたものです。これにより、スケジューラーは完全な目的地情報を得られますが、硬直性が導入されます。一度車両が割り当てられると、状況が変わっても乗客は別のエレベーターに切り替えることができません。記事では、この柔軟性の欠如により、1バンクに8台以上の車両がある非常に高いビルを除いて、デスティネーション・ディスパッチは従来の上下ボタンよりも待ち時間が悪くなることが多いと指摘しています。この直感に反する結果は、5秒間の再最適化ループに起因します。「キオスクは硬直性を強制し、割り当てられたエレベーターに乗らなければなりません。エレベーターを呼んでから30秒後の世界の状況は大きく変わっているかもしれませんが、システムは適応することができません」【@JoshTriplett】。しかし、デスティネーション・ディスパッチは、交通が同じ階に向かう大きなグループで構成されている場合、それらの乗客をまとめて処理できるため、優れた性能を発揮することがあります【@omoikane】。

フルシミュレーションの洞察

インタラクティブ・シミュレーターを使用すると、ユーザーは階数、車両数、リクエストの流量を変更できます。これらのパラメータを調整することで、LOOK、RSR、およびデスティネーション・ディスパッチのバランスがどのように変化するかを確認できます。例えば、8階建て、4台の車両、毎分18件のリクエストの場合、シミュレーターは各アルゴリズムの待ち時間パーセンテージを表示します。これは、最適なアルゴリズムが特定の建物の交通パターンとエレベーターの容量に依存することを裏付けています。

人的要因と実用的な考慮事項

現実世界のエレベーターのパフォーマンスは、純粋なスケジューリング・ロジック以上のものによって影響を受けます：

ユーザーの行動: 多くの乗客は、到着が早まると誤解して上ボタンと下ボタンの両方を押しますが、これは実際には不必要な停車と混乱を引き起こします【@olex】。
容量検知: 信頼できる満員検知器がない場合、エレベーターは満員であるにもかかわらず全階に停車することがあり、群衆が満員の車両の外で待たされるという苛立たしい場面が生じます【@vova_hn2】。
摩耗と消耗: 待ち時間を減らすための積極的な再配置は、機械的な摩耗を増やす可能性があり、乗客の遅延とメンテナンスコストの間のトレードオフを示唆しています【@taftster】。
心理的な待ち時間: 待ち時間の間に気を紛らわせるものや、進捗を感じさせるものを提供することで、実際の待ち時間が同じであっても満足度を高めることができます【@psadri】。
プリフェッチ戦略: Apple Parkのように、将来の応答時間を短縮するために、呼び出しの後に空いているエレベーターを地上階に移動させる設置例もあります【@ladberg】。これらの要因は、シミュレーションにおける「最善」のアルゴリズムが、実際には乗客にとって最も快適に感じられるものとは異なる場合がある理由を示しています。