Эффективный подход для решения задачи маршрутизации транспорта с временными окнами

В работе рассмотрена задача маршрутизации транспорта с временными окнами (VRPTW), которая представляет собой NP-трудную задачу комбинаторной оптимизации с большим числом ограничений. В работе подробно изучены и описаны существующие современные классические эвристики, а также метаэвристики для решения задачи VRPTW. Учитывая особенности ограничений грузоподъемности транспортных средств, а также временных окон, автором работы предложены наиболее подходящие окрестности для локального поиска (процедуры перехода от текущего решения к соседнему), позволяющие алгоритму наиболее эффективно исследовать «перспективные» области пространства решений. Разработана и программно реализована метаэвристика на основе подхода VNS (Variable Neighborhood Search – Поиск с Переменной Окрестностью) с двумя видами окрестностей, а также подхода GRASP (Greedy Randomized Adaptive Search Procedure – Процедура Жадного Рандомизированного Адаптивного Поиска).