Эвристический алгоритм на основе характеристик решений для задачи CVRPTW

Основной идеей данной работы является изучение возможности применения знания о структуре решения задачи CVRPTW в процессе поиска наиболее оптимального набора маршрутов. Исследование было вдохновлено работой (Arnold & Sörensen, What makes a VRP solution good? The generation of problem-specific knowledge for heuristics, 2018), в которой авторы проанализировали эффективность использования информации о некоторых характеристиках решения для задачи CVRP. На наборе искусственных данных было показано, что по значениям некоторых структурных свойств можно с достаточно высокой вероятностью различать более оптимальные решения от менее оптимальных. На основании этого факта была предложена модификация алгоритма VNS, которая пытается при достижении локального оптимума выйти за его пределы, используя информацию о структуре решения. Вычислительные эксперименты на наборе данных из (Solomon, 1987) показали, что предложенный метод способен находить решения, которые сравнимы с лучшими известными решениями в литературе.