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

Publikation: Bog/antologi/afhandling/rapportRapportForskning

Resumé

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.
OriginalsprogEngelsk
Udgivelses stedRoskilde
ForlagRoskilde Universitet
Vol/bind109
Antal sider99
StatusUdgivet - 2006
NavnRoskilde Universitet. Computer Science. Computer Science Research Report
ISSN0109-9779

Citer dette

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 s. (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, bind 109, Roskilde Universitet, Roskilde.

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

Roskilde : Roskilde Universitet, 2006. 99 s.

Publikation: Bog/antologi/afhandling/rapportRapportForskning

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 s. (Roskilde Universitet. Computer Science. Computer Science Research Report).