Интернет конференция по проблемам теории и практики управления

Название: Метаэвристики в близких задачах маршрутизации типа многих коммивояжеров
Автор: Олег Олегович Макаров
Аннотация:
Основываясь на близости задач маршрутизации по метаинформации, в работе представлен этап формирования баз данных для обучения интеллектуализированной системы выбора эвристических алгоритмов решения задачи многоагентной маршрутизации. Близость двух задач маршрутизации определяется близостью их математических моделей и близостью участвующих в решении фрагментов сложной сети. В решении многоагентных задач типа коммивояжера большой размерности производится согласованная декомпозиция на локальные кластерные задачи маршрутизации. На локальном уровне выбираются подходящие алгоритмы.
Приведены результаты экспериментов по решению задач коммивояжера с использованием различных метаэвристик на данных из TSPLIB. Определены эффективные алгоритмы нахождения маршрутов. Эксперимент показал, что большинство примененных метаэвристик позволяют находить приближенные или оптимальные решения. Приведен список лучших по отношению точности алгоритмов, которые планируется использовать в разработке интеллектуальной системы выбора метаэвристик, с учетом особенностей задачи (структура и сложность сети, точность, время). Предполагается комбинирование метаэвристик, которое может привести к оптимальным результатам.
Ключевые слова:
многоагентная задача коммивояжера, метаэвристики, TSPLIB, приближенные решения, интеллектуальная система