비대칭 외판원문제에서 Out-of-Kilter 호를 이용한 Perturbation = Perturbation Using Out-of-Kilter Arc of the Asymmetric Traveling Salesman Problem

다국어 초록 (Multilingual Abstract)

This paper presents a new perturbation technique for developing efficient iterated local search procedures for the asymmetric traveling salesman problem(ATSP). This perturbation technique uses global information on ATSP instances to speed-up computation and to improve the quality of the tours found by heuristic method. The main idea is to escape from a local optima by introducing perturbations on the out-of-kilter arcs in the problem instance. For a local search heuristic, we use the Kwon which finds optimum or near-optimum solutions by applying the out-of-kilter algorithm to the ATSP. The performance of our algorithm has been tested and compared with known method perturbing on randomly chosen arcs. A number of experiments has been executed both on the well-known TSPLIB instances for which the optimal tour length is known, and on randomly generated instances. For 27 TSPLIB instances, the presented algorithm has found optimal tours on all instances. And it has effectively found tours near AP lower bound on randomly generated instances.

참고문헌 (Reference)

1 "외판원문제에서 국지해를 탈출하기 위한 비용완화법" 30 (30): 120-129, 2004

2 "비대칭 외판원문제에서 호의 후보집합 결정" 28 : 129-138, 2003

3 "비대칭 외판원문제에서 out-of-kilter 호의 특성" 3 (3): 117-124, 2003

4 "The Traveling Salesman Problem：A Case Study in Local Optimization Local Search in Combinatorial Optimization" Inc. 215-310, 1997

5 "The Traveling Salesman Problem and Minimal Spanning Tree" 18 : 1138-1162, 1970

6 "TSPLIB：A Traveling Salesman Problem Library" 3 : 376-384, 1991

7 "Perturbation：An Efficient Technique for the Solution of Very Large Instances of the Euclidean TSP" 8 (8): 125-133, 1996

8 "Large-step Markov Chains for the TSP Incorporating Local Search Heuristics" 11 : 219-224, 1992

9 "Application of the Out-of-Kilter Algorithm to the Asymmetric Traveling Salesman Problem" 54 : 1085-1092, 2003

10 "An Efficient Implementation of the Lin-Kernighan Traveling Salesman Heuristic" 126 : 106-130, 2000

11 "An Efficient Heuristic Algorithm for the Traveling Salesman Problem" 21 : 495-516, 1973

12 "A Patching Algorithm for the Nonsymmetric Traveling Salesman Problem" 8 : 561-573, 1979

13 "A Note on the Complexity of the Asymmetric Traveling Salesman Problem" 20 : 31-38, 1997