「ボタンのないエレベーター」が逆に遅い？エレベーターとHDDが共有するアルゴリズムの謎

August 1, 2026

アルゴリズムエレベーター解説

データソース：HN + web research · HN

昨日、エレベーターの挙動や制御の仕組みを解説したインタラクティブ記事が、世界最大のエンジニアコミュニティ Hacker News で首位を獲得しました（771 ポイント、198 件のコメント）。多くの開発者が、エレベーターのアルゴリズムをめぐって議論を交わしました。

議論のきっかけは、一見直感に反する観察結果でした。最新のオフィスビルでは、かご内の階数ボタンを無くし、ロビーで事前に行き先階を入力して指定されたエレベーターに乗る「行先予知運行システム（Destination Dispatch）」の導入が進んでいます。しかし、多くのシミュレーション条件下において、この最新システムが従来の「▲▼ボタン」よりも遅いという結果が示されたのです。コメント欄には、エレベーター制御の専門家、ストレージドライバの開発者、ホテルの設備管理者などが集まり、多様な視点から議論が繰り広げられました。

エレベーターは誰もが毎日利用するものですが、その背後にある制御の奥深さはあまり知られていません。元記事は、速度変更が可能なアニメーションや、階数・台数を自由に追加できるインタラクティブなシミュレーションを用いて、各アルゴリズムにおける待ち時間の分布変化を視覚的に解説しています。さらに HN のコメント欄で共有された現実世界の知見を交え、その要点をまとめました。

エレベーター制御の何が難しいのか

まず物理的な制約が存在します。1 台のエレベーターは同時に 1 つの方向にしか進めず、積載量には限界があり、階数が増えるほど選択肢は爆発的に増加します。複数台のエレベーターを同時に効率よく運用するには、誰をどの順番で拾うかという複雑なスケジューリング問題（配車制御）を解決しなければなりません。

さらに、乗客の移動パターンには強い非対称性があります。オフィスビルの朝のピーク時には、ほぼ全員がロビーから上層階へ向かいます。夕方の退勤時にはその逆となり、昼休みには双方向の混雑が発生します。単一のルールセットであっても、時間帯によってパフォーマンスは劇的に変化します。特に朝の混雑時における待ち時間メトリクスの最適化は極めて困難です。

群管理（Group Control）も難易度を上げる要因です。オフィスビルでは通常、5〜6 台のかごが共通の呼び出しボタンパネルを共有しています。乗客が「上」ボタンを押した際、どの号機を向かわせるべきかの判断は、かごの移動、乗り降り、新たなリクエストの発生に応じて刻一刻と再計算されます。1 台の制御ルールはシンプルですが、複数台の協調制御こそが難題なのです。

従来型エレベーターの仕組み

最も広く使われている標準的なアルゴリズムは、1961 年に特許が取得された「SCAN」です。エレベーターはロビーから最上階まで一方向に移動し、途中で呼び出しがあれば停止しながら乗客を拾い、最上階で折り返します。これは路線バスの運行パターンに似ています。コンピュータ科学者が「ハードディスクの磁気ヘッドの移動パターンと全く同じである」と気づいたことから、SCAN は「エレベーターアルゴリズム」とも呼ばれています。

しかし、全員が最上階まで行くわけではありません。そこで登場したのが改良版の「LOOK」アルゴリズムです。LOOK では、現在進んでいる方向にある最も遠いリクエスト階まで到達した時点で折り返します。これは多くの人が見慣れている挙動であり、「方向を維持し、途中で拾い、進行方向にリクエストが無くなれば折り返す」というシンプルな原則に従います。

エレベーターシミュレーションのデモ 図：John.fun のインタラクティブ解説によるエレベーターシミュレーション。出典：john.fun/elevators

エレベーターの性能を評価する主要な指標は待ち時間です。具体的には分布で評価され、p50 は乗客の半数が待つ時間、p90 は 9 割の乗客が収まる待ち時間を示します。平均待ち時間を覚えている人はほとんどおらず、記憶に残るのは「いつまで経っても来なかった」という一部の極端な体験です。そのため、アルゴリズムの最適化では p90 のロングテールを抑えることが最優先されます。

