비대칭 외판원문제에서 out-of-kilter 호의 특성

Abstract

As the traveling salesman problem is NP-hard, many heuristics have been developed. Among heuristics, Kwon algorithm efficiently finds optimum or near-optimum by applying the optimal algorithm, Out-of-Kilter to the asymmetric traveling salesman problem. But characteristics of out-of-kilter arc of the algorithm are not clear. This paper presents the properties of out-of-kilter arcs, change of the number of out-of-kilter arcs, residual number of outof-kilter arcs, and the number of exchanging arcs when we implement the Kwon algorithm. For test bed, we used 27 real-world TSPLIB problems and 220 randomly generated problems. Test results show that initial number of out-ofkilter arcs is affected by the range of cost and initial solution quality, and the algorithm exchanges general odd or even number of arcs. And average 2.2% of the number of initial out-of-kilter arcs was remained when it found a solution.