# A multilevel approach to the travelling salesman problem

Walshaw, Chris
(2002)
*A multilevel approach to the travelling salesman problem.*
Operations Research, 50 (5).
pp. 862-877.
ISSN 0030-364X (Print), 1526-5463 (Online)
(doi:10.1287/opre.50.5.862.373)

## 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.

Item Type: | Article |
---|---|

Additional Information: | [1] CMS Ref. No: 02/35. |

Uncontrolled Keywords: | networks/graphs, heuristics, meta-heuristic for TSP, mathematics, combinatorics, multilevel refinement for combinatorial problems, simulation, applications, optimization by multilevel refinement |

Subjects: | Q Science > QA Mathematics Q Science > QA Mathematics > QA76 Computer software |

Pre-2014 Departments: | School of Computing & Mathematical Sciences School of Computing & Mathematical Sciences > Computer & Computational Science Research Group School of Computing & Mathematical Sciences > Department of Computer Science School of Computing & Mathematical Sciences > Department of Mathematical Sciences |

Related URLs: | |

Last Modified: | 14 Oct 2016 09:01 |

URI: | http://gala.gre.ac.uk/id/eprint/583 |

### Actions (login required)

View Item |