An Effective Implementation of K-opt Moves for the Lin-Kernighan TSP Heuristic

Research output: Book/ReportReportResearch

Abstract

Local search with k-change neighborhoods, k-opt, is the most widely
used heuristic method for the traveling salesman problem (TSP). This
report presents an effective implementation of k-opt for the Lin-
Kernighan TSP heuristic. The effectiveness of the implementation is
demonstrated with extensive experiments on instances ranging from
10,000 to 10,000,000 cities.
Original languageEnglish
Place of PublicationRoskilde
PublisherRoskilde Universitet
Volume109
Number of pages99
Publication statusPublished - 2006
SeriesRoskilde Universitet. Computer Science. Computer Science Research Report
ISSN0109-9779

Cite this

Helsgaun, K. (2006). An Effective Implementation of K-opt Moves for the Lin-Kernighan TSP Heuristic. Roskilde: Roskilde Universitet. Roskilde Universitet. Computer Science. Computer Science Research Report
Helsgaun, Keld. / An Effective Implementation of K-opt Moves for the Lin-Kernighan TSP Heuristic. Roskilde : Roskilde Universitet, 2006. 99 p. (Roskilde Universitet. Computer Science. Computer Science Research Report).
@book{3ace4eb09ff311db9f01000ea68e967b,
title = "An Effective Implementation of K-opt Moves for the Lin-Kernighan TSP Heuristic",
abstract = "Local search with k-change neighborhoods, k-opt, is the most widelyused heuristic method for the traveling salesman problem (TSP). Thisreport presents an effective implementation of k-opt for the Lin-Kernighan TSP heuristic. The effectiveness of the implementation isdemonstrated with extensive experiments on instances ranging from10,000 to 10,000,000 cities.",
author = "Keld Helsgaun",
year = "2006",
language = "English",
volume = "109",
publisher = "Roskilde Universitet",

}

Helsgaun, K 2006, An Effective Implementation of K-opt Moves for the Lin-Kernighan TSP Heuristic. Roskilde Universitet. Computer Science. Computer Science Research Report, vol. 109, Roskilde Universitet, Roskilde.

An Effective Implementation of K-opt Moves for the Lin-Kernighan TSP Heuristic. / Helsgaun, Keld.

Roskilde : Roskilde Universitet, 2006. 99 p.

Research output: Book/ReportReportResearch

TY - RPRT

T1 - An Effective Implementation of K-opt Moves for the Lin-Kernighan TSP Heuristic

AU - Helsgaun, Keld

PY - 2006

Y1 - 2006

N2 - Local search with k-change neighborhoods, k-opt, is the most widelyused heuristic method for the traveling salesman problem (TSP). Thisreport presents an effective implementation of k-opt for the Lin-Kernighan TSP heuristic. The effectiveness of the implementation isdemonstrated with extensive experiments on instances ranging from10,000 to 10,000,000 cities.

AB - Local search with k-change neighborhoods, k-opt, is the most widelyused heuristic method for the traveling salesman problem (TSP). Thisreport presents an effective implementation of k-opt for the Lin-Kernighan TSP heuristic. The effectiveness of the implementation isdemonstrated with extensive experiments on instances ranging from10,000 to 10,000,000 cities.

M3 - Report

VL - 109

BT - An Effective Implementation of K-opt Moves for the Lin-Kernighan TSP Heuristic

PB - Roskilde Universitet

CY - Roskilde

ER -

Helsgaun K. An Effective Implementation of K-opt Moves for the Lin-Kernighan TSP Heuristic. Roskilde: Roskilde Universitet, 2006. 99 p. (Roskilde Universitet. Computer Science. Computer Science Research Report).