Metaheuristic algorithms for multi-agent routing problems

The problems of constructing routes in complex networks by many sales agents are considered. Formalization leads to problems of pseudo-Boolean discrete optimization with restrictions that take into account the specifics of route construction. The sparsity of the constraint matrix makes it possible to apply decomposition approaches and network clustering. The development of approximate algorithms for selecting routes in complex networks involves taking into account the properties of the network structure, its complexity, the presence of restrictions, regulations, reachability conditions, and the number of sales agents. It is shown that the solution of routing problems can be based on the application of a multi-agent approach in combination with clustering (decomposition) of the original problem and metaheuristics. Multi-agent systems with swarm intelligence are used to solve complex discrete optimization problems that cannot be effectively solved by classical algorithms. The agent model for a complex network of problems like many traveling salesmen becomes an intellectualized system that defines heuristic algorithms for finding the optimal solution by reactive agents (that follow the rules laid down in them). The compositions of the algorithms described in detail, which have proven themselves well in computational experiments, are used; those are modification of the genetic algorithm, ant colony optimization, artificial bee colony algorithm, simulated annealing. A generalized algorithm is proposed and implemented, in which a simpler network (a flyover network) is matched to the source network. In this case, a numerical experiment was performed for the problem of routing on a GIS map for urban infrastructure. Clustering algorithms are implemented, in which the initially traversed routes are refined using 2-opt algorithms, simulated annealing, and other metaheuristics. A comparison of the algorithms used and an illustration of their operation are given.