Построение многоагентных маршрутов в сети с иерархией вершин

Аннотация

Многоагентная задача маршрутизации типа коммивояжера является NP-трудной. Для построения приближенных решений важен учет всей имеющейся информации о структуре сети, ограничениях и целях. Выделяется класс задач (характерный для распределения ресурсов в инфраструктурных сетях), в которых введен иерархический порядок вершин. Рассматриваются прикладные задачи многоагентной маршрутизации mTSP на таких сетях с учетом разного уровня иерархии вершин и кластеризации сети (HCmTSP). Построение маршрутов HCmTSP согласовано с естественной кластеризацией сложной инфраструктурной сети. Приводится обзор задач, методов и алгоритмов, основанных на разных эвристиках. Показано, что в зависимости от логистических целей может быть выбран различный тип кластеризации, согласованной с mTSP. Сравниваются результаты вычислительного эксперимента по типам кластеризации и маршрутам. Приводятся результаты синтеза маршрутов двух уровней иерархии. Разработаны и реализованы алгоритмы построения маршрутов mTSP с одним центром (базой) и синтеза двухуровневых маршрутов обхода кластеров и маршрутов TSP на кластерах. В задаче mTSP с одним выделенным центром для построения начальных маршрутов исследуется гибридный алгоритм распределения вершин по кругу в зависимости от угла, с дальнейшим разбиением на кластеры и поиском TSP агентами на каждом кластере. Используются эвристики нескольких муравьиных колоний. В задаче синтеза базовый алгоритм имитации отжига сравнивается с решателем Concorde. Приведены численные результаты для известных тестовых наборов данных и для реальных данных городской инфраструктуры. Работа предназначена для отбора алгоритмов, их тестирования и проведения вычислительных экспериментов и наполнения программного комплекса: построение многоагентных маршрутов в сложных сетях с иерархией вершин.