论文部分内容阅读
分析了求解旅行商问题(traveling salesman problem,TSP)的4种贪婪构建型算法的特点,发现这类算法的最大缺点是在求解初期以贪婪的方式构建解,导致求解后阶段为初期的贪婪付出代价.本文在Held Karp模型基础上提出了一种改造TSP问题距离矩阵的方法——距离矩阵方差最小法(minimizing variance of distance matrix,MVODM),以降低这类算法构建初期的贪婪性,提高算法的总体求解质量.分别采用4种贪婪构建型算法结合和不结合MVODM两种方式,求解了TSPLIB标准库中54个算例,以验证MVODM的有效性.求解结果表明:MVODM能够非常有效地提高4种算法的求解质量,部分改进后的算法质量甚至超过很多世界一流的构建型算法,并且MVODM的执行效率非常高,当算例的规模达到2319时在本实验计算机上的耗时仅为0.076 s,算法的耗时增加量几乎可以忽略不计.
This paper analyzes the characteristics of four greedy algorithms for solving traveling salesman problem (TSP), and finds that the biggest drawback of this algorithm is that it constructs solutions in a greedy way in the initial stage of solution, resulting in the initial greedy solution Cost.This paper proposes a method of transforming the distance matrix of TSP problem based on Held Karp model-minimizing variance of distance matrix (MVODM), in order to reduce the greedy of the algorithm in the initial stage and improve the algorithm Of the total quality of the solution.Using four kinds of greedy construction algorithm combined with and without MVODM two ways to solve the TSPLIB standard library of 54 examples to verify the effectiveness of MVODM.The results show that: MVODM can be very effective to improve The quality of the four algorithms is improved, the quality of some of the improved algorithms is even higher than many world-class construction algorithms, and the execution efficiency of MVODM is very high. When the scale of the example reaches 2319, the time spent on the experimental computer is only 0.076 s, the algorithm’s time-consuming increase is almost negligible.