管理工程学报
管理工程學報
관리공정학보
JOURNAL OF INDUSTRIAL ENGINEERING AND ENGINEERING MANAGEMENT
2011年
2期
95-102
,共8页
双向扩展差额算法%两端延伸最近城市搜索法%启发式算法%TSP问题
雙嚮擴展差額算法%兩耑延伸最近城市搜索法%啟髮式算法%TSP問題
쌍향확전차액산법%량단연신최근성시수색법%계발식산법%TSP문제
旅行商(TSP)问题是典型的组合优化中的NP-hard难题.本文在最近城市搜索法和两端延伸最近城市搜索法基础上提出了双向扩展差额求解算法,并分析了算法的复杂度.采用以上三种算法求解了TSPLIB标准库中多个算例,比较结果表明本算法能够更快的找到更优的方案,具有更好的综合性能.
旅行商(TSP)問題是典型的組閤優化中的NP-hard難題.本文在最近城市搜索法和兩耑延伸最近城市搜索法基礎上提齣瞭雙嚮擴展差額求解算法,併分析瞭算法的複雜度.採用以上三種算法求解瞭TSPLIB標準庫中多箇算例,比較結果錶明本算法能夠更快的找到更優的方案,具有更好的綜閤性能.
여행상(TSP)문제시전형적조합우화중적NP-hard난제.본문재최근성시수색법화량단연신최근성시수색법기출상제출료쌍향확전차액구해산법,병분석료산법적복잡도.채용이상삼충산법구해료TSPLIB표준고중다개산례,비교결과표명본산법능구경쾌적조도경우적방안,구유경호적종합성능.