Analysis of metaheuristics for multi-agent routing problems

The article presents a numerical experiment dedicated to solving the Traveling Salesman Problem (TSP) using various metaheuristics on a data set from the TSPLIB library. The main goal of the experiment was to determine the most efficient and accurate methods for finding routes. A brief description of each of the studied algorithms is given. An approach is described for collecting graph metric characteristics that are unique for the network structure. In the context of TSP, these metrics may include node degrees, edge weights, connectivity, and other properties that describe the relationships between cities. By using metadata, it is possible to obtain a generalized description of the network, which aids in understanding its complexity and properties. A detailed description of the algorithm for calculating the statistics of weight distribution in a graph is also given. Understanding the weight distribution is essential in determining the characteristics of the TSP instances, such as the presence of clusters or patterns that might impact the choice of metaheuristic. The application of this algorithm to the graph made it possible to automate the selection of the reference distance parameter for hierarchical clustering. Hierarchical clustering is a method used to group similar items together based on their characteristics. By identifying cohesive point sets using this approach, it can potentially discover patterns or substructures in the TSP instances. The experiment showed that all the applied metaheuristics are able to find approximate solutions for TSP on various data sets. However, depending on the characteristics of the problem, some methods proved to be more efficient and accurate than others. The final table contains a list of the best algorithms with an indication of the number of times when each of them produced the best solution among the others. It could provide valuable insights into which metaheuristics work best under certain conditions. Based on the results obtained, it is planned to establish a link between the graph metadata and the results, which will allow developing an intelligent system for choosing the optimal metaheuristic. The choice of metaheuristics is recommended to be carried out taking into account the specifics of the TSP, such as the number of cities, geographical characteristics, accuracy requirements, and execution time. Combining different metaheuristics is suggested as a possible approach to improve the results in solving the TSP. Hybrid approaches that leverage the strengths of multiple algorithms could lead to better solutions, especially for complex TSP instances. The findings in the article have practical implications for real-world routing and scheduling problems that can be modeled as TSP instances. By understanding the performance of different metaheuristics based on the problem’s characteristics, practitioners can make informed decisions on selecting the most suitable approach for their specific needs. In summary, the article’s numerical experiment, which explores the application of various metaheuristics to solve the TSP problem, yields valuable insights into the efficiency and effectiveness of these algorithms. By considering the graph metadata and characteristics of TSP instances, researchers aim to develop an intelligent system that can select the best metaheuristic for different scenarios, leading to improved solutions for real-world routing and optimization problems.