Метаэвристические алгоритмы для многоагентных задач маршрутизации

Рассматриваются задачи построения маршрутов в сложных сетях многими агентами-коммивояжерами. Формализация приводит к задачам псевдобулевой дискретной оптимизации с ограничениями, учитывающими специфику построения маршрутов. Разреженность матрицы ограничений позволяет применять декомпозиционные подходы и кластеризацию сети. Разработка приближенных алгоритмов выбора маршрутов в сложных сетях связана с учетом свойств структуры сети, ее сложности, наличия ограничений, предписаний, условий достижимости, числа агентов-коммивояжеров. Показано, что решение задач маршрутизации может базироваться на применении многоагентного подхода в сочетании с кластеризацией (декомпозицией) исходной задачи и метаэвристик. Многоагентные системы с роевым интеллектом применяются для решения сложных задач дискретной оптимизации, которые нельзя эффективно решить с помощью классических алгоритмов. Агентная модель для сложной сети задачи типа многих коммивояжеров становится интеллектуализированной системой, определяющей эвристические алгоритмы поиска оптимального решения реактивными агентами (следующими заложенным в них правилам). Применяются композиции подробно описанных алгоритмов, которые хорошо себя зарекомендовали в вычислительных экспериментах: модификации генетического алгоритма, муравьиного, роевого (пчелиной колонии), имитации отжига. Предложен и реализован обобщенный алгоритм, в котором исходной сети ставится в соответствие более простая сеть (сеть облета). Численный эксперимент в этом случае проведен для задачи маршрутизации по карте ГИС для городской инфраструктуры. Реализованы алгоритмы кластеризации, в которых первоначально пройденные маршруты уточняются с помощью алгоритмов 2-opt, имитации отжига и других метаэвристик. Дается сравнение применяемых алгоритмов и иллюстрация их работы.