Эта публикация цитируется в 1 статье

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

М. С. Германчук

Крымский федеральный университет им. В. И. Вернадского, Таврическая академия, факультет математики и информатики, просп. Академика Вернадского, 4, Симферополь, 295007, Российская Федерация

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

Ключевые слова: псевдобулевая оптимизация с ДНФ ограничениями, полиномиальное решение задачи многих коммивояжеров, алгоритмы.

УДК: 519.16

MSC: 90C27

DOI: 10.37279/1729-3901-2020-19-4-30-55