Specifics of building multiagent routes in hierarchical networks

The article discusses applied models of multiagent routing, taking into account the specifics of the organization of the network structure, the goals of the system and the local goals of agents. The class of problems of multiple traveling salesmen (mTSP) of different levels of hierarchycal clustering (HCmTSP) is singled out. The construction of HCmTSP routes is consistent with the natural clustering of a complex infrastructure network. An overview of problems, methods and algorithms based on various heuristics is given. The hierarchical clustering of the network is distinguished. It is shown that, depending on the logistical goals, a different type of clustering consistent with mTSP should be chosen. It is shown that the task of constructing multiagent mTSP routes in complex networks with a hierarchical vertex structure has numerous applications. For example, it is necessary to deliver goods from a certain center to regional centers, where they will be overloaded and delivered to consumers in the shortest time or at the lowest cost. It combines cluster traversal tasks (cluster traveling salesman task) and local traveling salesman tasks on each cluster. Other models are associated with the use of unmanned aerial vehicles - drones (UAVs) in the tasks of monitoring infrastructure networks. The original network is matched with a simpler flyby network and the original task of many traveling salesmen (mTSP) is simplified. Modern information approaches lead to new formulations of multiagent routing tasks in social networks with a hierarchical structure of user communities. To study hierarchical mTSP, modern approaches based on exact and approximate algorithms are used, using heuristics, metaheuristics, genetic algorithms and a neural network approach, intellectualized big data processing. The task of developing hierarchical routing algorithms for many agents in infrastructure networks is associated with: description of hierarchical clustering algorithms and their application to routing tasks; coordination of hierarchical clustering with the task of building routes on clusters; construction of hierarchical routing algorithms combining cluster traversal and construction of traveling salesmantype routes on clusters. The hierarchical mTSP structure is distinguished with a set of clusters of the lower level of the hierarchy, several bases (warehouses for transshipment of goods) and a base (vertex) of the highest level. It is shown that when developing HCmTSP algorithms, clustering consistent with the traveling salesman’s task is significantly used. Having analyzed the clustering efficiency based on the decomposition of the original problem, clustering algorithms consistent with TSP are proposed. Depending on one or many separation centers, their hierarchy, the structure of the network as a whole, it is necessary to choose the appropriate clustering. The article provides an overview of sources and a description of methods for solving mTSP based on clustering. The formulation of the problem is concretized and the results of a numerical experiment confirming the theoretical positions are presented. The results of a computational experiment on clustering types and routes are compared. Preference is given to hierarchical clustering consistent with the HCmTSP route hierarchy.