点击次数：

论文类型：期刊论文

发表时间：2015-01-01

发表刊物：中国科学. 信息科学

收录刊物：ISTIC、CSCD

卷号：45

期号：8

页面范围：1060-1079

ISSN号：1674-7267

关键字：组合优化; 旅行商问题; 构建型算法; 计算方法; 通用策略

摘要：分析了求解旅行商问题(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,算法的耗时增加量几乎可以忽略不计.