Efficient Recombination in the Lin-Kernighan-Helsgaun Traveling Salesman Heuristic

Keld Helsgaun, Renato Tinós, Darrell Whitley

Research output: Contribution to conferencePaperResearchpeer-review

Abstract

The Lin-Kernighan-Helsgaun (LKH) algorithm is one of the most successful search algorithms for the Traveling Salesman Problem (TSP). The core of LKH is a variable depth local search heuristic developed by Lin and Kernighan (LK). Several improvements have been incorporated to LKH along the years. The best results reported in the literature were obtained by an iterative local search version known as multi-trial LKH. In multi-trial LKH, solutions generated by soft restarts of the LK heuristic are recombined using Iterative Partial Transcription (IPT). We show that IPT can be classified as a partition crossover. Partition crossovers use the features common to the parents to decompose the evaluation function. Recently, a new generalized partition crossover, known as GPX2, was proposed for the TSP. We investigate the use of GPX2 in multi-trial LKH and compare it to multi-trial LKH using IPT. Results of experiments with 11 large instances of the TSP indicate that LKH with GPX2 outperforms LKH with IPT in most of the instances, but not in all of them.
The Lin-Kernighan-Helsgaun (LKH) algorithm is one of the most successful search algorithms for the Traveling Salesman Problem (TSP). The core of LKH is a variable depth local search heuristic developed by Lin and Kernighan (LK). Several improvements have been incorporated to LKH along the years. The best results reported in the literature were obtained by an iterative local search version known as multi-trial LKH. In multi-trial LKH, solutions generated by soft restarts of the LK heuristic are recombined using Iterative Partial Transcription (IPT). We show that IPT can be classified as a partition crossover. Partition crossovers use the features common to the parents to decompose the evaluation function. Recently, a new generalized partition crossover, known as GPX2, was proposed for the TSP. We investigate the use of GPX2 in multi-trial LKH and compare it to multi-trial LKH using IPT. Results of experiments with 11 large instances of the TSP indicate that LKH with GPX2 outperforms LKH with IPT in most of the instances, but not in all of them.

Conference

ConferenceParallel Problem Solving from Nature
NumberXV
LocationUniversity of Coimbra
CountryPortugal
CityCoimbra
Period08/09/201812/09/2018
Internet address

Keywords

  • Traveling Salesman Problem
  • Recombination operator
  • Heuristic search
  • Evolutionary combinatorial optimization

Cite this

Helsgaun, K., Tinós, R., & Whitley, D. (2018). Efficient Recombination in the Lin-Kernighan-Helsgaun Traveling Salesman Heuristic. 95-107. Paper presented at Parallel Problem Solving from Nature, Coimbra, Portugal.
Helsgaun, Keld ; Tinós, Renato ; Whitley, Darrell. / Efficient Recombination in the Lin-Kernighan-Helsgaun Traveling Salesman Heuristic. Paper presented at Parallel Problem Solving from Nature, Coimbra, Portugal.13 p.
@conference{28b39dae1cf246f58052bab46f0bed0d,
title = "Efficient Recombination in the Lin-Kernighan-Helsgaun Traveling Salesman Heuristic",
abstract = "The Lin-Kernighan-Helsgaun (LKH) algorithm is one of the most successful search algorithms for the Traveling Salesman Problem (TSP). The core of LKH is a variable depth local search heuristic developed by Lin and Kernighan (LK). Several improvements have been incorporated to LKH along the years. The best results reported in the literature were obtained by an iterative local search version known as multi-trial LKH. In multi-trial LKH, solutions generated by soft restarts of the LK heuristic are recombined using Iterative Partial Transcription (IPT). We show that IPT can be classified as a partition crossover. Partition crossovers use the features common to the parents to decompose the evaluation function. Recently, a new generalized partition crossover, known as GPX2, was proposed for the TSP. We investigate the use of GPX2 in multi-trial LKH and compare it to multi-trial LKH using IPT. Results of experiments with 11 large instances of the TSP indicate that LKH with GPX2 outperforms LKH with IPT in most of the instances, but not in all of them.",
keywords = "Traveling Salesman Problem, Recombination operator, Heuristic search, Evolutionary combinatorial optimization",
author = "Keld Helsgaun and Renato Tin{\'o}s and Darrell Whitley",
year = "2018",
month = "8",
language = "English",
pages = "95--107",
note = "Parallel Problem Solving from Nature, PPSN ; Conference date: 08-09-2018 Through 12-09-2018",
url = "http://ppsn2018.dei.uc.pt",

}

