Як алгоритми ліфтів вирішують, яка кабіна відповість на виклик

Стаття, опублікована на john.fun/elevators, досліджує те, що відбувається між натисканням кнопки виклику та прибуттям кабіни, і порівнює алгоритми, які вирішують, який ліфт обслуговує якого пасажира. Її висновок суперечить інтуїції: у багатьох будівлях найпростіші правила дають найкоротше очікування.

Одна кабіна: SCAN і LOOK

Найпростіший алгоритм, SCAN, був запатентований 1961 року. Кабіна починає з вестибюля, піднімається до найвищого поверху, потім розвертається і спускається, забираючи та висаджуючи пасажирів дорогою. LOOK — це варіант, який насправді відчуває більшість пасажирів: кабіна піднімається лише до найвищого виклику і після цього повертає.

Оцінювання кабін за допомогою RSR

Коли кабін кілька, найпростіша система використовує центральний диспетчер, який призначає кожен новий виклик найближчому ліфту. Складніший підхід — Relative System Response (RSR) від Otis: він нараховує кожній кабіні бал за те, наскільки вона придатна для підбору пасажира, і чим менший бал, тим краще. Бал поєднує орієнтовний час до прибуття до пасажира, штраф за завантаженість кабіни, штраф за скупчення кабін у тому самому напрямку, бонус за збіг напрямку, бонус за вільну кабіну поблизу та бонус за низьке завантаження.

RSR також переоптимізує рішення кожні п'ять секунд, тож пасажир, спочатку призначений одній кабіні, може бути переведений на іншу, якщо перша затримується. За словами статті, саме цей крок перерозподілу підтримує потік пасажирів.

Вимірювання очікування і чому простота виграє

Автор наполягає, що час очікування слід оцінювати як розподіл, а не як середнє: p90 у дві хвилини означає, що 90 відсотків пасажирів чекають дві хвилини або менше, а p50 в одну хвилину — що половина очікувань триває менше хвилини. Пасажири пам'ятають найгірші випадки, а не середнє, тому «хвіст» розподілу має значення.

Наведені в статті тести показують, що зі зростанням пасажиропотоку LOOK може перевершувати RSR: коли кабіни заповнені й зупиняються майже на кожному поверсі, додаткові правила важать менше. LOOK також зазвичай виграє в RSR у невеликих будівлях із меншою кількістю кабін у групі. Розподіл за призначенням — кіоски, які підказують, у яку кабіну сідати, ще до входу — загалом гірший для часу очікування, ніж традиційні кнопки вгору й вниз, окрім дуже високих будівель із вісьмома або більше кабінами в групі. Причина в тому, що кіоск нав'язує фіксоване призначення, тоді як звичайна система може переоптимізувати рішення кожні п'ять секунд. На сторінці є інтерактивна симуляція з відкритими параметрами.