A multilevel approach to the travelling salesman problem
成果类型：
Article
署名作者：
Walshaw, C
署名单位：
University of Greenwich
刊物名称：
OPERATIONS RESEARCH
ISSN/ISSBN：
0030-364X
DOI：
10.1287/opre.50.5.862.373
发表日期：
2002
页码：
862-877
关键词：
摘要：
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 multi level variants seem to optimise far better the more clustered instances with which the LK and CLK algorithms have the most difficulties.