Складний алгоритм: як працюють ліфти

Ти підходиш до ліфта, натискаєш на кнопку зі стрілкою, і настає очікування. Довге очікування. Дуже довге...

Насправді існує вагома причина, через яку кабіни ліфта одна за одною відправляються нагору, не зупиняючись на твоєму поверсі. Це не тому, що вони тебе не люблять. Щоразу, коли ми натискаємо на кнопку, ліфт вирішує не найпростішу задачу. Система повинна вибрати, коли і яку кабіну направити на наш поверх. Крім того, потрібно вирішити, чи варто ліфту піднятися нагору з п'ятого поверху і забрати пасажирів на сьомому, перш ніж опуститися до нас на перший. А ще потрібно врахувати, хто вже прочекав найдовше і який маршрут буде найбільш ефективним.

Ця система вимагає детальної розробки і тонкого налаштування, і не можна не захоплюватися копіткою роботою інженерів, які створили її.

Раніше було простіше

Порядок руху найперших ліфтів з електронним управлінням визначали люди. Оператор, що знаходиться в кабіні, направляв ліфт вгору і вниз за допомогою дроселя і зупиняв рух, як тільки він або диспетчер бачили нового пасажира. Однак ліфтери робили помилки, вимагали гідних оплати та умов праці, тому вже до початку 1950-х їх повсюдно замінили електронними перемикачами.

Щоб ліфт міг сам керувати своїм рухом, інженерам потрібен був алгоритм, що визначає, в яких випадках куди кабіні потрібно направлятися. Найпростіший спосіб - рухатися вниз і вгору із зупинками на зазначених поверхах у встановлені часові проміжки. Для пасажира це виглядає як поїздка електричками з пересадками: спочатку йдеш на десятий поверх, куди в 15:10 набуває ліфт, наступний до пересадочного поверху, а там вже шукаєш, як дістатися на потрібний. Про ефективність говорити не доводиться: в години пік пасажири змушені витрачати час, чекаючи, коли ліфт відправиться за розкладом, а в той час, коли майже ніхто ним не користується, кабіни даремно витрачають електроенергію, порожніми курсуючи між поверхами.

До 1965 року інженери зупинилися на знайомій кожному з дитинства моделі: пасажир натискає на кнопку виклику, і на його поверх прибуває кабіна. Але ось завдання: як алгоритму зрозуміти, куди направляти кабіну, якщо її викликають відразу на декількох поверхах?

Болісне сподівання

Яка повинна бути ідеальна система координації ліфтів? Чи повинен ліфт приїхати спочатку до того пасажира, який чекає найдовше? Або краще направити кабіну до найближчого поверху виклику? Як знайти баланс між швидкістю подачі ліфта і витратою електроенергії?

Зрозуміло, що потрібно оптимізувати час на провезення пасажирів. Але як розставити пріоритети? Якщо одному пасажиру доведеться чекати не 20 с, а хвилину, перш ніж перед ним розкриються двері ліфта, наскільки це для нього буде втомливіше? Втричі? А може, в шість чи сім? Навіть для такого нехитрого завдання немає чітких ввідних даних.

Іноді навіть краще, якщо сама поїздка в ліфті займе більше часу. Представимо два сценарії: у першому ліфт приїжджає через 10 з після натискання кнопки виклику, а сама поїздка до потрібного поверху займає хвилину. За другим сценарієм ви чекаєте ліфт 30 с і їдете теж 30 с. Більшості людей очікування здається настільки нестерпним, що вони вибрали б перший варіант, нехай і доведеться витратити зайві десять секунд. Виходячи з цього, інженери програмують алгоритм таким чином, щоб він враховував «коефіцієнт втомливості», замість того щоб просто мінімізувати час поїздки.

Не варто забувати і про фізичні обмеження ліфтів: у них є межа швидкості, а проміжок часу, щоб прорахувати наступний крок, - не більше 1-2 с. Крім того, у ліфта немає права на помилку: якщо він проїде потрібний поверх без зупинки, пасажиру це не сподобається. Хто знає - раптом незадоволений пасажир від злості рознесе панель управління? Грамотна комп'ютерна система повинна знайти ідеальний баланс між можливостями ліфта і цілями його користувача, навіть якщо тому треба було бути нагорі десять хвилин тому.

Алгоритми

У багатьох ліфтах все ще використовується самий ранній і простий "