Модели и алгоритмы локального поиска для маршрутизации транспортных средств с возвратами и временными окнами

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