エレベーターはなぜ今なお難問なのか — 負荷が高まると単純なLOOKが精緻なRSRを上回る

精緻な最適化は常に勝つのか、それとも負荷が高まるほど単純さが勝つのか — 毎日乗るエレベーターが、その境界線を目の前で見せてくれる。

はじめに — 毎日乗るシステムが、実は解けていないスケジューリング問題である

john.fun/elevators というインタラクティブなエッセイが、その日のHacker NewsでAIを除く記事のうち1位に躍り出た(855ポイント)。テーマは意外にもエレベーターだった。画面の中で直接操作できるシミュレーションによって、複数の昇降機が階を上下しながら呼び出しを処理する様子を見せ、どの配車アルゴリズムが人をより速く運ぶかを実測する。そしてその結果は、多くの読者が予想しなかった方向へ流れていく。

我々はエレベーターを解決済みの問題とみなしている。100年以上存在し、ボタンを押せば来て、たいていはそこそこ速い。しかし少し掘り下げれば、これは典型的な未解決の最適化問題だ。呼び出しは未来を知らぬまま一つずつ到着し、各昇降機は今この瞬間にどこへ向かうかを取り返しのつかない形で決めねばならず、配車を誤れば戻す手段がない。これはまさに「不確実性下のオンラインスケジューリング(online scheduling under uncertainty)」の教科書的な事例である — ディスクヘッドのスケジューリング、ジョブキューの割り当て、配車アプリの車両アサインと同じ一族の問題だ。

エッセイの核心的な発見はこう要約される。オーチスが実際に用いる精緻な独自アルゴリズムRSRが、負荷が高まるほど、教科書にしか出てこないような単純なLOOKに負ける。精緻さが常に勝つのではなく、負荷という条件の前で逆転する、というのだ。本稿はその逆転がなぜ起きるのか、そしてその教訓がエレベーターの外のどこまで移り着くのかを追う。

現象 — 二つのアルゴリズム、そして覆された勝負

まず舞台に上がるアルゴリズムを整理しよう。これらはすべて「複数の階から到着する呼び出しを、限られた台数の昇降機で、取り返しのつかない形で処理する」という同じ問題を、異なる哲学で解く。

SCANとLOOK。 この二つは、OSの授業でディスクアーム(disk arm)スケジューリングとして学ぶ、まさにそのアルゴリズムだ。実際にSCANは別名が「エレベーターアルゴリズム」であるほど昇降機と根が同じである。SCANは一方向に最上階まで一気に掃引しながら途中の呼び出しをすべて処理し、端に達すると向きを反転する。LOOKはその改良版で、進行方向にもう呼び出しがなければ、わざわざ端まで行かずその場で向きを返す。エッセイの表現を借りれば、LOOKは「ほとんどの人が知り、期待するそのアルゴリズム」である — 上へ行く人は上へまとめて乗せ、方向がなくなったら反転する、直観そのままの規則だ。

RSR(Relative System Response)。 オーチスの独自アルゴリズムである。LOOKが規則一つで動くなら、RSRはスコアで動く。呼び出しが入ると各昇降機についてスコアを付け、最良スコアの車を送る。スコアはおおむね「到着予想時間(ETA)+乗車荷重ペナルティ+同一方向の密集(anti-bunching)ペナルティ」のような項で構成され、近くで遊んでいる車や方向の合う車、荷の少ない車にはボーナスが付く。決定的なのは、RSRが5秒ごとに全体を再計算する点だ — 状況が変われば配車を再最適化し、昇降機の間で乗客を再割り当てできる。一見、RSRはLOOKより明らかに賢い。より多くの情報を、より頻繁に反映する。

行き先選択方式(Destination Dispatch)。 三番目の候補はインターフェースそのものを変える。ロビーのキオスクで乗客が乗る前に行き先の階を先に入力すると、システムが同じ行き先どうしをまとめて特定の昇降機を割り当てる。情報が最も多い — 各乗客がどこへ行くかを出発前から知っている。だから理論上は最も賢いはずである。

エッセイの実験の舞台は、この三つを同じ条件で回すシミュレーションだ。測定指標がとりわけ精緻である。単純な平均待ち時間ではなく、待ち時間の分布を見る — 中央値のp50と、上位10%の裾の遅延を表すp90。ここに「30秒以内に昇降機が来る割合は?」「90秒以内は?」といった固定ウィンドウ指標を加える。この設計には一つの観察が下敷きになっている。人は平均を覚えていない。昇降機がいつまでも来なかったあの最悪の瞬間、すなわちp90の経験を覚えている。だから良い配車とは平均を少し縮めることではなく、裾を切り落とすことだ。

