Сложный алгоритм: как работают лифты

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

Чтобы лифт мог сам управлять своим движением, инженерам нужен был алгоритм, определяющий, в каких случаях куда кабине нужно направляться. Самый простой способ — двигаться вниз и вверх с остановками на указанных этажах в предустановленные временные промежутки. Для пассажира это выглядит как поездка на электричках с пересадками: сначала идешь на десятый этаж, куда в 15:10 прибывает лифт, следующий до пересадочного этажа, а там уже ищешь, как добраться на нужный. Об эффективности говорить не приходится: в часы пик пассажиры вынуждены тратить время, ожидая, когда лифт отправится по расписанию, а в то время, когда почти никто им не пользуется, кабины впустую расходуют электроэнергию, порожними курсируя между этажами.

К 1965 году инженеры остановились на знакомой каждому с детства модели: пассажир нажимает на кнопку вызова, и на его этаж прибывает кабина. Но вот задача: как алгоритму понять, куда направлять кабину, если ее вызывают сразу на нескольких этажах?

Какова должна быть идеальная система координации лифтов? Должен ли лифт приехать сначала к тому пассажиру, который ждет дольше всех? Или лучше направить кабину к ближайшему этажу вызова? Как найти баланс между скоростью подачи лифта и расходом электроэнергии?

Понятно, что нужно оптимизировать время на провоз пассажиров. Но как расставить приоритеты? Если одному пассажиру придется ждать не 20 с, а минуту, прежде чем перед ним раскроются двери лифта, насколько это для него будет утомительнее? В три раза? А может, в шесть или семь? Даже для такой незамысловатой задачи нет четких вводных данных.

Иногда даже лучше, если сама поездка в лифте займет больше времени. Представим два сценария: в первом лифт приезжает через 10 с после нажатия кнопки вызова, а сама поездка до нужного этажа занимает минуту. По второму сценарию вы ждете лифт 30 с и едете тоже 30 с. Большинству людей ожидание кажется настолько невыносимым, что они выбрали бы первый вариант, пускай и придется потратить лишние десять секунд. Исходя из этого, инженеры программируют алгоритм таким образом, чтобы он учитывал «коэффициент утомительности», вместо того чтобы просто минимизировать время поездки.

Во многих лифтах все еще используется самый ранний и простой механизм электронного управления. Этот алгоритм содержит два правила:

1. Пока внутри лифта или на этажах, куда приближается лифт по ходу движения, есть пассажиры, которым нужно по направлению текущего движения, лифт продолжает перемещаться в этом направлении.

2. Как только вызовы лифта по текущему направлению движения закончились, но при этом есть вызов в противоположном направлении, механизм направляет движение в обратную сторону. Если же вызовов нет, лифт останавливает движение до следующего вызова.

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

В небольших офисах и многоквартирных домах, где от лифта не требуется повышенной энергоэффективности, удобно задействовать этот незамысловатый механизм. Однако его применение в зданиях с большей этажностью влечет за собой ряд трудностей. Каждый раз, проезжая средние этажи, лифт обслуживает находящихся там пассажиров, но алгоритм может долго не давать лифту остановиться на цокольном этаже по пути на седьмой. Поэтому ожидание на первом и последнем этажах, где лифт вызывают чаще всего, может продлиться мучительно долго. Кроме того, большие здания обычно обслуживает не один, а несколько лифтов. Если каждый из них будет следовать одному и тому же алгоритму, начнется настоящая чехарда: на некоторых этажах будут попеременно раскрываться несколько лифтов. Кроме того, все они будут усиленно обслуживать средние этажи, иногда открываясь по два раза на один вызов.

Чтобы оптимизировать работу групп лифтов, инженеры придумали ряд хитростей. Им удалось заставить лифты «договариваться» между собой — а это уже половина дела. Если лифт вызывают на первом этаже, а кабина 1 в это время направляется вверх, то вместо нее может спуститься кабина 2. Кроме того, можно привязать каждый лифт к определенной группе этажей. Возможно, вам приходилось бывать в зданиях, где несколько лифтов просто стоят в лобби с открытыми дверями. Это называется «стратегия парковки», когда пустые лифты возвращаются на этажи, где они пользуются наибольшим спросом. Сегодня технологии прогнозирования пассажиропотока и программы для мониторинга в режиме реального времени позволяют компьютерной системе лифта варьировать стратегии, чтобы подстроиться под нужды пассажиров в утренние и вечерние часы пик.

Должен ли лифт приехать сначала к тому пассажиру, кто ждет дольше всех? Или лучше направить кабину к ближайшему этажу вызова?

Настоящий прорыв в программировании лифтов пришелся на 1970-е, когда появилась возможность перепрограммировать компьютеры. Если кто-то изобретал новую стратегию маршрутизации лифтов, то вовсе не обязательно было, как раньше, продавать идею строительному магнату и ждать, пока он построит небоскреб. Теперь можно было обкатать и настроить разработку на виртуальных симуляторах.

После этого индустрия обогатилась множеством новых алгоритмов. Одна из популярных сегодня стратегий — «контроль расчетного времени прибытия». Ее суть в том, что компьютер оценивает все кабины, движущиеся по направлению к этажу, где была нажата кнопка вызова, и выбирает ту, которая, по его расчетам, прибудет на место быстрее всех. Другая востребованная стратегия — всегда направлять на вызов ту кабину, которая, согласно прогнозу, наиболее удобна для пассажира. Это предполагает сочетание минимального времени поездки, минимальных затрат энергии и других обозначенных конструктором приоритетов.

Вершина оптимизации — это технология группировки по месту назначения (destination dispatch), которая используется в лифтах небоскребов, построенных или модернизированных после 1990-х годов. В этих зданиях вместо кнопок вызова «вверх» и «вниз» вы выбираете кнопку с нужным этажом, и интеллектуальная система сообщает, какой лифт из группы доставит вас до места назначения.

Благодаря тому что система знает, куда конкретно нужно добраться пассажирам, ее эффективность стремится к идеальной. Люди, которым нужно на один и тот же этаж, группируются в одной кабине, и каждая группа добирается до места назначения без лишних остановок. Можно догадаться, что при этом время ожидания лифта в среднем увеличивается, поэтому система, оснащенная технологией группировки по месту назначения, может менять приоритеты в течение дня. Например, в утренний час пик, когда ключевой является полезная производительность, ждать прибытия лифта придется дольше, но зато время поездки сокращается. Днем, когда пассажиропоток уменьшается, лифт может приехать быстрее и ожидание будет менее утомительным.

Имея в распоряжении все эти варианты, можно выбрать из них самый подходящий. Зачастую этот выбор тоже автоматизируется. Используя технологии машинного обучения, инженеры моделируют желаемый результат, и затем программа-контроллер симулирует действия, чтобы добиться оптимального эффекта в соответствии с заданной моделью. В каждый момент времени система сканирует состояние симуляторов лифта и параметры каждого исходящего вызова, решает, какие действия следует предпринять, и измеряет результативность. В итоге программа находит наиболее эффективные пути для всех комбинаций факторов. Они бывают настолько сложны, что даже разработчикам не всегда понятно, почему контроллер работает так, а не иначе.