Determination of arc candidate set for the asymmetric traveling salesman

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 787 problems. The result showed that the optimal solutions obtained from our arc candidate set are equal for the ones of the original problems. We expect that this function would be very useful to reduce the complexity of TSP.