一类求解TSP构建型算法的通用改进策略
摘要
In this paper, we analyze the characteristics of four construction heuristics for solving the traveling salesman problem (TSP) and determine that the greatest common weakness of this type of heuristic lies in the greedy construction of solutions during the initial search period. Based on the Held Karp model, we propose the method of Minimizing Variance of Distance Matrix (MVODM) to transform the distance matrix for TSP problems. This method could reduce the greediness of construction during the initial period and improve the overall quality of the solutions. To evaluate the effectiveness of the method, we solve 54 benchmark instances from TSPLIB by using four greedy construction heuristics with and without MVODM for comparison. The results show that MVODM could greatly enhance the solution quality of four heuristics, and some improved heuristics even outperform many world-leading construction heuristics. Moreover, the efficiency of MVODM is so high that an instance size of 2319 cities was run in only 0.076 s on our computer. The increased computation time caused by MVODM could largely be omitted.