そして勝負が覆る。トラフィックが閑散としているときはRSRの精緻さが値をする — 遊んでいる車をあらかじめ配置し、方向を合わせて送り、密集を避けるそのすべての規則が待ち時間を整える。ところが流入率が上がるほど、つまり昇降機が常に満員でほぼすべての階に停まる高負荷領域へ行くほど、LOOKがRSRに追いつき、ついには追い抜く。エッセイの一文を移せば、「流量が高まるほどLOOKが実際にRSRを追い抜き始める」。行き先選択方式はさらに驚きだ。最も多くの情報を持ちながら、いくつもの条件でむしろ悪い成績を出す。情報量と性能が比例しない — これがこのエッセイが投げかける最初の亀裂である。

深層 — 不確実性下のオンラインスケジューリング、そして早期確定の罠

なぜこうした逆転が起きるのか。答えはこの問題が「オンライン(online)」であるという点にある。オフライン最適化はすべての呼び出しを前もって知り、最適解を計算する。しかし現実のエレベーターは、次の1秒に誰がどの階でボタンを押すかを知らぬまま、今の決定を下さねばならない。この条件でアルゴリズムの価値は「今、最適に見える配車」ではなく「未来がどう転んでも大きく損をしない配車」で判定される。アルゴリズム理論が競合分析(competitive analysis)で測る、まさにその性質だ — 未来をすべて知る神託に比べてどれだけマシか。

このレンズで見ると、精緻さが負荷の前で崩れる理由が浮かび上がる。RSRの強みは、状況に合わせてあらかじめ資源を配置することにある。ところが高負荷では配置すべき余剰資源がない。すべての昇降機が満員で、ほぼすべての階に停まる。この領域で最適解は事実上「進む方向へ掃引し続け、載せられるだけ載せる」に収束するのだが、それはまさにLOOKがやっていることだ。RSRが5秒ごとに精緻に計算するスコアは、選択肢が消えた状況では計算コストだけが残り、利得は消える。精緻な最適化は余裕があるときに余裕をうまく使う技術であって、余裕がないときに無い余裕を生み出す魔法ではない。

早期確定(early lock-in)の罠。 行き先選択方式の逆説は、より深い教訓を含んでいる。この方式は乗客を呼び出しの時点で特定の昇降機に確定割り当てする — 「あなたは3号機にお乗りください」。問題はその確定が未来を閉じてしまう点にある。30秒後に世界が変わり、別の昇降機がはるかに有利になっても、すでに割り当てられた乗客は再配置できない。一方、伝統的な上/下ボタン方式は乗客を「上へ行く人」という緩い状態にしか束ねないため、システムは最後の瞬間までどの車に乗せるかを先送りできる。決定を遅く確定するほど、より多くの情報を反映できる。行き先選択方式は情報を早く得る代わりに柔軟性を早く捨てた。そして高負荷では、その柔軟性が情報よりも値打ちがある。

ここでHacker Newsスレッドの議論を一つ引く。ただし直接の引用ではなく、コメントの空気の要約である。スレッドで最も反芻された指摘は、行き先選択方式が「あなたが呼び出した30秒後の世界」に適応できない、というものだった。早期確定が再最適化の扉を閉ざすという洞察を、実際の建物に乗った人々の経験談が裏づけていた。

平均対裾のトレードオフ。 もう一つの軸は、何を最適化するかである。平均待ち時間(p50)を縮める配車と、最悪待ち時間(p90/p99)を縮める配車は、しばしば別の方向を指す。ある規則は多数の待ちを少しずつ縮める代わりに、少数を非常に長く待たせる。人の不満は平均ではなく裾で爆発するので、体感品質を支配するのはp90だ。良いスケジューラは平均を誇らず裾を管理する — これはエレベーターだけの話ではなく、遅延を扱うすべてのシステムの共通戒律である。

トラフィック・レジーム依存性。 決定的に、正解は建物ではなく時間帯と用途によって変わる。エレベーターの交通工学は一日を三つの局面に分ける — 朝の上昇ピーク(up-peak、ロビーから上階へ)、夕方の下降ピーク(down-peak、上階からロビーへ)、そして階間移動が入り混じるオフピーク(interfloor)。オーチス系の文献がいう上昇ピークとは、ロビーから入った乗客が特定の階だけへ向かい、階間の呼び出しがほとんどない時間帯を指し、下降ピークでは遊んでいる車をあらかじめ上階へ上げて待機させる。最適戦略が局面ごとに異なるということは、一つの固定された精緻な規則が常に勝つのは難しいという意味だ。

建物の用途も盤面を覆す。オフィスは朝の上昇ピークと昼の双方向ラッシュが支配し、トラフィックの大半がロビーと個別の階の間を行き来する。ホテルは食事の時間帯に双方向へ流れる。住居用の建物はまた別のリズムを刻む。ここでHacker Newsスレッドのもう一つの指摘が痛い — これも直接の引用ではなく、コメントの空気の要約である。ランダムな行き先で回すシミュレーションは現実に似ていない、というものだ。オフィスのトラフィックはロビーと個別の階の間が大半で、昼休みには同じ階の人々が一緒に降り、一緒に上ってくるバッチング(batching)が起き、むしろ処理を助ける。ランダムな一様分布はアルゴリズムを公平に比較するには良いが、どのアルゴリズムが実際の建物で勝つかは教えてくれない。

