Metaheuristics in related routing problems such as many traveling salesmen

O. O. Makarov

Taurida Journal of Computer Science Theory and Mathematics, no. 3 (2022), pp. 80-102

Résumé

Based on the proximity of routing problems in terms of meta-information, the paper presents the stage of forming databases for training an intelligent system to select metaheuristic algorithms for solving the multi-agent routing problem. The closeness of two routing problems is determined by the closeness of their mathematical models and the closeness of the fragments of a complex network involved in the solution. The description of the method of determining the proximity of two graphs based on finding the weighted metric distance between the vectors of metaheuristic parameters of the corresponding graphs is given. A formal approach to solving the routing problem on the basis of proximity problems is described. The stages of forming the solution of the original problem and the close problem are shown. The experiment confirming the hypothesis that the vectors of metaheuristic characteristics of close problems are at a small distance from each other is shown. Auxiliary experiments showing the maximum allowable difference between graphs at which they are considered close are also described. In addition, an experiment is presented to prove the hypothesis that a metaheuristic algorithm that works optimally for a particular problem will also work optimally for a close one. The description of the structure of the intellectualized system for the choice of metaheuristics is given and the basic principles of the system’s work are formed. In the solution of multi-agent problems of the type of a traveling salesman of large dimensionality, a coordinated decomposition into local cluster routing problems is performed. Suitable algorithms are selected at the local level. Experimental results of solving the traveling salesman problems using various metaheuristics on TSPLIB data are presented. Efficient route finding algorithms are identified. The experiment showed that most of the applied metaheuristics allow to find approximate or optimal solutions. A list of the best algorithms in terms of accuracy is given, which are planned to be used in the development of an intelligent system for selecting metaheuristics, taking into account the specifics of the problem (network structure and complexity, accuracy, time). A combination of metaheuristics that can lead to optimal results is assumed.

Détail

Keywords: traveling salesman problem, multiple traveling salesman problem, problem proximity, metaheuristics, graph metadata.
Mots-clés : TSPLIB