비대칭 외판원문제에서 호의 후보집합 결정

Abstract

The traveling salesman problem (TSP) is an NP-hard problem. As the number of nodes increases, it takes a lot of time to find an optimal solution. Instead of considering all arcs, if we select and consider only some arcs more likely to be included in an optimal solution. We can find efficiently an optimal solution. Arc candidate set is a group of some good arcs. For the lack of study in the asymmetric TSP. It needs to research arc candidate set for the asymmetric TSP systematically. In this paper we suggest a regression function determining arc candidate set for the asymmetric tsp. We established the function based on 2100 experiments. And we proved the goodness of fit for the model through various 787problems. The result showed that the optimal solutions obtained from our arc candidate set are equal to the ones of original problems. We expect that this function would be very useful to reduce the complexity of TSP.