Release Time:2019-03-10  Hits:

Indexed by: Journal Article

Date of Publication: 2011-08-15

Journal: 系统工程理论与实践

Included Journals: Scopus、CSCD、ISTIC、PKU、EI

Volume: 31

Issue: 8

Page Number: 1419-1428

ISSN: 1000-6788

Key Words: 旅行商问题;混合算法;最近邻域算法;插入算法

Abstract: 研究了求解旅行商问题(TSP)的构建型启发式算法中的最近邻域算法和插入算法的特点,集最近邻域算法求解速度快、插入算法求解质量高的优点,提出了一种最近邻域与插入混合算法.分析了混合算法的合理性、复杂度及参数取值,并分别采用以上三种算法求解了TSPLIB标准库中多个算例,结果表明混合算法的求解速度接近最近邻域算法,对城市数量小于1000的小规模TSP问题的求解质量与插入算法相当,而对大规模TSP问题的求解质量明显优于插入算法.