Perturbation using out-of-kilter arc of the asymmetric traveling salesman problem

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 optimum by introducing perturbations on the out-of-kilter arcs in the problem instance. For a local seach heuristic we use Kwon's method 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 algoithm has found optimal tours on all instances. And it has effectively found tours near the assignment problem lower bound on randomly generated instances.