Helsgaun, K, Tinós, R & Whitley, D 2018, 'Efficient Recombination in the Lin-Kernighan-Helsgaun Traveling Salesman Heuristic' Paper presented at Parallel Problem Solving from Nature, Coimbra, Portugal, 08/09/2018 - 12/09/2018, pp. 95-107.

Efficient Recombination in the Lin-Kernighan-Helsgaun Traveling Salesman Heuristic. / Helsgaun, Keld; Tinós, Renato; Whitley, Darrell.

2018. 95-107 Paper presented at Parallel Problem Solving from Nature, Coimbra, Portugal.

Research output: Contribution to conferencePaperResearchpeer-review

TY - CONF

T1 - Efficient Recombination in the Lin-Kernighan-Helsgaun Traveling Salesman Heuristic

AU - Helsgaun,Keld

AU - Tinós,Renato

AU - Whitley,Darrell

PY - 2018/8

Y1 - 2018/8

N2 - The Lin-Kernighan-Helsgaun (LKH) algorithm is one of the most successful search algorithms for the Traveling Salesman Problem (TSP). The core of LKH is a variable depth local search heuristic developed by Lin and Kernighan (LK). Several improvements have been incorporated to LKH along the years. The best results reported in the literature were obtained by an iterative local search version known as multi-trial LKH. In multi-trial LKH, solutions generated by soft restarts of the LK heuristic are recombined using Iterative Partial Transcription (IPT). We show that IPT can be classified as a partition crossover. Partition crossovers use the features common to the parents to decompose the evaluation function. Recently, a new generalized partition crossover, known as GPX2, was proposed for the TSP. We investigate the use of GPX2 in multi-trial LKH and compare it to multi-trial LKH using IPT. Results of experiments with 11 large instances of the TSP indicate that LKH with GPX2 outperforms LKH with IPT in most of the instances, but not in all of them.

AB - The Lin-Kernighan-Helsgaun (LKH) algorithm is one of the most successful search algorithms for the Traveling Salesman Problem (TSP). The core of LKH is a variable depth local search heuristic developed by Lin and Kernighan (LK). Several improvements have been incorporated to LKH along the years. The best results reported in the literature were obtained by an iterative local search version known as multi-trial LKH. In multi-trial LKH, solutions generated by soft restarts of the LK heuristic are recombined using Iterative Partial Transcription (IPT). We show that IPT can be classified as a partition crossover. Partition crossovers use the features common to the parents to decompose the evaluation function. Recently, a new generalized partition crossover, known as GPX2, was proposed for the TSP. We investigate the use of GPX2 in multi-trial LKH and compare it to multi-trial LKH using IPT. Results of experiments with 11 large instances of the TSP indicate that LKH with GPX2 outperforms LKH with IPT in most of the instances, but not in all of them.

KW - Traveling Salesman Problem

KW - Recombination operator

KW - Heuristic search

KW - Evolutionary combinatorial optimization

M3 - Paper

SP - 95

EP - 107

ER -

Helsgaun K, Tinós R, Whitley D. Efficient Recombination in the Lin-Kernighan-Helsgaun Traveling Salesman Heuristic. 2018. Paper presented at Parallel Problem Solving from Nature, Coimbra, Portugal.