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

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

Ключевые слова: задача коммивояжера, задача нескольких коммивояжеров, близость задач, TSPLIB, метаэвристика, метаданные графа