最後に、実務の制約が理論を圧倒するという指摘も重い。建物のオーナーは昇降機を「ちょうど必要なだけ」設置する — 一台の設備投資が他のすべてのコストを圧倒するからだ。その結果、真の制約は乗客の快適さではなく処理量(throughput)である。実際の昇降機は重量センサーで乗車荷重を読み、満員かどうかを判断し、頻繁な急発進・急停止は摩耗とエネルギーを増やすため、処理量と摩耗の間にもトレードオフがある。これらすべての制約を載せ、さらにダブルデッキの昇降機や特定の階だけ停まる急行シャフトまで加えれば、「最適アルゴリズム」が何であるかは急速に不透明になる。精緻な規則一つがすべての条件を支配するという絵は、現実では成り立たない。

展望 — エレベーターからロードバランサーへ、移り着く教訓

エレベーターの話が面白い本当の理由は、その教訓が昇降機の外へまっすぐ歩き出てくるからだ。「複数の要求が未来を知らぬまま一つずつ到着し、限られたサーバが取り返しのつかない形で処理し、早期確定が再最適化を妨げる」という構造は、ソフトウェアの至るところにある。

ロードバランサーとジョブスケジューラ。 要求をサーバに割り振るロードバランサーは、エレベーターに乗客を配車する問題と同型だ。最も精緻に見える方針 — 要求ごとに全サーバの負荷を測り最適サーバを選ぶこと — は低負荷では輝くが、高負荷では測るコストだけが残りがちだ。実際、分散システムで広く使われる「2つのランダム選択(power of two choices)」が、素朴な最小負荷選択より安定なのも同じ筋である。早期確定の罠もそのまま移ってくる。要求をキューの先頭で特定のワーカーに釘付けする(スティッキーな)設計は、そのワーカーが遅くなっても再配置できない。遅く確定するワークスティーリング(work stealing)スケジューラが柔軟な理由がここにある。

配車アプリと物流。 ライドヘイリングの車両-乗客マッチングは、行き先選択方式のジレンマをリアルタイムで経験する。乗客を特定の車両に早く確定しすぎると、3分後にはるかに近い車が空いても再マッチングできない。配達・物流のリアルタイム配車も同じ軸の上にある — 早く確定して予測可能性を得るか、遅く確定して柔軟性を残すか。

ではエンジニアが持ち帰る実践的な教訓は何か。第一に、負荷区間を分けて判断せよ。 低負荷で勝つアルゴリズムと高負荷で勝つアルゴリズムは異なりうる。単一の負荷でベンチマークして「これが最高」と結論づけるのは危険だ。第二に、複雑な最適化器を疑え。 精緻さが値をするのはたいてい余裕があるときだ。最適化器の計算・保守コストが利得を上回る負荷区間が必ずあり、その区間では単純な規則のほうが良い。第三に、決定をできるだけ遅く確定せよ。 早期確定は情報を得る代わりに柔軟性を売る。再最適化が値打ちを持つ環境ほど、確定を先送りする設計が強い。第四に、平均ではなく裾を最適化せよ。 体感品質はp90/p99が支配する。

展望を三筋に整理する。楽観的に見れば、こうしたインタラクティブなシミュレーションは「精緻さ=優越」という盲信を剥がし、負荷条件を明示的に問う設計文化を広げる。悲観的に見れば、ベンダーの独自アルゴリズムは依然ブラックボックスで実測ベンチマークは公開されないため、どの方式が実際に良いかは建物ごとのトラフィックデータなしには分からない — ランダムなシミュレーションの勝負を現実と誤読する危険が残る。現実的な中間値は、精緻な最適化と単純な規則を負荷に応じて切り替えるハイブリッドだ。低負荷ではRSR流の精緻さを使い、高負荷が検知されればLOOK流の単純な掃引に切り替える — 実際のエレベーター制御機が上昇ピーク・下降ピーク・オフピークのモードを切り替えるのも、まさにこの発想の実装である。

結論 — 精緻さは余裕の技術であって、負荷の解ではない

リード質問に答えるなら、精緻な最適化は常に勝つわけではない。余裕があるときに勝ち、負荷が余裕を消せば負ける。LOOKがRSRを追い抜くその地点は、アルゴリズムの欠陥ではなく問題の性質である — 高負荷では良い配車が一つに収束し、その収束点に単純な規則が計算コストなしですでに立っているからだ。

エレベーターが100年来の問題でありながら今なお開かれている理由がここにある。正解が一つではなく、条件の関数だからだ。負荷、トラフィック・レジーム、建物の用途、確定の時点、何を最適化するか — これらの軸が作る空間の上で、勝者が席を入れ替える。毎日なにげなく乗るあの箱が、実は我々が築くすべてのオンラインシステムの縮図である。次に複雑な最適化器を導入しようとするとき、一つだけ先に問おう — この精緻さは余裕があるときの技術なのか、それとも本当に負荷の前でも持ちこたえるのか。

出典: