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

关键词：双向扩展差额算法 两端延伸最近城市搜索法 启发式算法 tsp问题 

单位：大连理工大学系统工程研究所 辽宁大连116024