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

Authors: Sang-Ho K.; Young-Gun G.; Maing-Kyu K.

Source: Journal of the Operational Research Society, Volume 54, Number 10, October 2003 , pp. 1085-1092(8)

Buy & download fulltext article:

Price: $43.00 plus tax (Refund Policy)

Abstract:

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 times for 216 randomly generated instances from nine instance generators.Journal of the Operational Research Society (2003) 54, 1085–1092. doi:10.1057/palgrave.jors.2601614

Document Type: Research article

DOI: http://dx.doi.org/10.1057/palgrave.jors.2601614

Affiliations: 1: 1Hanyang University, Sa-dong, Ansan, Kyounggi-do, South Korea

Publication date: 2003-10-01