基于求解TSP问题的双向扩展差额算法  

Two Directions Moving With Difference Algorithms to Solve Traveling Salesman Problems

作　　者：饶卫振[1] 金淳[1] 黄英艺[1] 

机构地区：[1]大连理工大学系统工程研究所,辽宁大连116024

出　　处：《管理工程学报》2011年第2期95-102,共8页Journal of Industrial Engineering and Engineering Management

基　　金：国家自然科学基金资助项目(70571008);辽宁省自然科学基金资助项目(20062184)

摘　　要：旅行商(TSP)问题是典型的组合优化中的NP-hard难题。本文在最近城市搜索法和两端延伸最近城市搜索法基础上提出了双向扩展差额求解算法,并分析了算法的复杂度。采用以上三种算法求解了TSPLIB标准库中多个算例,比较结果表明本算法能够更快的找到更优的方案,具有更好的综合性能。Traveling salesman problems（TSP） are an optimization problem that has been studied extensively.The primary objective of TSP is to locate the shortest route for each customer visit by salespersons.The approximate algorithm is a better choice than the exact algorithms in order to solve TSP.Approximate algorithms can be divided into two classes：construction algorithms and improvement algorithms.A construction algorithm builds a tour with no attempts to improve tour logistics after it is constructed.Algorithms designed to solve TSP can be constructed efficiently.Given the time constraint,these algorithms offer approximate solutions to TSP programs and initial solutions to the improvement of tour heuristics.Upper bounds for exact algorithms can then be obtained.This paper presented two construction algorithms.The first algorithm was to construct the TDMDA（two directions moving with difference algorithm） based on the searching algorithm of the nearest neighbor city.The second algorithm was to construct BENCS（both ends extending nearest city searching algorithm）.Section 1 defined TSP and displayed concrete steps of NNCS and BENCS executions.We showed TDMDA key concepts and steps in detail.NNCS departs from an arbitrary city,and then successively visits the closest unvisited city.BENCS is a construction algorithm based on NNCS.Section 2 showed key TDMDA concepts and described TDMDA steps used to solve symmetric and asymmetric TSP,respectively.A NNCS solution begins with a city and grows a fragment at only one end,while BENCS allows a fragment to grow at both ends and performs two nearest neighbor searches to add one city each to both ends of a fragment solution.TDMDA,a construction algorithm based on BENCS,uses the same rules as BENCS＇,but extending directions between two ends or nearest unvisited cities.TDMDA deducts the distance between the end cities and its nearest city from the second nearest city.TDMDA builds a rule using start cities to assist us in yielding better solutions.Section 3 evaluated TDM

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

分 类 号：F502[经济管理—产业经济]