Release Time:2019-03-10  Hits:

Indexed by: Journal Article

Date of Publication: 2011-04-15

Journal: 管理工程学报

Included Journals: CSSCI、ISTIC、PKU

Volume: 25

Issue: 2

Page Number: 95-102

ISSN: 1004-6062

Key Words: 双向扩展差额算法;两端延伸最近城市搜索法;启发式算法;TSP问题

Abstract: 旅行商(TSP)问题是典型的组合优化中的NP-hard难题.本文在最近城市搜索法和两端延伸最近城市搜索法基础上提出了双向扩展差额求解算法,并分析了算法的复杂度.采用以上三种算法求解了TSPLIB标准库中多个算例,比较结果表明本算法能够更快的找到更优的方案,具有更好的综合性能.