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

K Sang-Ho (), G Young-Gun () and K Maing-Kyu ()
Additional contact information
K Sang-Ho: Hanyang University, Sa-dong, Ansan
G Young-Gun: Hanyang University, Sa-dong, Ansan
K Maing-Kyu: Hanyang University, Sa-dong, Ansan

Journal of the Operational Research Society, 2003, vol. 54, issue 10, 1085-1092

Abstract: 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.

Keywords: traveling salesman; heuristics; networks and graphs (search for similar items in EconPapers)
Date: 2003
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1057/palgrave.jors.2601614 Abstract (text/html)
Access to full text is restricted to subscribers.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:pal:jorsoc:v:54:y:2003:i:10:d:10.1057_palgrave.jors.2601614

Ordering information: This journal article can be ordered from
http://www.springer. ... search/journal/41274

DOI: 10.1057/palgrave.jors.2601614

Access Statistics for this article

Journal of the Operational Research Society is currently edited by Tom Archibald and Jonathan Crook

More articles in Journal of the Operational Research Society from Palgrave Macmillan, The OR Society
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().