Arxiv/A hybrid adaptive Iterated Local Search with diversification control to the Capacitated Vehicle Routing Problem 2020 2012.11021 — различия между версиями

«A hybrid adaptive Iterated Local Search with diversification control to the Capacitated Vehicle Routing Problem 2020 2012.11021»^{скачать}

Метаэвристика широко используется для решения сложных задач оптимизации, таких как задачи маршрутизации транспортных средств (VRP), для которых есть точные методы решения непрактично.

В частности, была изучена метаэвристика, основанная на локальном поиске. успешно применен к емкостному VRP (CVRP). CVRP направлен на определение маршруты доставки с минимальной стоимостью для данного набора идентичных транспортных средств, поскольку каждое транспортное средство движется только по одному маршруту, и имеется единственное (центральное) депо.

В лучшая метаэвристика для CVRP, чтобы избежать застревания в локальных оптимумах внедрение определенных механизмов восхождения на холмы, таких как стратегии диверсификации в методы решения. Эта статья представляет гибридизацию романа адаптивная версия итерированного локального поиска с перенаправлением пути (AILS-PR) к CVRP.

Основным вкладом данной статьи является автоматический механизм управления шаг разнообразия метаэвристики, чтобы позволить ей уйти от локальных optima. Результаты экспериментов со 100 тестовыми экземплярами CVPR показывают, что AILS-PR превзошел самые современные метаэвристики CVRP.