効率的なエレベーターのアルゴリズムは？

エレベーターの輸送効率はエレベーターの動き方を定めるアルゴリズムによって左右されます。そんなエレベーターのアルゴリズムごとの効率の差を分かりやすく確認できるシミュレーターがジョン・ヘリック氏によって公開されています。

Elevators
https://john.fun/elevators

シミュレーターは上記のリンク先の最下部に用意されています。

これがエレベーターのシミュレーターです。上部に「30秒以内に乗車できる確率」と「90秒以内に乗車できる確率」が表示されます。

操作可能な項目は「乗客パターン」「階数」「カゴ数」「1分当たりの乗車人数」「倍速」「アルゴリズム」の5カ所。

乗客パターンは「朝(出勤時間)」「ランチタイム」「午後(帰宅時間)」「階間移動」の4種類。朝は1階から上階に向かう人が多く、ランチタイムは出入りが同等で、午後は上階から1階に向かう人が多くなります。

アルゴリズムは「LOOK」「RSR」「Destination Dispatch(行先予約方式)」の3種類です。「LOOK」は「呼ばれた最高階もしくは再下階まで行ってから折り返す」という一般的なエレベーターアルゴリズムで、「行先予約方式」は「各階のエレベーターホールにある端末で行先階を指定してエレベーターを呼び出す」という一部のエレベーターで採用されているアルゴリズムです。

RSRは特殊なアルゴリズムで、各エレベーターの「スコア」を算出して担当するエレベーターを選択します。スコアは「到着までの時間 ＋ 乗員ペナルティ ＋ 別のエレベーターと行先がかぶる場合のペナルティ － 進行方向が合っている場合のボーナス － 近くに待機中のエレベーターがある場合のボーナス － 乗員が少ない場合のボーナス」で算出されます。

「8階建て」「4台のエレベーター」「毎分18人乗車」「朝(1階から上階に向かう人が多い)」という条件でのシミュレーション例が以下。LOOKアルゴリズムだと30秒以内に乗車できる確率は66％、90秒以内に乗車できる確率は99％となりました。

RSRだと30秒以内乗車率は72％に低下。

行先予約方式だと30秒以内乗車率は48％、90秒以内乗車率は92％に低下しました。この条件だと行先予約方式は適していないようです。

エレベーターを6台に増やしてみました。LOOKだと30秒以内乗車率は94％、90秒以内乗車率は100％。

RSRだと30秒以内乗車率が96％に増加。

行先予約方式だと30秒以内乗車率が77％になりました。

実際のシミュレーターではアニメーション付きで各アルゴリズムの特徴を理解できるので試してみてください。