Walshaw, Chris ORCID: https://orcid.org/0000-0003-0253-7779 (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)

Full text not available from this repository.

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:	Publisher Publisher Organisation
Last Modified:	14 Oct 2016 09:01
URI:	http://gala.gre.ac.uk/id/eprint/583

Actions (login required)

View Item