Задача коммивояжера с временными окнами (TSPTW): динамическое программирование и эвристики

Математическая модель TSPTW добавляет к графу дорог временную шкалу. Для каждой вершины i задается временное окно [e_i, l_i], где e_i — самое раннее допустимое время начала обслуживания, а l_i — самый поздний дедлайн. К переменным бинарного пути добавляются непрерывные переменные t_i, отражающие фактическое время прибытия в узел. Логика модели накладывает жесткие дизъюнктивные ограничения: если транспорт прибывает в узел раньше времени e_i, он обязан простаивать в ожидании открытия окна (Wait Time). Если же время в пути плюс время на обслуживание предыдущего клиента приводит к прибытию позже дедлайна l_i, маршрут признается физически недопустимым (Infeasible), и эта ветвь вычислений безвозвратно отсекается.

Для поиска абсолютно точного решения TSPTW применяется алгоритм динамического программирования Беллмана-Хелда-Карпа. Состоянием системы в алгоритме является пара (S, i), где S — множество уже посещенных узлов, а i — текущий узел. Однако наличие непрерывного времени разрушает компактность таблицы мемоизации. Чтобы справиться с этим, математики используют метод сглаживания пространства состояний (State-Space Relaxation). Суть метода заключается в ослаблении требования посещать каждую вершину ровно один раз, что позволяет проецировать бесконечное временное пространство на дискретную сетку. В сочетании с методом ветвей и границ (Branch-and-Bound) и генерацией отсекающих неравенств этот подход позволяет находить строгие оптимумы для сетей, содержащих до сотни узкоспециализированных клиентов.

Для решения реальных индустриальных задач огромной размерности (тысячи заказов) исследовательские центры разрабатывают многоуровневые эвристические алгоритмы. Мощным инструментом является алгоритм ALNS (Adaptive Large Neighborhood Search — Адаптивный поиск в больших окрестностях). Алгоритм состоит из двух фаз: разрушения (Ruin) и воссоздания (Recreate). На фазе разрушения алгоритм вырывает из текущего маршрута несколько десятков узлов (например, узлы, которые вносят наибольший вклад в задержки или время ожидания). На фазе воссоздания жадные алгоритмы вставки (Insertion Heuristics) возвращают эти узлы обратно в маршрут, пытаясь найти более эффективную комбинацию без нарушения временных окон.

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