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

Research output: Book/ReportReportResearch

Abstract

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.
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.
LanguageEnglish
Number of pages13
StatePublished - 18 Jul 2018

Keywords

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

Cite this

@book{bc9216b473f144c0a93447a9e0201b1c,
title = "Using POPMUSIC for Candidate Set Generation in the Lin-Kernighan-Helsgaun TSP Solver",
abstract = "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.",
keywords = "Traveling salesman problem, Lin-Kernighan, POPMUSIC, Candidate set generation, TSP",
author = "Keld Helsgaun",
year = "2018",
month = "7",
day = "18",
language = "English",

}

Using POPMUSIC for Candidate Set Generation in the Lin-Kernighan-Helsgaun TSP Solver. / Helsgaun, Keld.

2018. 13 p.

Research output: Book/ReportReportResearch

TY - RPRT

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

AU - Helsgaun,Keld

PY - 2018/7/18

Y1 - 2018/7/18

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

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

KW - Traveling salesman problem

KW - Lin-Kernighan

KW - POPMUSIC

KW - Candidate set generation

KW - TSP

M3 - Report

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

ER -