A Multilevel Approach to the Travelling Salesman Problem

Chris Walshaw ()
Additional contact information
Chris Walshaw: Computing and Mathematical Sciences, University of Greenwich, Old Royal Naval College, Greenwich, London, SE10 9LS, United Kingdom

Operations Research, 2002, vol. 50, issue 5, 862-877

Abstract: We motivate, derive, and implement a multilevel approach to the travelling salesman problem. The resulting algorithm progressively coarsens the problem, initialises a tour, and then employs either the Lin-Kernighan (LK) or the Chained Lin-Kernighan (CLK) algorithm to refine the solution on each of the coarsened problems in reverse order. In experiments on a well-established test suite of 80 problem instances we found multilevel configurations that either improved the tour quality by over 25% as compared to the standard CLK algorithm using the same amount of execution time, or that achieved approximately the same tour quality over seven times more rapidly. Moreover, the multilevel variants seem to optimise far better the more clustered instances with which the LK and CLK algorithms have the most difficulties.

Keywords: Networks/graphs; heuristics: meta-heuristic for TSP; Mathematics; combinatorics: multilevel refinement for combinatorial problems; Simulation; applications: optimization by multilevel refinement (search for similar items in EconPapers)
Date: 2002
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (3)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.50.5.862.373 (application/pdf)

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:inm:oropre:v:50:y:2002:i:5:p:862-877

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().