Research of Replaceability of the Distance Matrix With Preorder Matrix in Traveling Salesman Problem

The well-known and studied combinatorial optimization problem is The Traveling Salesman Problem (TSP), in which needs to find the most profitable route for the traveler crossing from starting city, through all principal cities once and then returning to the original one. Interest in TSP caused by its practical significance with considerable complexity and a large number of possible spheres of use at present and future such as delivery, construction of navigation routes, optimization of flight routes of military aircraft, etc. This study proposed one of the possible ways to represent this problem, called the Preorder Matrix. The main idea is to replace the weight matrix that represents the TSP with a matrix, which consists of elements representing an ordinal index of unique weight matrix values sorted in ascending order. Such the replacement allows creating classes of problems of one complexity represented by the Preorder Matrix. The objective of the study is to evaluate the possibility and adequacy of using the Preorder Matrix for the TSP. For this assessment, we use open data for symmetric and asymmetric TSP with best-known solutions (weight and path(s)) and two algorithms Method Branch and Bound and LKH-3 that give us the exact and approximate solution. The main steps of research are to generate the Preorder Matrix for these tasks, evaluate the percentage of differences in the resulting weight of the Hamiltonian path for the real task and Hamiltonian path getting from Preorder solution, but applied to a real task. Such an experiment gives us reason to evaluate the adequacy of using the Preorder Matrix as the criteria of the complexity of TSP tasks.