비대칭 외판원문제에서 후보집합을 이용한 지역해 탈출 방법

Abstract

외판원문제는 최적해를 구하는 다항식 앨고리듬이 발견되지 않은 NP-Hard 문제이므로 문제의 크기가 커질수록, 즉 교점과 호의 개수가 증가할수록 최적해를 구하는 데 걸리는 시간이 지수적으로 증가한다. 따라서 계산량을 줄이기 위해서 일부의 호들로 구성되는 후보집합을 고려할 필요가 있다. 후보집합이란 최소 비용의 해밀턴 순환로에 포함될 가능성이 높은 호들의 집합이다. 모든 호를 고려하지 않고 후보집합만을 사용하면 효율적으로 해민턴 순환로를 찾을 수 있다. 각 교점에서 나가는 호의 비용을 오름차순으로 정렬하고 호의 후보집합의 개수를 순차적으로 증가시켜 가며 지역해 탈출을 시도한다. 본 연구에서는 두 종류의 기존 해법을 사용했는데 교점수가 많은 문제에서 값이 개선되는 것을 볼 수 있었고 지역해를 탈출하는 횟수가 증가되는 것을 볼 수 있었다. 이는 교점수가 많은 문제이지만 후보집합이 호의 개수는 적으면서 순환로를 개선시킬 가능성이 높은 호들로 이루어져 있고 이를 순차적으로 사용하기 때문이다. 본 연구에서 제안한 앨고리듬을 적용하면 적절한 시간내에 지역해를 탈출하는 해를 구할 수 있고 특히 교점수가 많은 대형 외판원문제에서 효율적이다.; The Traveling Salesman Problem is a NP-hard problem that doesn’t have an algorithm of a polynomial complexity As the size of a problem, i.e., the number of nodes and arcs, becomes larger, the complexity to get an optimal solution increases exponentially. Therefore, to reduce the computation time, we need to consider a candidate set of arcs. The candidate set is a group of arcs which is more likely to be included in Hamiltonian cycle of the minimum cost. We can find a Hamiltonian cycle with only a candidate set, not considering all the arcs. We try to escape from a local optimum, arranging the cost of arcs coming from each nodes in ascending order. In this paper, with using two kinds of local search algorithm we can see that the result is improved in the problems those have many nodes and that the number of escape from local optimum is also increasing. If we apply the algorithm suggested in this paper, we can escaping from local optimum in a reasonable amount of time. In particular, it is efficient to solve a problem in the big traveling salesman problem which has many nodes.