Вчера я 4 минуты стоял в подъезде и смотрел, как два лифта одновременно поехали вверх. Все два. На табло — 12, 15, 18. Я на первом. Мне на шестой. И я подумал: вот я кучу лет пишу софт, оптимизирую запросы к базе данных, кеширую всё что движется — а эти две коробки на тросах не могут разобраться, кто из них должен спуститься за мной.
Потом я погрузился в тему. И выяснил, что они не «не могут разобраться». Они математически не способны найти идеальное решение. Вообще никто не способен. Задача диспетчеризации группы лифтов — NP-трудная. То есть буквально: не существует алгоритма, который гарантированно найдёт оптимальный маршрут за разумное время.
И вот уже 60 лет лучшие инженеры мира решают эту задачу эвристиками. По сути — догадками.
Мысленный эксперимент: 3 лифта, 20 этажей, час пик
Представь здание. 20 этажей. 3 лифта. Утро понедельника, 9:15. В лобби бизнес-центра стоят 50 человек. Кому-то на 5-й, кому-то на 19-й, кто-то вообще с 7-го хочет на 12-й (и как он словил лифт в 9 утра — отдельный вопрос).
Задача: распределить людей по лифтам так, чтобы среднее время ожидания было минимальным.
Звучит просто? Ну давайте посчитаем. Для каждого нового вызова с этажа диспетчер должен решить какой из 3 лифтов послать. Это 3 варианта. Для 50 вызовов — 3⁵⁰ комбинаций. Это 7.18 × 10²³. Семьсот секстиллионов вариантов. Для контекста: атомов во вселенной примерно 10⁸⁰. То есть мы пока не дошли до масштабов вселенной, но уже уверенно обогнали число песчинок на всех пляжах Земли.
И это ещё простая модель. В реальности каждый лифт — система с непрерывным состоянием: текущий этаж, направление движения, скорость, загрузка (в килограммах), список уже нажатых кнопок внутри кабины, время открытия/закрытия дверей. Пока ты думаешь, на каком этаже высадить Васю, Маша на 14-м уже нажала кнопку и изменила всю матрицу решений.
Формально это доказали ещё в начале 2000-х. Задача назначения вызовов в группе лифтов сводится к обобщённой задаче маршрутизации, а та — к NP-трудной задаче. Для n этажей и k лифтов пространство комбинаций — n^k. Полный перебор невозможен. Или есть другой способ…
Первый подход: «Просто езжай туда-сюда»
Самый древний алгоритм диспетчеризации лифтов настолько прост, что его назвали SCAN. Или — «лифтовый алгоритм» (да, алгоритм лифта назвали «лифтовым алгоритмом»)
Принцип: лифт едет вверх, пока есть хоть один вызов выше. Подбирает всех попутчиков. Доехал до верхнего — разворачивается и едет вниз. Подбирает всех попутчиков вниз. Доехал до нижнего — разворачивается. Повторить до тепловой смерти вселенной.
Если вы когда-нибудь работали с дисковыми накопителями — вы этот алгоритм знаете. В операционных системах SCAN используется для планирования запросов к жёсткому диску. Головка чтения/записи ходит от внутренних дорожек к внешним и обратно, обслуживая запросы по пути. Дональд Кнут описал теоретическую симуляцию одного лифта ещё в 1960-х — в контексте обсуждения сопрограмм и двусвязных списков (не лифтов).
SCAN — честный. Никого не обделит. Но тупой. Если вы на 2-м этаже, а лифт только что проехал вас наверх — ждите, пока он доберётся до 20-го, развернётся и спустится обратно. Даже если наверху никого нет. Он всё равно доедет до конца. Потому что алгоритм.
LOOK: «А может, не надо ехать до конца?»
LOOK — это SCAN для людей с минимальным здравым смыслом. Разница: лифт не едет до физического конца шахты, а смотрит (look, да), есть ли впереди ещё запросы. Нет запросов выше? Разворачивайся прямо тут.
C-LOOK идёт дальше: лифт обслуживает запросы только в одном направлении. Доехал до верхнего вызова — прыгает вниз к самому нижнему и снова едет вверх, как автобус-экспресс, который с конечной летит на начальную, не останавливаясь.
Для одного лифта нормально работает. Среднее время ожидания приемлемое, дисперсия невысокая, голодание невозможно. Но мы же говорим про группу лифтов. А для группы SCAN/LOOK — это как три автобуса на одном маршруте, которые ничего друг про друга не знают. Они неизбежно сбиваются в «стайку» и едут вместе, один за другим, потому что у них одинаковая логика.
(Если вы ждали автобус 40 минут, а потом приехали три подряд — поздравляю, вы наблюдали аналогичный эффект. В теории транспорта это называется bus bunching.)
Destination dispatch: «А скажите мне, куда вы едете»
В 1996 году Schindler выпустила систему Miconic 10, и это был, пожалуй, первый момент, когда лифтовая индустрия реально сделала инженерный прорыв, а не просто прикрутила новые кнопки.
Идея гениально простая: спрашивать у пассажира этаж назначения до посадки в лифт. Не вверх/вниз, а конкретный этаж. На этаже стоит панель с цифрами (или тачскрин, если здание модное). Вводишь «15» — система отвечает «Лифт C». Ты идёшь к лифту C, в кабине нет кнопок этажей (шок для неподготовленного человека).
Вопрос, а что это даёт? Ответ — всё. Диспетчер теперь знает куда едет каждый пассажир до того, как тот вошёл в кабину. Он может группировать людей с близкими этажами в один лифт. Лифт A везёт всех на 2-5, лифт B на 6-12, лифт C на 13-20. Меньше остановок на кабину — быстрее каждый рейс — выше пропускная способность всей группы.
После Schindler подтянулись все: Otis со своим Compass (2005), KONE с Polaris (тоже 2005, потом переименовали в KONE Destination), Mitsubishi с DOAS, ThyssenKrupp с AGILE. По разным оценкам, destination dispatch сокращает время в пути на 25% и поднимает пропускную способность на 30% по сравнению с классическими системами.
30 процентов. Просто за счёт того, что ты спрашиваешь человека, куда он едет, до того как закрыл двери.
(Я, кстати, не шучу про отсутствие кнопок внутри лифта. В каких-нибудь свежих бизнес-центрах класса A вы, вероятнее всего, увидите панель без единой цифры. Только кнопку открытия дверей и телефон экстренной связи.)
Что внутри чёрного ящика: ETA и взвешенные функции
Ок, destination dispatch хорошая идея. Но как именно система решает, какой лифт назначить на какой вызов?
Классический подход — ETA (Estimated Time of Arrival). Для каждого лифта считается расчётное время прибытия к вызвавшему этажу, с учётом текущей позиции, направления, запланированных остановок, загрузки. Назначается лифт с минимальным ETA.
Просто? Слишком. Потому что минимальное ETA для этого вызова может убить время ожидания для следующих десяти. Отправил ближайший лифт к одному пассажиру — а он по дороге набрал ещё пять остановок, и теперь все на 18-м ждут 3 минуты.
Поэтому реальные системы используют взвешенные функции стоимости. Что-то вроде:
def cost(elevator, call, weights): return (weights[0] * eta(elevator, call) + weights[1] * coincident_bonus(elevator, call) + weights[2] * load_penalty(elevator) + weights[3] * direction_change_penalty(elevator, call) + weights[4] * future_demand_estimate(call))
Бонус за «попутный» вызов (лифт уже едет в нужном направлении и проедет мимо этого этажа). Штраф за загруженность. Штраф за смену направления. Оценка будущего спроса — если сейчас 8:55 и лобби заполняется, лучше держать один лифт внизу.
Веса подбираются вручную. Инженерами. На основе симуляций. Для каждого здания. Потому что 20-этажный офисный центр и 50-этажный небоскрёб — это разные вселенные трафика.
И вот тут мы подходим к самому интересному.
Почему ML проиграл эвристикам
Казалось бы — идеальная задача для машинного обучения. Большое пространство состояний, стохастическая среда, повторяющиеся паттерны. Бери, да тренируй.
Так и делали. Crites и Barto ещё в 1996 году применили Q-learning к системе из 4 лифтов и 10 этажей. Результат: 4 дня тренировки на 100 MIPS процессоре, что соответствовало примерно 60 000 часам симулированного времени. Для одного сценария вечернего часа пик. Неплохо работало, но…
С тех пор было десятки попыток. Генетические алгоритмы. Нечёткая логика. Мультиагентные системы. Dueling Double Deep Q-Network (D3QN) — это не я придумал, это реально так называется. Каждая новая статья обещает прорыв.
А в реальных зданиях стоят всё те же эвристики. Почему?
Первая причина — время принятия решения. У диспетчера лифтов есть около 200 миллисекунд на принятие решения. Нажал кнопку и через 200мс лифт должен начать движение. Нейросеть, даже маленькая, на микроконтроллере лифтовой группы — это рискованная инвестиция. Эвристика на switch-case отрабатывает за микросекунды.
Вторая — интерпретируемость. Когда лифт ведёт себя странно, инженер KONE должен понять почему. «Вес w₃ слишком высокий, лифт штрафует загруженные кабины» — это диагноз. «Нейросеть решила так» — это не диагноз. Это шестая стадия принятия. Лифт — система безопасности. Если кабина застрянет или уедет не туда, люди застрянут между этажами. Регуляторы хотят объяснимость, а не точность.
Третья — паттерны меняются. ML-модель, натренированная на утренний пик (все едут вверх из лобби), теряется в обеденный (все едут хаотично между этажами). Отдельные модели для каждого паттерна? Нужна ещё одна модель, которая предсказывает текущий паттерн. И если она ошиблась — всё летит. Недавние работы с D3QN пытаются решить это «unified all-in-one» тренировкой, но результаты пока… скажем так, многообещающие в лабораторных условиях.
Четвёртая — и самая неочевидная — эвристики уже очень хороши. 60 лет итераций, миллионы установленных систем, петабайты логов реального трафика. Взвешенные функции стоимости, калиброванные под конкретные паттерны трафика, работают с вероятностью процентов 95 от теоретического оптимума. ML выигрывает оставшиеся 5% (может быть), проигрывая в надёжности, объяснимости и стоимости деплоя.
Когда я об этом читал, мне стало как-то… уютно? Не знаю, как объяснить. Есть что-то приятное в том, что задачу, которую невозможно решить точно, мы решаем достаточно хорошо набором правил, которые инженеры 60 лет полировали вручную.
200 миллисекунд
Вот что происходит, когда ты нажимаешь кнопку на этаже в современном здании с destination dispatch:
-
Ты вводишь «15» на тачскрине (≈2 сек).
-
Контроллер получает вызов: этаж 3 → этаж 15 (≈5мс на передачу).
-
Для каждого из N лифтов вычисляется взвешенная функция стоимости — ETA, загрузка, направление, попутные вызовы, прогноз спроса (≈50-150мс).
-
Назначается лифт с минимальной стоимостью (≈1мс).
-
На табло загорается «Лифт C» (≈10мс на рендер).
Итого: где-то 100-200 миллисекунд от нажатия до ответа. За это время система решает NP-трудную задачу. Не оптимально. Но достаточно хорошо, чтобы ты доехал до 15-го за 45 секунд, а не за 3 минуты.
Каждый день, в каждом здании мира, миллионы раз.
В общем, я все ждал, когда один из двух лифтов в моём доме 2008-го года постройки спустится ко мне. У нас обычные кнопки вверх/вниз. Никакого destination dispatch. Классический SCAN (наверное). А может, вообще FCFS — кто нажал первый, к тому и едем.
В итоге решил пойти пешком. Шестой этаж — не двадцатый.
