Прикладные задачи многоагентной маршрутизации

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

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

Аннотация: Прикладные сетевые задачи многоагентной маршрутизации (applied network tasks of multiagent routing или $mTSP$) возникают во многих прикладных областях и приводят к различным моделям псевдобулевой оптимизации. Такие задачи, как правило, являются $NP$-трудными, для них точные алгоритмы применимы только в случае малой размерности исходной сети (графа). Модели таких задач в работах автора возникли при планировании многодневных туристических маршрутов по достопримечательностям; выборе маршрутов агентами в условиях чрезвычайных ситуаций; при использовании беспилотных летающих аппаратов, дронов (БПЛА) $mTSP$ для построения маршрутов; в задачах обхода кластеров (обход сообществ социальных сетей). Приведены результаты согласованной с $mTSP$ кластеризации сети и сравнительный анализ композиций алгоритмов. Важным в процессе исследования является учет всей имеющейся информации, фактов, знаний, прецедентов как для построения иерархии моделей, так и для разработки практических алгоритмов решения. Предложенный сценарий исследования $mTSP$ может быть перспективным для разработки интеллектуализированных многоагентных систем прикладной маршрутизации.

Ключевые слова: multiagent traveling salesman problems ($mTSP$), прикладные алгоритмы маршрутизации, согласованная кластеризация.

УДК: 519.16

MSC: 90C27