Multi-agent route planning in hierarchical networks

Abstract

The article presents a study on the multi-agent routing problem of the traveling salesman type, which is known to be NP-hard. To construct approximate solutions, it is essential to consider all available information about the network structure, constraints, and goals. In this regard, the research identifies a class of problems characterized by a hierarchical order of nodes, which is typical for resource allocation in infrastructure networks. The study focuses on applied problems of multi-agent mTSP routing in such networks, considering different levels of vertex hierarchy and network clustering (HCmTSP). The paper emphasizes the significance of constructing HCmTSP routes that are consistent with the natural clustering of complex infrastructure networks. An overview of tasks, methods, and algorithms based on different heuristics is provided. The analysis indicates that the choice of clustering consistent with mTSP depends on logistic goals, and the paper presents computational experiment results for clustering types and routes. Furthermore, the research offers synthesis results for routes of two hierarchy levels and develops and implements algorithms for constructing single-center mTSP routes and the synthesis of two-level cluster avoidance routes and TSP routes on clusters. In the mTSP problem with a single dedicated center, the paper investigates a hybrid algorithm for distributing vertices in a circle, followed by partitioning into clusters and searching for TSP by agents on each cluster, using several ant colony heuristics. For the synthesis problem, the basic annealing simulation algorithm is compared with the Concorde solver, and numerical results are provided for known test datasets and real urban infrastructure data. The research is aimed at aiding in algorithm selection, testing, and computational experiments, as well as contributing to the development of a software package for constructing multi-agent routes in complex networks with a hierarchy of vertices.