Hits:
Indexed by:期刊论文
Date of Publication:2015-01-01
Journal:中国科学. 信息科学
Included Journals:ISTIC、CSCD
Volume:45
Issue:8
Page Number:1060-1079
ISSN No.: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,算法的耗时增加量几乎可以忽略不计.