CAJ | 학술논문

旅行商（TSP）问题是典型的组合优化中的NP-hard难题。本文在最近城市搜索法和两端延伸最近城市搜索法基础上提出了双向扩展差额求解算法,并分析了算法的复杂度。采用以上三种算法求解了TSPLIB标准库中多个算例,比较结果表明本算法能够更快的找到更优的方案,具有更好的综合性能。
여행상（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 TDMDA performance.We used TDMDA,NNCS and BENCS to solve 15 TSPLIB instances.Computational results showed that TDMDA can obtain a better solution to TSP problems and consume more running time than the other two algorithms.TDMDA was able to derive the best solution and consume the smallest total running time in all 15 instances.The complexity of these three algorithms was analyzed and compared.We compared the complexity of these three algorithms,and our analysis results showed that all the three algorithms have the same complexity O（n2）.We objectively evaluated TDMDA performance In summary,TDMDA is a better algorithm to locate the shortest route for each customer visit by salespersons than NNCS and BENCS.TDMDA can help calculate the shortest route and is an effective and efficient construction algorithm.