Metaheuristic Algorithms for Multiagent Routing Problems

• Published in: Automation and remote control 2021-10, Vol.82 (10), p.1787-1801
• Main Authors: Germanchuk, M. S., Lemtyuzhnikova, D. V., Lukianenko, V. A.
• Format: Article
• Language: English
• Subjects: Algorithms; Ant colony optimization; Boolean algebra; CAE) and Design; Calculus of Variations and Optimal Control; Optimization; Clustering; Complexity; Computer-Aided Engineering (CAD; Control; Control Sciences; Decomposition; Genetic algorithms; Heuristic methods; Mathematics; Mathematics and Statistics; Mechanical Engineering; Mechatronics; Multiagent systems; Optimization; Robotics; Route selection; Sales; Search algorithms; Simulated annealing; Swarm intelligence; Systems Theory
• ISSN: 0005-1179; 1608-3032
• DOI: 10.1134/S0005117921100155

The problems of constructing routes in complex networks by many sales agents are considered. Formalization leads to pseudo-Boolean discrete optimization problems with constraints that take into account the specifics of route construction. The sparsity of the constraint matrix permits one 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 multiagent approach in combination with clustering (decomposition) of the original problem and metaheuristics. Multiagent systems with swarm intelligence are used to solve complex discrete optimization problems that cannot efficiently be solved by classical algorithms. The agent model for a complex network of a problem of the many traveling salesmen type becomes an intelligent system that defines heuristic algorithms for finding the optimal solution by reactive agents (that follow the rules laid down in them). We use and describe in detail the composition of the algorithms, which have proven themselves well in computational experiments; those are a modification of the genetic algorithm, ant colony optimization, artificial bee colony algorithm, and simulated annealing. A generalized algorithm is proposed and implemented in which a simpler network (a flyover network) is matched to the source network. Here a numerical experiment was carried out 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.