location: Current position: Home >> Scientific Research >> Paper Publications

一类求解TSP构建型算法的通用改进策略

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,算法的耗时增加量几乎可以忽略不计.

Pre One:一类动态车辆路径问题模型和两阶段算法

Next One:考虑节点综合重要度的物流网络级联失效模型