Просмотр исходного текста страницы Arxiv/Heuristics for vehicle routing problems — Sequence or set optimization? 2018 1803.06062

{{checked|}}
{{arxivlink|arxiv/Heuristics for vehicle routing problems — Sequence or set optimization? 2018 1803.06062|
Мы исследуем структурную декомпозицию для маршрутизации транспортных средств с ограниченными возможностями. проблема (CVRP), основанная на «назначении» транспортного средства клиенту и посещениях «упорядочивание» переменных решения. Мы показываем, что эвристический поиск сфокусирован на решения о назначении с систематическим оптимальным выбором последовательностей (с использованием Concorde TSP solver) во время оценки каждого хода многообещающе, но требует непомерно высокие вычислительные затраты. 

Поэтому мы вводим промежуточный поиск пространство, основанное на процедуре динамического программирования Баласа и Симонетти, которая находит хороший компромисс между интенсификацией и вычислительной эффективностью. 

Предлагаются различные приемы ускорения для быстрого исследования: сокращение соседства, фильтры динамического перемещения, структуры памяти и методы конкатенации. Наконец, стратегия туннелирования призвана изменить форму пространство поиска по мере выполнения алгоритма.

Сочетание этих методов в рамках классического локального поиска, а также как в едином гибридном генетическом поиске (UHGS) приводит к значительным повышение точности решения. Находятся новые лучшие решения для на удивление небольшие экземпляры всего с 256 клиентами. Эти решения имели не были достигнуты до сих пор с классическими кварталами. В целом это исследование позволяет лучше оценить соответствующее влияние последовательности и назначения оптимизации, предлагает новые способы сочетания оптимизации этих двух решений и открывает многообещающие перспективы исследований для CVRP и ее варианты. 
}}
{{enddiv}}

[[Категория:ArxivArticles]]