Release Time:2019-03-11  Hits:

Indexed by: Journal Article

Date of Publication: 2015-01-01

Journal: 中国科学. 信息科学

Included Journals: CSCD、ISTIC

Volume: 45

Issue: 8

Page Number: 1060-1079

ISSN: 1674-7267

Key Words: 组合优化; 旅行商问题; 构建型算法; 计算方法; 通用策略

Abstract: 分析了求解旅行商问题(traveling salesman problem,
   TSP)的4种贪婪构建型算法的特点,发现这类算法的最大缺点是在求解初期以贪婪的方式构建解,导致求解后阶段为初期的贪婪付出代价.本文在Held
   Karp模型基础上提出了一种改造TSP问题距离矩阵的方法距离矩阵方差最小法(minimizing variance of distance
   matrix,
   MVODM),以降低这类算法构建初期的贪婪性,提高算法的总体求解质量.分别采用4种贪婪构建型算法结合和不结合MVODM两种方式,求解了TSPLI
   B标准库中54个算例,以验证MVODM的有效性.求解结果表明:
   MVODM能够非常有效地提高4种算法的求解质量,部分改进后的算法质量甚至超过很多世界一流的构建型算法,并且MVODM的执行效率非常高,当算例的规
   模达到2319时在本实验计算机上的耗时仅为0.076 s,算法的耗时增加量几乎可以忽略不计.