注目★★★★★Hacker News
エレベータの待ち時間を最小化する、意外と複雑なアルゴリズムの正体
30秒で把握
- 1SCAN/LOOK/RSR など段階的に進化したエレベータ配車アルゴリズムにより、待ち時間を最小化
- 2RSR は反バンチング・近接優先・5秒ごとの再最適化で柔軟に対応し利用体験を向上
- 3利用量増加時は単純化が優位、キオスク式より従来ボタン式が効率的という反直感的結果
要約
エレベータのボタン操作から配車まで、一見シンプルに見える仕組みは実は複雑なアルゴリズムに支えられている。1961年に特許取得された SCAN アルゴリズムから始まり、現在は Otis の RSR (Relative System Response) アルゴリズムなど、複数台のエレベータを最適に配車する手法が開発されている。RSR は反バンチング (同じ方向の同じ階への重複配車を避ける)、近くの遊休車を優先する仕組みに加え 5 秒ごとに再最適化を行うことで、待ち時間を削減する。興味深いことに、利用者数が増えると単純な LOOK アルゴリズムが RSR を上回り、また目的地入力キオスク型は従来のボタン式よりも待ち時間が長くなる傾向にある。これは再最適化による柔軟性の価値が、事前情報よりも重要であることを示している。
あなたへの影響
エレベータの配車アルゴリズムは単純さと最適性のバランスを取る典型例であり、サービス設計の現場で「余分な情報より再最適化が効く」という教訓を与えてくれます。
推奨：大規模システムのスケジューリング問題を考える際の参考になるでしょう。