Почему точные методы пасуют перед реальной логистикой
Задача маршрутизации с пикапами и доставками с временными окнами (PDPTW) - это комбинаторный взрыв в чистом виде. Каждая новая заявка умножает пространство решений, а реальные ограничения - пассажировместимость, обязательные перерывы водителей, жёсткие временные слоты - делают ландшафт поиска рваным и невыпуклым. На 10 заявках точный решатель на базе смешанного целочисленного программирования (MILP) ещё справляется за минуты. На 24 заявках и нескольких машинах время счёта уходит в часы, а на 50 - в дни. Практическая логистика требует ответа за секунды.
Ограничение пассажировместимости добавляет измерение к каждому состоянию машины: количество людей на борту меняется после каждого пикапа и доставки. Перерывы водителей вносят жёсткие временные окна, которые нельзя нарушать законодательно. Точные методы - ветви и границы, column generation - упираются в экспоненциальный рост дерева поиска. Результат: оптимальное решение недостижимо за операционное время.
Метаэвристики решают эту проблему иначе. Они не ищут глобальный оптимум с гарантией, а строят достаточно хорошее решение быстро. Adaptive Large Neighborhood Search (ALNS) - один из сильнейших инструментов для задач маршрутизации с гетерогенными ограничениями. Он комбинирует несколько стратегий разрушения и восстановления, адаптивно взвешивая их по ходу поиска. На практике это даёт сокращение стоимости маршрутов в 7 раз относительно жадной эвристики - и всё за секунды счёта.
Если вы работали с оптимизацией логистики через математическое программирование, то знаете болевую точку: модель MILP отлично описывает задачу, но не масштабируется. ALNS закрывает этот разрыв, сохраняя практическую применимость на индустриальных инстансах.
ALNS: адаптивный поиск, который учится на ходу
Large Neighborhood Search (LNS) работает по простому циклу: возьми текущее решение, разрушь значительную его часть, затем восстанови - возможно, лучше. ALNS добавляет к этому адаптивность: несколько операторов разрушения и восстановления конкурируют друг с другом, а веса успешных растут по ходу итераций. Поиск сам смещает фокус туда, где ландшафт податливее.
Цикл ALNS: выбрать оператор разрушения на основе текущих весов, удалить q запросов из маршрутов, выбрать оператор восстановления, вставить удалённые запросы обратно, оценить стоимость нового решения. Если решение лучше - принять. Если хуже - принять с вероятностью, зависящей от температуры (имитация отжига). Обновить веса операторов: успешные получают бонус, неуспешные теряют вес. Повторить тысячи раз.
Баланс exploration/exploitation управляется двумя механизмами: температурой принятия худших решений и степенью разрушения. Высокая температура и большое q - больше исследования. Низкая температура и малое q - интенсивная эксплуатация окрестности текущего решения.
Операторы разрушения: случайное, худшее и связанное удаление
Три оператора покрывают спектр от слепой диверсификации до целенаправленного разрушения проблемных участков.
Случайное удаление - равновероятно выбирает q запросов и выкидывает их из маршрутов. Максимальная диверсификация, ноль интеллекта. Эффективно на ранних итерациях, когда решение далеко от оптимума и нужно широко прощупать пространство. Псевдокод:
def random_removal(solution, q):
return random.sample(solution.requests, q)Удаление худших запросов - вычисляет стоимость каждого запроса в текущем решении (прирост общей стоимости при его наличии) и удаляет q с наибольшей стоимостью. Это эксплуатационный оператор: он бьёт туда, где больно. Если запрос заставляет машину делать большой крюк или ждать полчаса под временным окном - он кандидат на удаление. Псевдокод:
def worst_removal(solution, q):
costs = [(r, solution.cost_if_removed(r)) for r in solution.requests]
costs.sort(key=lambda x: x[1], reverse=True)
return [r for r, _ in costs[:q]]Связанное удаление - выбирает случайный запрос-затравку, затем удаляет q запросов, наиболее похожих на него по расстоянию, временным окнам или географии. Идея: похожие запросы часто конкурируют за одни и те же слоты маршрута, их групповое удаление позволяет пересобрать кластер эффективнее. Мера близости - взвешенная сумма разниц по координатам, времени начала окна и требуемой вместимости. Этот оператор даёт структурированную диверсификацию, не раскидывая запросы хаотично.
Операторы восстановления: жадная вставка против regret-2
Восстановление - более тонкая работа. Нужно вставить удалённые запросы обратно в маршруты с минимальным штрафом.
Жадная вставка - для каждого удалённого запроса перебирает все возможные позиции во всех маршрутах и выбирает позицию с наименьшим приростом стоимости. Запросы вставляются последовательно, порядок влияет на результат. Быстро, дёшево по вычислениям, но близоруко: вставка первого запроса может заблокировать выгодную позицию для второго.
Regret-2 вставка - для каждого удалённого запроса вычисляет не только лучшую позицию, но и вторую лучшую. Разница между ними - regret-значение. Запрос с наибольшим regret вставляется первым, потому что откладывание его вставки грозит наибольшими потерями. Формула: regret(r) = cost(r, second_best_position) - cost(r, best_position). Запросы с высоким regret получают приоритет.
Пример расчёта: запрос А можно вставить в маршрут 1 с приростом +10 единиц стоимости или в маршрут 2 с приростом +25. Regret = 25 - 10 = 15. Запрос Б: лучшая вставка +12, вторая +13. Regret = 1. Regret-2 вставит А первым - альтернатива для него значительно хуже. Жадная вставка может вставить Б первым, занять слот, и тогда А придётся вставлять за +25. Regret-2 даёт более дальновидные решения ценой O(n²) против O(n) у жадной. На практике это окупается качеством финального маршрута.
Реализация на Python: от библиотеки до рабочего солвера
Библиотека alns для Python предоставляет каркас: определение задачи через состояния, операторы разрушения и восстановления, критерии принятия и остановки. Разработчику остаётся реализовать специфику предметной области.
Состояние задачи - это объект, хранящий текущие маршруты, список необслуженных запросов, счётчики времени. Операторы разрушения получают состояние и степень разрушения, возвращают изменённое состояние с удалёнными запросами. Операторы восстановления получают состояние и список удалённых запросов, возвращают состояние со вставленными запросами.
Ключевой фрагмент - функция стоимости. Она вычисляет суммарное расстояние, штрафы за нарушение временных окон, штрафы за необслуженные запросы. Штрафы должны быть настроены так, чтобы направлять поиск к допустимым решениям: сначала ALNS находит feasible solution, затем оптимизирует стоимость внутри допустимой области.
from alns import ALNS
from alns.criteria import HillClimbing, SimulatedAnnealing
alns = ALNS()
alns.add_destroy_operator(random_removal)
alns.add_destroy_operator(worst_removal)
alns.add_destroy_operator(related_removal)
alns.add_repair_operator(greedy_insertion)
alns.add_repair_operator(regret2_insertion)
criterion = SimulatedAnnealing(
start_temperature=100,
end_temperature=0.1,
step=0.9999
)
result = alns.iterate(initial_solution, criterion, max_iterations=10000)Схема адаптивного взвешивания встроена в библиотеку: операторы, приводящие к улучшению глобального рекорда, получают больший вес; операторы, дающие приемлемое ухудшение, - средний вес; операторы, чьи решения отвергаются, - вес снижается. После каждого сегмента итераций веса обновляются с коэффициентом затухания, чтобы история не довлела над свежими результатами.
Интеграция обязательных перерывов водителей
Перерывы водителей - ограничение, которое ломает наивные реализации. Машина не может ехать более 4 часов непрерывно, после чего требуется 45-минутный перерыв. Это не просто временное окно - это окно, которое активируется накоплением времени в пути.
Подход к моделированию: при каждой вставке запроса в маршрут проверяется накопленное время вождения от последнего перерыва. Если добавление запроса приведёт к превышению лимита, перед ним вставляется перерыв. Стоимость маршрута увеличивается на фиксированный штраф за перерыв. Операторы восстановления должны учитывать эту логику: позиция вставки влияет не только на расстояние, но и на необходимость дополнительных перерывов.
Практический эффект: без учёта перерывов ALNS строит геометрически короткие маршруты, которые невыполнимы в реальности. С учётом перерывов маршруты становятся длиннее по расстоянию, но допустимы по законодательству. Разница в стоимости может составлять 15-20% - это цена feasibility.
Кейс из нефтегаза: 24 заявки, 7-кратное сокращение стоимости
Задача: перевозка персонала между объектами нефтегазового месторождения. 24 заявки типа «забрать группу людей в точке А и доставить в точку Б». Временные окна жёсткие - опоздание недопустимо. Пассажировместимость машин ограничена 8 человеками. Водители обязаны соблюдать режим труда и отдыха. Несколько машин доступны, но их количество - тоже переменная оптимизации.
Начальное решение построено жадной эвристикой: для каждой заявки ищется ближайшая машина, заявка вставляется в конец маршрута, если ограничения позволяют. Результат: 3 машины, суммарная стоимость (взвешенная сумма расстояния и времени) - 1470 условных единиц, 2 заявки не обслужены из-за конфликта временных окон.
ALNS с тремя операторами разрушения и двумя восстановления, 10 000 итераций, simulated annealing. Результат: все 24 заявки обслужены, 2 машины вместо 3, стоимость - 210 единиц. Сокращение в 7 раз. Время счёта - 12 секунд на ноутбуке с Core i7.
График сходимости характерен для ALNS: первые 2000 итераций - быстрое падение стоимости с плато на feasible решении, затем медленное улучшение с периодическими скачками вверх (принятие худших решений для выхода из локальных оптимумов), финальные 3000 итераций - микроулучшения в пределах 2-3%.
Связанное удаление показало наибольший вес к концу поиска - 0.48 против 0.22 у случайного и 0.30 у худшего. Regret-2 доминировал над жадной вставкой с весом 0.71 против 0.29. Это подтверждает: на структурированных данных с кластерами заявок интеллектуальные операторы окупаются.
Этот результат перекликается с темой анализа реальных процессов вместо идеальных моделей: жадная эвристика предполагала, что заявки можно обслужить в порядке поступления, но реальные временные окна и перерывы водителей требовали принципиально иной структуры маршрутов.
От нефтегаза до e-commerce: где ещё применить ALNS
Ядро задачи - пикапы, доставки, временные окна, ограничения вместимости - универсально для логистики. Меняется предметная область, но структура ограничений остаётся.
В e-commerce и last-mile доставке добавляются временные слоты клиентов («доставка с 18:00 до 21:00»), грузоподъёмность вместо пассажировместимости, приоритеты заказов (премиум-доставка). Оператор связанного удаления модифицируется: мера близости учитывает не географию, а временной слот - заказы в один слот удаляются группой. Regret-2 получает дополнительный фактор - штраф за нарушение приоритета.
В райдшеринге (ride-sharing) пикап и доставка - это посадка и высадка пассажира. Вместимость - количество свободных мест. Временные окна - желаемое время подачи и прибытия. Перерывы водителей - обязательны. ALNS адаптируется заменой функции стоимости: вместо расстояния минимизируется время ожидания пассажиров и отклонение от желаемого времени.
В курьерских службах с несколькими типами транспортных средств (велосипед, авто, пеший) операторы восстановления получают дополнительное измерение - выбор типа транспорта под запрос. Связанное удаление группирует запросы по типу транспорта.
Общий принцип: ALNS - это каркас, а операторы и функция стоимости - точки кастомизации под отрасль. Если вы проектировали AI-агентов с нуля, то узнаете паттерн: оркестратор (ALNS) + подключаемые стратегии (операторы) + цикл обратной связи (адаптивные веса).
Когда ALNS не нужен: ограничения и альтернативы
ALNS - мощный, но не универсальный инструмент. На малых задачах (до 10-12 заявок, простые ограничения) точные методы находят оптимум за секунды, и метаэвристика не даёт выигрыша. Если ограничения линейны и задача укладывается в MILP без хитрых нелинейностей - решатель вроде HiGHS или Gurobi предпочтительнее: он даёт гарантию оптимальности и не требует настройки операторов.
Сравнение с другими метаэвристиками: генетические алгоритмы хорошо работают на задачах, где решение можно осмысленно кодировать в хромосому и скрещивать. Для маршрутизации это нетривиально - оператор кроссовера должен сохранять допустимость потомков. Табу-поиск эффективен для локальной окрестности, но на крупных задачах с многими ограничениями окрестность огромна, и табу-список не спасает от блужданий. ALNS выигрывает за счёт крупных шагов (разрушение 20-30% решения) и адаптивного выбора стратегии.
Рекомендации по выбору метода:
- Менее 15 заявок, линейные ограничения - MILP (Pyomo + HiGHS)
- 15-50 заявок, сложные ограничения - ALNS
- Более 50 заявок - ALNS с параллельными запусками и отбором лучшего
- Динамическая задача (заявки приходят онлайн) - ALNS с периодическим перепланированием
Границы применимости ALNS - это не недостаток, а специфика инструмента. Как и в случае с компрессией знаний TAKC, где сжатие в 8-64 раза работает для аналитических запросов, но не для фактологических, ALNS решает определённый класс задач маршрутизации эффективнее аналогов. Выбор метода - это инженерное решение, основанное на размере инстанса, структуре ограничений и требованиях к времени ответа.