- エレベーターの運行は単純な呼び出し応答ではなく、車両数、乗客の流れ、積載量、移動方向をあわせて考慮する配車最適化問題である
- 単一車両向けのSCANは最上階で方向を変えるが、LOOKは実際に要求のある最も高い階で折り返すため、一般的な運行イメージにより近い
- 複数車両を扱うRSR(Relative System Response) は到着予想時間や積載量などをスコア化し、5秒ごとに配車を再最適化して、遅延した車両の乗客を別の車両へ振り替えられる
- 車両が常に満員だったり、各階で停止するほど乗客流量が多く車両数が少なかったりするなら、複雑なRSRより単純なLOOKのほうが優れることがある
- 目的階を事前入力する目的地配車(Destination Dispatch) はより多くの情報を得られるが、指定車両を変更しにくいため、超高層・車両8台以上のような一部のケースを除けば、従来の上下ボタン方式より待ち時間が概ね長くなる
単一車両はどこで方向を変えるのか
- 1961年に特許を取得したSCANは、ロビーを出発して最上階まで上がった後に方向を変えて下り、移動経路上の乗客を乗せ降ろしする
- LOOKは最上階まで無条件に行かず、要求された最も高い階まで運行してから折り返す
- 一般的に人々が知っていて期待するエレベーターの運行方式はLOOKに近い
複数車両の基本配車
- エレベーターが複数台あるなら、どの車両がどの呼び出しを担当するかを調整する必要がある
- 基本システムでは中央スケジューラが各車両の停止階を指定し、新しい呼び出しを最も近い車両に割り当てる
- しかし単純な距離ベースの配車だけでは、近い車両が満員である状況などを十分に反映しにくい
待ち時間を評価する方法
- エレベーターアルゴリズムの最も直感的な評価指標は、呼び出しから車両到着までの待ち時間である
- 簡単には、車両が30秒または90秒以内に到着した割合を測定できる
- より厳密に評価するには、数千回の運行の待ち時間を集めて分布とヒストグラムを確認する
- p90が2分なら、乗客の90%が2分以内に待ったことを意味する
- p50が1分なら、呼び出しの半分で車両が1分以内に到着する
- 乗客は平均待ち時間より、妙に長く待たされたp90のケースをより強く記憶する傾向がある
時間帯によって変わる乗客の流れ
- 大型オフィスビルの朝は、ロビーから上層階へ向かう移動が大半を占める
- 夕方は退勤者により、上層階から下へ向かう流れが優勢になる
- 昼休みには上りと下りが混在し、それ以外の時間には階と階の間の移動が多い
- 待ち時間の分布は時間帯と交通パターンによって大きく変わり、とくに朝の通勤時間の統計が悪い
RSRはどの車両を選ぶのか
- OtisのRSR(Relative System Response) は、各車両が乗客を乗せるのにどれだけ適しているかをスコア化し、スコアが低いほど適している
- 乗車スコアは複数の要素を組み合わせて計算する
- 呼び出し階までの到着予想時間
- 乗車中の乗客数に応じた積載ペナルティ
- 同じ方向で同じ階へ向かう車両がすでにある場合に適用するクラスタリング防止ペナルティ
- 移動方向一致ボーナス
- 呼び出し階から2階以内にいるアイドル車両ボーナス
- 低積載量ボーナス
- クラスタリング防止(anti-bunching) は、別の車両がすでに同じ方向で同じ階へ向かっているなら追加割り当てを抑制する
- RSRは5秒ごとに全体配車を再最適化する
- 車両Aが遅延すると、もともとAが乗せる予定だった乗客を車両Bに再割り当てできる
- この継続的な再最適化が、乗客の流れを円滑にする鍵である
LOOKとRSRの性能差
- 待ち時間分析ツールを使えば、LOOKとRSRの30秒・90秒以内到着率を比較できる
- 乗客流量が増えるほど、LOOKがRSRを上回り始める
- 車両が常に満員で、すべての階に停止するなら、RSRの追加ルールがもたらす効果は小さくなる
- 車両グループあたりのエレベーター台数が少ない小型ビルでもLOOKがRSRより良い傾向があり、単純な方式のほうが適している可能性がある
- 待ち時間だけでなく、乗車後に目的階までかかる移動時間も測定できる
- LOOKとRSRはこの指標でも異なる特性を示すが、具体的な比較は扱わない
目的地配車が、より多くの情報を持ちながら不利な理由
- 目的地配車は、各階のキオスクで目的階を先に入力すると、乗るエレベーターを指定する方式である
- 最適化システムは車両到着前に乗客ごとの目的地をすべて把握できるが、待ち時間は一般に従来の上下ボタン方式より長くなる
- 非常に高い建物で、車両グループあたりのエレベーターが8台以上ある場合のように、キオスク方式が有利な例外もある
- 性能低下の核心原因は、配車の硬直性である
- 従来方式では5秒ごとに車両経路と乗客割り当てを再最適化できる
- 目的地配車では、乗客は最初に指定された車両に乗らなければならない
- 呼び出しから30秒後に運行状況が変わっても、指定車両を柔軟に変更できない
- 目的地という追加情報の利点より、再配置の柔軟性を失う不利益のほうが大きい
シミュレーションの調整項目と範囲
- 全体シミュレーションでは、階数、車両数、分あたり乗客流量を調整し、30秒・90秒以内到着率を確認できる
- 実際のエレベーターアルゴリズムにはさらに多くの考慮事項があり、ここで扱った範囲は全体領域の一部にすぎない
- 呼び出しボタンの入力は伝達されるが、エレベーターは複数の運行条件をあわせて計算するため、すぐに到着しないことがある
1件のコメント
Hacker Newsの意見
この半世紀のうちおよそ半分の期間、エレベーターはコンピューターなしでリレーだけで制御されており、こうしたアルゴリズムも配線された論理回路で実装されていた
回路図などの興味深い詳細は、Otisの古い特許で見ることができる
高校のコンピューターサイエンスの授業で、複数のエレベーターアルゴリズムのシミュレーションを個人プロジェクトとして実装したことがある
回転式ハードディスクは、垂直方向ではなくスピンドルの周りを巻く非常に長いエレベーターのようなもので、SCANは実際にディスクスケジューリングアルゴリズムである: https://en.wikipedia.org/wiki/Elevator_algorithm
行き先の階をランダムに設定していたため、行き先予約配車が全体的によくないという結果になったのではないかと気になる
実際の建物では、地上階以外の人の大半は地上階へ向かうし、地上階では同じ階で働く人たちが昼休みに一緒に出かけて、同じ階へ一緒に戻る傾向がある。行き先予約配車は同じ目的地の大きな集団をまとめて乗せられるので、こうしたパターンに有利である
一部のホテルのキオスク方式は、朝食の混雑時間帯に合わせてユーザーインターフェースも変える
昼食に行く人や戻る人のクラスタ効果も実際に存在し、朝や夕方よりも昼間に顕著である
オフィスやホテルがこの方式に切り替えた後、待ち時間が大きく減ったという記事もある
最近訪れた新築の建物でもこの方式を使っていた。大学時代に電気工学を専攻していたルームメイトは、呼び出しボタン、モーター、位置検知用の黒い四角が表示された透明な円盤をブレッドボードにつないでエレベーター回路を作っていたが、おそらく単純なアルゴリズムだった
エレベーターのスケジューリングを初めて知るなら、このゲームを勧めたい: https://play.elevatorsaga.com/
iOS・Android向けのエレベーター制御・自動化ゲームSky Lobbyを開発しながら、この問題をかなり考えた
プレイヤーが期待する動きに最も近いLOOKに似たアルゴリズムを採用しつつ、選択が曖昧なときは長く待っている階を優先して、ゲームで重要なp90を改善した。しかし、2階を同時に担当するダブルデッキエレベーター、シャフト間の乗り換え階、急行シャフトまで加わると、最適あるいは最も直感的なアルゴリズムはずっと不明確になる。実システムではなくゲームなので、十分に良いヒューリスティクスを見つけ、気に入らないときはプレイヤーが運行計画を手動で上書きできるようにしたところ、ほとんどの人は満足していた
エレベーターを待つたびに、乗客の乗車から目的地到着までの待ち時間を最小化するアルゴリズムを作るのがどれほど厄介かを考える
ときどき、これを実装した人たちは、わざともっと長く待たせる邪悪なサディストなのではないかと思うことさえある
大きなカンファレンスの翌朝はみんな下へ降りたがるのに、満員のエレベーターが全階に律儀に止まっていた。10人乗りのエレベーターがすでに10フロア分の呼び出し客を乗せているなら、各階で「空きがないですね、次に乗ります」を繰り返す代わりに、そのまま地上階へ直行して5分節約できるべきだ。特に2階の移動が不自由な人が飛行機に乗らなければならないなら深刻な問題になる
全エレベーターの位置と動きを見ると、スケジュールは驚くほど詰まっている。ロビーでは待ち時間が果てしなく感じられるが、配車の観点では活動はひっきりなしに続いており、建物の利用時間中はエレベーターはほとんど遊んでいない。状態パネルを見ているだけでも面白い。さらに、エレベーター整備士が「朝早く会おう」と言うと、たいてい午前4時ごろを意味し、人が出勤する前に作業を終えようとする
エレベーターは高価で、建物オーナーは衝動的に過剰投資しないので、通常は予想需要を処理できる程度、時にはそれ以下の最小台数のエレベーターしか設置しない
4台のエレベーターの上にそれぞれ予定停止階が表示され、待っている間にもエレベーターと階の割り当てを変えながら音で知らせる。最適配車を可能にするための機能のように見える
エレベーターで最大の問題はアルゴリズムより、行き先の方向に合わせて上・下の呼び出しボタンを押すという概念を理解していない人たちだ
「早く来る」と言って両方のボタンを押すと、半分は逆方向へ先に行くことになり、すでに乗っている人にも不要な停止を追加してしまう
たぶん偽のロード表示の心理に近い。到着時間が分からないまま待つのは退屈でいらだつが、逆方向でも動いているエレベーターに乗れば進んでいる感じがする。結局、より長くかかっても、何かが起きている状態の方がましに感じられる
一方で上り需要が少ないなら、先に上へ乗ってから端まで往復した方が、空きが出るのを期待して待つより合理的な戦略になりうる
このときは上・下ボタンを両方押す行動は愚かではなく論理的だ
アルゴリズムの性能とは別に、人々の待ち時間の知覚心理も重要だ
何もせずに待つと非常にいらだつが、同じ時間でも何かをしていれば進展と感じられ、不満が減る。空港でも、乗客をゲートから手荷物受取ベルトへまっすぐ行かせて最初のバッグが出るまで待たせる代わりに、わざと長く回り道する動線にしたところ、総所要時間は同じでも満足度が上がった例がある
複数のエレベーターアルゴリズムでは、全体の摩耗と保守コストはあまり議論されないことが多い
動きが増えれば、作動油の交換や部品故障が早まる可能性がある。効率的なアルゴリズムは時間帯や他のエレベーターの位置に応じて事前再配置を行うこともあり、たとえば1台が下りてくるなら別の1台を上へ送ることがある。需要シグナルベースのアルゴリズムはこうした動きを最小化する。待ち時間を増やしてでも保守を減らすバランスが重要で、コストを負担する建物オーナーは乗客の待ち時間をそれほど重視しない可能性が高い