Solving Methods of Traveling Salesman Problem : 巡廻外販員問題에 대한 解法

국문 초록 (Abstract)

본 논문은 순회외판원문제에 대한 몇 가지 해법을 소개하고 순회외판원문제의 효과적인 근사해를 구하기 위하여 새로운 알고리즘을 제공하고자 한다. 주어진 알고리즘이 효과적인 알고리즘인지 과학적으로 판단하기 위해서는 최악의 실행시간뿐만 아니라 평균 실행시간까지 조사해야하지만 본 논문에서는 최악의 실행시간으로만 한정하기로 한다.
제안된 새로운 알고리즘은 다음과 같은 4단계로 시행된다.
1단계 : 각 도시간 비용을 크기 순으로 정열한 후 비용이 작은 r개의 도시를 제외한 (n-r)개의 도시만 선택
2단계 : (n-r)개의 도시를 최근거리인접점 알고리즘을 이용하여 초기해를 구한다.
3단계 : 초기해에 분지한계법을 이용하여 부분최적해를 구한다.
4단계 : 부분최적해와 제외한 r개의 도시로 근사해를 구한다.
최악의 실행시간으로 한정하여 비교·분석한 결과 제안된 알고리즘의 실행시간은 O((n-r)!)로 분지한계법보다는 실행시간이 더 빠르지만 최근거리인접점 알고리즘이나 k-optimal 알고리즘보다는 더 느린 것으로 나타났다.

다국어 초록 (Multilingual Abstract)

We introduce the traveling salesman problem and survey several solving methods for it. And we suggest the new algorithm of solving methods for the traveling salesman problem. To observe efficiency with scientific exactitude of this algorithm, we compare and analyze not only the worst-case running time but also average-case between suggested algorithm and other, but we restrict only the worst-case running time in this paper and compute it.
The algorithm for an approximate solution of the TSP is following steps:
Step 1. The number of costs of all cities, that is n^(2), is sort in the order of their (small) size by Merge sort. And choose n-r cities among n cities, where r(＜n)) is the number of cities with small cost among costs sort.
Step 2. Initial assignment with n-r cities : Find the initial solution using nearest neighbor algorithm. It is unnecessary that the initial solution is tour at this place.
Step 3. Find partial optimal solution using Branch and bound algorithm for n-r cities.
Step 4. Find approximate solution from partial optimal solution for n-r cities and r cities.
Running time of suggested algorithm is O((n-r)!) in the worst-case. From a point of view of worst-case running time, O((n-r)!) is faster than that of branch and bound, but slower than that of nearest neighbor and k-optimal.

목차 (Table of Contents)

• CONTENTS = ⅰ
• (國文抄錄) = ⅱ
• Ⅰ. INTRODUCTION = 1
• Ⅱ. MATHEMATICAL FORMULATION OF TSP = 3
• Ⅲ. ALGORITHM ANALYSIS = 6
• Ⅳ. HEURISTIC AND APPROXIMATE ALGORITHMS FOR THE TSP = 12
• 4.1. Nearest neighbor algorithm. = 13
• 4.2. Branch and Bound algorithm. = 13
• 4.3. K-Optimal algorithm. = 15
• 4.4. Genetic algorithm. = 16
• Ⅴ. SUGGESTION OF NEW ALGORITHM FOR SOLVING METHOD OF TSP = 19
• Ⅵ. CONCLUSION = 29
• REFERENCES = 30
• ABSTRACT = 31