Application of the out-of-kilter algorithm to the asymmetric traveling salesman problem

This paper presents a heuristic method that finds optimum or near-optimum solutions to the asymmetric traveling salesman problem. The method uses the out-of-kilter algorithm to search for a neighbourhood. When subtours are produced by a flow-augmenting path of the out-of-kilter algorithm, it patches them into a Hamiltonian cycle. It extends the neighbourhood space by exchanging an even number of arcs, and it also exchanges arcs by a non-sequential primary change. Instances from real applications were used to test the algorithm, along with randomly generated problems. The new heuristic algorithm produced optimum solutions for 16 out of 28 real-world instances from TSPLIB and other sources. Also, compared with four efficient heuristics, it produced the best solutions for all except six instances. It also produced relatively good solutions in reasonable time for 216 randomly generated instances from nine instance generators.