Applied tasks of multiagent routing problems

Applied network tasks of multiagent routing or (applied network tasks of multiagent routing или \(mTSP\)) arise in many application areas and lead to various models of pseudo-Boolean optimization. Such problems, as a rule, are \(NP\)--hard, for them exact algorithms are applicable only in the case of a small dimension of the original network (graph). Multiagency can be contained in the initial formulation or arise as a result of simplifying and reducing the dimension of the problem (decomposition, clustering). Models of such tasks in the author’s works arose when planning multi-day tourist routes to attractions; choosing routes by agents in emergency situations (when the infrastructure network may change); when using unmanned aerial vehicles, drones (\textit{БПЛА}) \(mTSP\) to build routes; in tasks of traversing clusters (bypassing communities social networks).\refpar The results of combination with \(mTSP\) network clustering and comparative analysis of algorithm compositions are given. It is important in the research process to take into account all available information, facts, knowledge, precedents both for building a hierarchy of models and for developing practical algorithmic solutions. The proposed research scenario \(mTSP\) can be promising for the development of intelligent multi-agent applied routing systems.

Keywords: multiagent traveling salesman problems (mTSP), applied routing algorithms, TSP clustering.