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

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

Полиномиально разрешимая задача назначения может быть использована для определения необходимого количества агентов и построения их маршрутов. Рассматривается подкласс задач псевдобулевой оптимизации с ограничениями в виде дизъюнктивной нормальной формы (ДНФ), к которым сводится задача mTSP. Задачи в этой форме полиномиально разрешимы и позволяют объединить знания о структуре сети, требования к прохождению маршрутов агентами (процедуры поиска) и эффективные алгоритмы логического вывода на ограничениях в виде ДНФ. Этот подход является теоретическим обоснованием для разработки многоагентной системы управления, ведущей к решению mTSP.

В рамках интеллектуального планирования, с использованием ресурсов и возможностей, с учетом ограничений для каждого агента на выбранных кластерах сети достигается построение общего решения для всей сложной сети.