エレベーターのボタンを押し、表示パネルの数字が一つずつ変わるのをじっと見つめる。「今日は運が悪いな」と思うかもしれない。しかし、それは運の問題ではなく、100年以上前から研究され続けている数学の最適化問題数值そのものだ。
昨日（8月1日）、ウェブ開発者の John Allsopp 氏が制作したインタラクティブなエレベーターアルゴリズム解説が技術コミュニティ Hacker News で首位を獲得し、本日も Lobsters で活発に議論されている（52ポイント、6件のコメント）。驚くようなニュースを伝えるものではなく、複雑なエレベーターの制御ロジックを直感的に操作できるシミュレーターにまとめた作品だ。多くの人の関心を集めたのは、誰もが一度は抱く疑問に答えているからだろう。「ボタンを押したとき、エレベーターは本当にこちらの呼び出しに気づいているのか？」
気づいている。ただ、考慮すべきことが多すぎるのだ。
エレベーターが最適化しているもの：平均値の罠
まず問いを立ててみよう。エレベーターの配車が優れているかどうかは、どう評価すべきだろうか？
直感的な答えは「平均待ち時間」だ。しかし、何千回もの乗車データを分布図にプロットしてみると、平均値という数字が人を惑わすことがわかる。John 氏のシミュレーションでは2つの指標が提示されている。p50（中央値）は1分、つまり半数の人が1分以内に乗車できる。一方、p90は2分で、90%の人が2分以内に乗車できることを意味する。
p50とp90の間のわずか1分の中に、エレベーター業界の重要な秘密が隠されている。人間の脳は平均値を記憶せず、最も惨痛だった体験だけを鮮明に記憶するのだ。上位10%の長い待ち時間は、実際の割合以上に強い印象を記憶に残す。そのため「エレベーターがなかなか来ない」という感覚は、統計的分布と人間の認知バイアスが作り出す錯覚であることが多い。実際には、半分以上のケースで1分以内に到着している。
エンジニアリング上のトレードオフも複雑だ。「平均待ち時間の短縮」「最大待ち時間の抑制」「消費電力の削減」という3つの目標は互いに相反する。最も近くにいる乗客の元へエレベーターを最優先で派遣すれば平均待ち時間は最短になるが、極端なケースでは別の階の乗客が5分以上待たされることになる。平均時間をわずかに犠牲にして「永久に来ない」ような極端な待ち時間を排除する——これが多くのオフィスビルで採用されている現実的な選択だ。無料のランチは存在しない。エレベーター会社は、乗客が気づきにくい最適なメニューを選んでいるに過ぎない。
図：原文で千回以上のシミュレーションによって描かれた待ち時間分布のデモ。出典：john.fun
最も古いルール：端まで行って、折り返す
自動アルゴリズムが登場する前、エレベーターの中には人間が乗っていた。20世紀半ばまで「エレベーターガール（運転士）」という職種は一般的であり、ドアを開閉し、行先階を尋ね、手動で目的地へ操作していた。やがてエレベーターが自動化され、運転士が姿を消すと、ルールは機械に委ねられ、配車問題は「人」から「数学」へと変わった。
最初期の自動ルールは驚くほどシンプルだった。1961年に特許を取得した SCAN アルゴリズムは、エレベーターがロビーを出発して最上階まで一方向に進み、途中で乗降を処理しながら進行し、頂点に達すると反転して下り、これを繰り返す仕組みだ。その後、「リクエストがないのにわざわざ最上階まで行く必要はない」と改良されたのが LOOK アルゴリズムで、呼び出しがある最高階に達した時点で折り返す。今日、ほとんどの人はこの挙動を当然のものとして受け止めており、それが「アルゴリズム」であることすら意識していない。
このロジックにはコンピュータサイエンスにおける有名な親戚が存在する。ハードディスクドライブ（HDD）のヘッド制御だ。磁気ディスク上でデータを検索する際、磁気ヘッドはまったく同じ動きをするため、情報科学ではこのアルゴリズムをそのまま「エレベーターアルゴリズム（Elevator algorithm）」と命名した。60年以上前の特許が、今なおハードディスクと建物のエレベーターシャフトの両方で稼働している。シンプルなルールの寿命は、大半の最新ソフトウェアよりもはるかに長い。
しかし、単体エレベーターのルールだけでは朝のラッシュに対応できない。朝9時のオフィスビルを想像してほしい。数百人が同時に1階ロビーで上行きボタンを押す。システムが単純にすべてのエレベーターをロビーに集めてしまうと、3台が同時にドアを開け、半分空席のまま一緒に上昇するという非効率が生じる。配車制御装置は一見「不合理」に見える動作を行わなければならない。例えば、空いているエレベーターを迂回させて別の階の乗客を拾わせるのだ。15階でボタンを押したあなたの前をエレベーターが通り過ぎていくとき、システムは呼び出しを聞き逃したわけではなく、全体に最適化された計画を実行しているのである。
図：原文トップページのインタラクティブデモ——4階建ての建物を往復する1台のエレベーター。25倍速で再生可能。出典：john.fun
複数台の連携：5秒ごとの再スコアリング
エレベーターの台数が増えると、問題は一気に複雑化する。「どのエレベーターが誰を迎えに行くべきか？」
現代のエレベーター群管理システム（例えばOtis社の RSR アルゴリズム）では、スコアリング方式が採用されている。各エレベーターに対して、予想到着時間、現在の乗車人数、他のエレベーターとのクラスタリング回避、進行方向の整合性、付近で待機中か否かなどを総合した「割り当てスコア」を算出し、最もコストの低いエレベーターが指名される。このシステムの巧妙な点は、撤回と再計算を行う点にある。5秒ごとに建物全体の状況を再計算し、担当エレベーターが途中の乗降で遅延した場合、その呼び出しは即座に別のエレベーターへと引き継がれる。
John 氏のシミュレーションは反直感的な結論を導き出している。利用者が非常に多いピーク時には、複雑な RSR よりもシンプルな LOOK ルールの方が高いパフォーマンスを発揮することがあるのだ。また、小規模な建物や基数が少ない場合もシンプルなルールが勝る。「時にはシンプルに保つことが最善である」——この平易な一言こそ、本稿を通じて最も価値のある教訓と言えるだろう。
行先予知制御：情報が増えても遅くなる理由
近年、ハイグレードなオフィスビルで「行先予知制御（Destination Dispatch）」の導入が進んでいる。エレベーターに乗る前にロビーの液晶端末で行先階を選択すると、画面に「3号機でお待ちください」と表示される仕組みだ。一見すると非常にスマートで、乗車前に全員の目的地を把握できれば、より最適な運行計画が立てられるように思える。
しかし、シミュレーション結果はその直感と逆を示した。大多数のシナリオにおいて、行先予知制御の平均待ち時間は従来の「上下ボタン」方式よりも悪化していたのだ。このシステムが優位に立つのは、8台以上のエレベーター群を備えた超高層ビルなどの特定環境に限られる。理由は明確だ。従来のシステムが持っていた「5秒ごとに柔軟に再最適化する機能」が、画面上で「指定の号機に乗ってください」と案内した瞬間に固定化されてしまうからだ。ボタンを押してから30秒後、ビル内の状況が変化しても、システムは割り当てを変更することができないのである。
Lobsters のエンジニアコミュニティでも実社会での不満が共有されている。ユーザーの vbernat 氏によれば、行先予知制御は全員が端末で行先を正しく登録することを前提としているが、焦ったユーザーが何度もボタンを押すことで、同じ階に2台のエレベーターが同時に派遣されるような誤作動が起きるという。Flask フレームワークの作者である mitsuhiko 氏も、現実には乗り間違えや乗り遅れが多発していると指摘する。一方で、セキュリティカードと連動させた運用では、タッチした瞬間に乗るべき号機が指定され、出社ラッシュ時にスムーズに移動できるという高評価もある。ただし、その代償として退勤時の下り方向で数分間待たされるケースもある。システムが朝の通勤ラッシュの最適化に全リソースを割いているからだ。
ここには思考を深めるべきポイントがある。「システムに多くの情報 access を与えること」と「その情報を有効に活用できること」は同義ではない。全体の最適解は、個人の「自分のもとへすぐ来てほしい」という要求と往々にして衝突する。配車アルゴリズムの計算において、個人にとっての1分と、ビル全体のアグリゲートされた時間はまったく異なる価値を持っているのだ。
なぜ遅く感じるのか：待ち時間の心理学
最後に豆知識を紹介しよう。エレベーターメーカーは昔から「体感待ち時間」の研究を重ねてきた。心理学によれば、人間は退屈な状態ほど時間を長く感じる傾向がある。伝統的な解決策として、エレベーターホールに大きな鏡を設置する手法があり、多くのビル管理者が採用して効果を上げている。エレベーターを待つ際の焦燥感の半分はアルゴリズムによってもたらされるが、残りの半分は人間の脳自体が作り出しているのだ。
また、興味深い現象がある。「エレベーターの上りと下りの回数は同じはずなのに、なぜいつも逆方向に移動しているエレベーターばかり目につくのか？」という疑問だ。その一因はピーク時の運行にある。満員の車輌は通過中の階をそのままスキップするため、目の前を通り過ぎていく満員のエレベーターばかりが強い記憶として刷り込まれるのである。
最初の問いに戻ろう。「エレベーターはボタンの呼び出しに気づいているのか？」答え言えす。ただ、数百人の目的地、定員、消費電力、フェアネスを考慮し、5秒ごとに再計算を行っている。次にエレベーターを待つ際、もし別の階へ向かってしまったとしても、それは建物全体のために全体最適化を実行している分散制御システムなのだと考えてみてほしい。その計算シートには、あなたにとっての1分と、ビル全体の人々の時間が等しく刻まれている。
参考リンク：
- John Allsopp：Elevators（インタラクティブ解説）
- Lobsters 議論 (s/jxqf1w/elevators)
- Wikipedia：Elevator algorithm
- Signal v. Noise：Defining the problem of elevator waiting times
- Scientific American：The reason why elevators feel slow
