Using POPMUSIC for Candidate Set Generation in the Lin-Kernighan-Helsgaun TSP Solver

Research output: Book/ReportReportResearch


This report describes an enhancement of the Lin-Kernighan-Helsgaun TSP solver (LKH) for fast generation of candidate sets for very-large scale traveling salesman problems. Its implementation is based on a metaheuristic called POPMUSIC. The enhancement makes it possible to generate high-quality candidate sets in almost linear time, even for non-geometric instances.
Original languageEnglish
Place of PublicationRoskilde
PublisherRoskilde Universitet
Number of pages13
Publication statusPublished - 18 Jul 2018


  • Traveling salesman problem
  • Lin-Kernighan
  • Candidate set generation
  • TSP

Cite this