Как лифты решают, кого забрать первым: алгоритмы SCAN, LOOK и RSR от Otis

Технический разбор на сайте john.fun описывает, как устроены алгоритмы диспетчеризации лифтов. Для одного лифта простейший алгоритм называется SCAN: он запатентован в 1961 году и заставляет кабину доезжать до самого верхнего этажа, прежде чем развернуться, подбирая и высаживая пассажиров по пути. Более практичный вариант, LOOK: кабина едет только до этажа, который реально запросили, не поднимаясь выше без нужды; именно этот алгоритм большинство людей и считают «обычным» поведением лифта. Когда кабин несколько, вступает в игру координация между ними. В базовой схеме центральный диспетчер назначает каждый вызов ближайшему свободному лифту. Автор показывает, что можно сделать лучше, на примере алгоритма RSR (Relative System Response) компании Otis: каждой кабине присваивается оценка того, насколько она подходит для конкретного вызова (чем ниже оценка, тем лучше), система штрафует кабину, если другая уже едет на тот же этаж в том же направлении, и поощряет простаивающие кабины в пределах двух этажей от вызывающего. Ключевая деталь RSR, переоптимизация каждые 5 секунд: если назначенная кабина застряла, вызов может быть на лету передан другой. Автор сравнивает LOOK и RSR по распределению времени ожидания (p90 и p50, доли поездок, уложившиеся в определённое время; в иллюстративном примере p90 около 2 минут, p50 около 1 минуты). Результат неочевиден: при высокой интенсивности потока, когда лифты и так забиты и останавливаются на каждом этаже, дополнительные правила RSR почти не дают выигрыша, и LOOK начинает обгонять RSR по эффективности; то же происходит в небольших зданиях с малым числом лифтов в группе. Отдельно разобраны системы Destination Dispatch, киоски на этаже, где пассажир заранее вводит нужный этаж, а система направляет его к конкретной кабине. Интуитивно кажется, что более полная информация о пассажиропотоке должна снижать время ожидания, но на практике, по данным статьи, такие киоски в большинстве случаев проигрывают обычным кнопкам «вверх/вниз». Причина, жёсткость: пассажир обязан сесть именно в назначенную кабину и не может воспользоваться преимуществом переоптимизации каждые 5 секунд, которая спасает систему с кнопками при изменении обстановки. Киоски выигрывают лишь в отдельных случаях, в очень высоких зданиях с 8 и более кабинами в лифтовой группе. Автор также отмечает, что люди плохо запоминают среднее время ожидания и вместо этого фиксируются на редких «вечных» задержках (случай p90), а утренний час пик статистически даёт худшие показатели ожидания среди всех периодов дня.

Ключевые факты

SCAN (1961 год), базовый алгоритм для одного лифта: кабина всегда доезжает до верхнего этажа перед разворотом; LOOK едет только до реально запрошенного этажа.
Для нескольких кабин компания Otis использует алгоритм RSR (Relative System Response): он оценивает каждую кабину по пригодности для вызова и переоптимизирует назначения каждые 5 секунд.
При высокой интенсивности потока и в небольших зданиях с малым числом лифтов простой LOOK начинает обгонять по эффективности более сложный RSR.
Киоски Destination Dispatch (выбор этажа заранее) в большинстве случаев проигрывают обычным кнопкам «вверх/вниз» по времени ожидания, кроме очень высоких зданий с 8+ кабинами в группе.
Люди фиксируются на редких долгих ожиданиях (p90), а не на среднем времени; утренний час пик даёт худшую статистику ожидания.

Почему это важно

Материал показывает, что обыденная вещь, лифт, скрывает нетривиальную задачу теории расписаний и массового обслуживания. Разбор наглядно демонстрирует общий инженерный принцип: более сложная и информированная система (Destination Dispatch с полным знанием маршрутов) не всегда побеждает простую и гибкую (кнопки плюс переоптимизация каждые 5 секунд), потому что жёсткость назначения может перевешивать выгоду от дополнительной информации.

Кому это важно

Материал адресован широкой инженерной и просто любопытной аудитории: тем, кто интересуется алгоритмами оптимизации, теорией очередей и распределённой координацией ресурсов. Прямого отношения к разработчикам ИИ-систем текст не имеет, это классическая инженерная задача из области индустрии лифтов и систем реального времени.

Как это применить

Статья приводит открытый интерактивный симулятор с полным набором параметров, где можно самому поиграть с алгоритмами SCAN, LOOK и RSR и посмотреть, как они справляются с разной интенсивностью пассажиропотока. Это позволяет читателю не просто прочитать выводы, а проверить их эмпирически на модели.

Можно ли доверять

Материал написан как самостоятельный технический разбор со ссылкой на конкретный запатентованный алгоритм (SCAN, 1961) и на конкретную коммерческую систему (RSR компании Otis), а не как маркетинговый или рекламный текст. Автор статьи и дата публикации в тексте не указаны, а числовые примеры распределения времени ожидания (p90 около 2 минут, p50 около 1 минуты) явно помечены как иллюстративные для учебного графика, а не как измеренные данные реального здания, это важное уточнение, которое не стоит принимать за статистику из практики.

Риски и подводные камни

Автор не приводит числовой разницы в производительности между LOOK и RSR, только качественное направление (кто выигрывает и при каких условиях), поэтому делать выводы о конкретном проценте выигрыша не стоит. В тексте не названы другие производители лифтовых систем, кроме Otis, и не указаны реальные здания или внедрения, так что выводы о Destination Dispatch стоит воспринимать как общую закономерность из симуляций, а не как отчёт о конкретном проекте.