待ち時間分布のデモ 図：John.fun のインタラクティブ解説による待ち時間分布の比較。出典：john.fun/elevators

ここにはトレードオフが存在します。待ち時間を短くすることと、乗車時間を短くすることは必ずしも両立しません。途中で多くの人を拾うために頻繁に停車すると、かご内にいる乗客の移動時間は長くなります。配車アルゴリズムは、待ち時間と乗車時間のバランスを絶妙に取る必要があります。

「賢い」アルゴリズムが必ずしも優れているとは限らない

複数台の制御において、単純なアプローチは「最も近くにいるかごを割り当てる」中央制御です。しかしエンジニアたちはさらに高度な仕組みを追求しました。オーチス（Otis）が開発した RSR（Relative System Response）アルゴリズムは、到着予想時間、現在の積載量、他号機との団子状態（クラスタリング）の回避、進行方向の一致、近隣の空き状態などを総合的にスコアリングし、最も適した号機を割り当てます。この配車判定は 5 秒ごとに再評価され、号機 A が遅延した場合は号機 B へ自動的にタスクが引き継がれます。

RSR には「団子状態防止ルール」が含まれており、別の号機が既にその階に向かっている場合、重ねて割り当てないよう制御されます。オフィスビルで 2 台のエレベーターが同時に到着してドアが開く現象は、この団子状態防止が機能しなかった結果です。スコアリングはリアルタイムで行われ、かごが 1 階移動するごとに評価値が更新されます。

しかしシミュレーション結果は意外な事実を示しました。交通量が高くなると、複雑な RSR よりもシンプルな LOOK アルゴリズムの方が優れたパフォーマンスを発揮したのです。小規模な建物や基数が少ない環境でも、LOOK が勝利する傾向が見られました。ルールを増やせば速くなるわけではなく、単純さを保つことが正解となるケースもあります。アルゴリズムの複雑さとパフォーマンス向上の間には、具体的な運用シナリオが存在することを示しています。

ハードディスクは「丸められたエレベーター」である

コメント欄で特に注目を集めたのが、「SCAN アルゴリズムはコンピュータのハードディスクにおける磁気ヘッドのスケジューリングアルゴリズムそのものである」という指摘です。Wikipedia でも「エレベーターアルゴリズム」と「SCAN」は同一の概念として記載されています。SCAN は元々、ディスクのリード／ライト要求を処理するために考案されたものでした。

メカニカルハードディスク内では、磁気ヘッドがプラッタ上のトラック間をシークしてデータを読み書きします。これはエレベーターが階数を移動して乗客を運ぶ構造と全く同じです。ディスク表面に分散したリクエストに対し、ヘッドが一方向にスキャンしながら途中の要求を処理し、端まで到達すると逆方向にスキャンします。HDD のシーク動作はマシン全体で最も低速な物理動作の一つであり、スケジューリングによって節約できるのはこのメカニカルな時間です。あるエンジニアは「ハードディスクとは、丸められたエレベーターに過ぎない」と表現しました。

コンピュータサイエンスの教科書において、SCAN は I/O スケジューリングの古典的テーマです。1961 年のエレベーターの特許と OS の教科書は、全く同じ発想に基づいています。ドナルド・クヌース（Donald Knuth）も『The Art of Computer Programming』でコルーチンを解説する際、エレベーターのシミュレーションを例に挙げました。人間を運ぶかデータを運ぶかの違いであり、制御ロジックの本質は共通しています。

現在、ソリッドステートドライブ（SSD）の普及によってシーク時間がほぼゼロになり、HDD 向けの SCAN アルゴリズムは徐々に役目を終えつつあります。しかし、エレベーター内では今も毎日稼働し続けています。1961 年の特許から始まった同じアイデアが、機械工学とコンピュータサイエンスの双方にまたがって息づいています。

おわりに

エレベーターがなかなか来ないとき、それはあなたを無視しているのではなく、裏で多様な変数を考慮しながら懸命に計算している最中なのかもしれません。次にエレベーターを待つ機会があれば、ボタンの向こう側で数世代にわたるエンジニアたちがアルゴリズムの高速化をめぐって議論を重ねてきたことに思いを馳せてみてはいかがでしょうか。そしてその議論の一部は、今なお結論が出ていないのです。