General k-opt submoves for the Lin-Kernighan TSP heuristic

Publikation: Bidrag til tidsskriftTidsskriftartikelForskningpeer review

Resumé

Local search with k-exchange neighborhoods, k-opt, is the most widely used heuristic method for the traveling salesman problem (TSP). This paper presents an effective implementation of k-opt in LKH-2, a variant of the Lin–Kernighan TSP heuristic. The effectiveness of the implementation is demonstrated with experiments on Euclidean instances ranging from 10,000 to 10,000,000 cities. The runtime of the method increases almost linearly with the problem size. LKH-2 is free of charge for academic and non-commercial use and can be downloaded in source code.
OriginalsprogEngelsk
TidsskriftMathematical Programming Computation
Vol/bind1
Udgave nummer2-3
Sider (fra-til)119-163
ISSN1867-2949
DOI
StatusUdgivet - 2009

Citer dette

@article{4b281be06a1911de89b4000ea68e967b,
title = "General k-opt submoves for the Lin-Kernighan TSP heuristic",
abstract = "Local search with k-exchange neighborhoods, k-opt, is the most widely used heuristic method for the traveling salesman problem (TSP). This paper presents an effective implementation of k-opt in LKH-2, a variant of the Lin–Kernighan TSP heuristic. The effectiveness of the implementation is demonstrated with experiments on Euclidean instances ranging from 10,000 to 10,000,000 cities. The runtime of the method increases almost linearly with the problem size. LKH-2 is free of charge for academic and non-commercial use and can be downloaded in source code.",
keywords = "Traveling salesman problem, TSP, Lin-Kernighan, k-opt",
author = "Keld Helsgaun",
year = "2009",
doi = "10.1007/s12532-009-0004-6",
language = "English",
volume = "1",
pages = "119--163",
journal = "Mathematical Programming Computation",
issn = "1867-2949",
publisher = "Physica-Verlag",
number = "2-3",

}

General k-opt submoves for the Lin-Kernighan TSP heuristic. / Helsgaun, Keld.

I: Mathematical Programming Computation, Bind 1, Nr. 2-3, 2009, s. 119-163.

Publikation: Bidrag til tidsskriftTidsskriftartikelForskningpeer review

TY - JOUR

T1 - General k-opt submoves for the Lin-Kernighan TSP heuristic

AU - Helsgaun, Keld

PY - 2009

Y1 - 2009

N2 - Local search with k-exchange neighborhoods, k-opt, is the most widely used heuristic method for the traveling salesman problem (TSP). This paper presents an effective implementation of k-opt in LKH-2, a variant of the Lin–Kernighan TSP heuristic. The effectiveness of the implementation is demonstrated with experiments on Euclidean instances ranging from 10,000 to 10,000,000 cities. The runtime of the method increases almost linearly with the problem size. LKH-2 is free of charge for academic and non-commercial use and can be downloaded in source code.

AB - Local search with k-exchange neighborhoods, k-opt, is the most widely used heuristic method for the traveling salesman problem (TSP). This paper presents an effective implementation of k-opt in LKH-2, a variant of the Lin–Kernighan TSP heuristic. The effectiveness of the implementation is demonstrated with experiments on Euclidean instances ranging from 10,000 to 10,000,000 cities. The runtime of the method increases almost linearly with the problem size. LKH-2 is free of charge for academic and non-commercial use and can be downloaded in source code.

KW - Traveling salesman problem

KW - TSP

KW - Lin-Kernighan

KW - k-opt

U2 - 10.1007/s12532-009-0004-6

DO - 10.1007/s12532-009-0004-6

M3 - Journal article

VL - 1

SP - 119

EP - 163

JO - Mathematical Programming Computation

JF - Mathematical Programming Computation

SN - 1867-2949

IS - 2-3

ER -