Efficiency Analysis of the Vertex Clustering in Solving the Traveling Salesman Problem

The TSP is the problem to find the shortest path in a graph visiting every nodes exactly once and returning to the start node. Due to the high complexity of TSP, there exists no algorithm for global exact optimization with polynomial cost. In order to provide an acceptable solution for real life problems, the TSP are usually solved with some heuristic optimization problem. The paper proposes a multi layered optimization model, where the node set is partitioned into clusters or into hierarchy of clusters. Based on the test experiments the proposed method is superior to the single level optimization method for both the TSP and MTSP problems.