Все мы знаем, как бесит ждать лифт, который словно игнорирует кнопку. Статья разбирает алгоритмы, управляющие кабинами, — от простейших до тех, что используются в современных небоскрёбах.
Простейший алгоритм — SCAN, запатентованный в 1961 году. Лифт идёт от вестибюля до самого верхнего этажа и обратно, подбирая всех по пути. Если он разворачивается на последнем запрошенном этаже, а не едет до крыши, это LOOK — именно так, по мнению автора, большинство людей представляет себе работу лифта. Когда кабин несколько, появляется центральный планировщик, распределяющий вызовы по ближайшим машинам.
Качество оценивают не по среднему времени ожидания, а по распределению. Главная метрика — p90: 90% пассажиров ждут не дольше этого порога. Люди запоминают именно те случаи, когда лифт ехал вечность, а не среднюю поездку. Хуже всего статистика в утренний час пик, когда толпа штурмует верхние этажи из лобби.
Умный алгоритм RSR (Relative System Response) от Otis считает для каждой кабины взвешенный score. Он штрафует за загрузку, если в ту же сторону на тот же этаж уже едет другая кабина (антискучивание), и даёт бонусы за бездействие рядом с пассажиром, попутное направление и низкую занятость. Но ключевая фишка — пересчёт каждые 5 секунд: пассажира могут без его ведома перебросить на другой лифт, если первоначальный задержится. Именно эта непрерывная переоптимизация сглаживает трафик.
Однако хитрее — не всегда значит лучше. При очень высоком пассажиропотоке, когда кабины забиты и останавливаются на каждом этаже, дополнительные правила перестают помогать, и LOOK начинает обгонять RSR по времени ожидания. В небольших зданиях с малым числом лифтов в группе простой LOOK тоже часто оказывается выигрышнее. Для полноты картины можно смотреть и на длительность самой поездки, но это уже другая тема.
Неожиданный поворот — система Destination Dispatch с киосками на этажах, где вы заранее вводите нужный этаж, а терминал указывает, какой кабины ждать. Зная точный пункт назначения каждого, планировщик, казалось бы, должен сократить ожидание. На практике же для большинства зданий такие киоски только ухудшают время ожидания по сравнению с обычными кнопками «вверх/вниз». Причина — жёсткая привязка к конкретному лифту. Через 30 секунд после нажатия обстановка в холле меняется, но пересесть уже нельзя. Гибкость, которую даёт постоянная переоптимизация без фиксированного назначения, перевешивает выгоду от «знания будущего». Исключение — очень высокие здания с 8 и более кабинами в группе.
В статье есть интерактивная симуляция с переключателями трафика и наглядной визуализацией — можно поиграться и всё увидеть своими глазами. Так что в следующий раз, застряв в ожидании, не обижайтесь на лифт. Он вас услышал, просто ему нужно время подумать.