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

Renato Tinós, Keld Helsgaun, Darrell Whitley

Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearchpeer-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.
LanguageEnglish
Title of host publicationParallel Problem Solving from Nature – PPSN XV : 15th International Conference, Coimbra, Portugal, September 8–12, 2018, Proceedings, Part I
EditorsA. Auger, C.M. Fonseca, N. Lourenco, P. Machado, L. Paquete, D. Whitley
Number of pages13
Volume1
PublisherSpringer
DateAug 2018
Pages95-107
ISBN (Print)978-3-319-99252-5
ISBN (Electronic)978-3-319-99253-2
DOIs
Publication statusPublished - Aug 2018
Event15th International Conference on Parallel Problem Solving from Nature - University of Coimbra, Coimbra, Portugal
Duration: 8 Sep 201812 Sep 2018
Conference number: 15
http://ppsn2018.dei.uc.pt

Conference

Conference15th International Conference on Parallel Problem Solving from Nature
Number15
LocationUniversity of Coimbra
CountryPortugal
CityCoimbra
Period08/09/201812/09/2018
OtherThe Fifteenth International Conference on Parallel Problem Solving from Nature (PPSN XV) will be held in Coimbra, Portugal on 8-12 September 2018. The conference will take place at the Campus of the University of Coimbra, recognised by UNESCO as world heritage site, due to its relevance in the dissemination of knowledge throughout the fields of arts, sciences, law, architecture, urban planning and landscape. The venue includes a set of buildings and rooms of historical relevance, thus giving the participants the opportunity to visit the different areas of the university and experience the feeling of studying and working in Coimbra.<br/><br/>This biennial meeting brings together researchers and practitioners in the field of Natural Computing. Natural Computing is the study of computational systems which use ideas and get inspiration from natural systems, including biological, ecological, physical, chemical, and social systems. It is a fast-growing interdisciplinary field in which a range of techniques and methods are studied for dealing with large, complex, and dynamic problems with various sources of potential uncertainties.<br/><br/>PPSN XV will showcase a wide range of topics in Natural Computing including, but not restricted to, Evolutionary Computation, Artificial Neural Networks, Artificial Life, Swarm Intelligence, Artificial Immune Systems, Self-Organising Systems, Emergent Behaviour, Molecular Computing, Evolutionary Robotics, Evolvable Hardware, Parallel Implementations and Applications to Real-World Problems. PPSN XV will also feature workshops and tutorials covering advanced and fundamental topics in the field of Natural Computing.<br/><br/>Following the PPSN tradition, all accepted papers will be presented during poster sessions and will be included in the proceedings, to be published in the Series Lecture Notes in Computer Science (LNCS) by Springer. Prospective authors are invited to contribute their high-quality original results in the field of Natural Computing.
Internet address
SeriesTheoretical Computer Science and General Issues
Volume11101
SeriesLecture Notes in Computer Science
Volume11101
ISSN0302-9743

Keywords

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

Cite this

Tinós, R., Helsgaun, K., & Whitley, D. (2018). Efficient Recombination in the Lin-Kernighan-Helsgaun Traveling Salesman Heuristic. In A. Auger, C. M. Fonseca, N. Lourenco, P. Machado, L. Paquete, & D. Whitley (Eds.), Parallel Problem Solving from Nature – PPSN XV: 15th International Conference, Coimbra, Portugal, September 8–12, 2018, Proceedings, Part I (Vol. 1, pp. 95-107). Springer. Theoretical Computer Science and General Issues, Vol.. 11101, Lecture Notes in Computer Science, Vol.. 11101 https://doi.org/10.1007/978-3-319-99253-2_8
Tinós, Renato ; Helsgaun, Keld ; Whitley, Darrell. / Efficient Recombination in the Lin-Kernighan-Helsgaun Traveling Salesman Heuristic. Parallel Problem Solving from Nature – PPSN XV: 15th International Conference, Coimbra, Portugal, September 8–12, 2018, Proceedings, Part I. editor / A. Auger ; C.M. Fonseca ; N. Lourenco ; P. Machado ; L. Paquete ; D. Whitley. Vol. 1 Springer, 2018. pp. 95-107 (Theoretical Computer Science and General Issues, Vol. 11101). (Lecture Notes in Computer Science, Vol. 11101).
@inproceedings{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, Traveling Salesman Problem, Recombination operator, Heuristic search, Evolutionary combinatorial optimization",
author = "Renato Tin{\'o}s and Keld Helsgaun and Darrell Whitley",
year = "2018",
month = "8",
doi = "10.1007/978-3-319-99253-2_8",
language = "English",
isbn = "978-3-319-99252-5",
volume = "1",
pages = "95--107",
editor = "A. Auger and C.M. Fonseca and N. Lourenco and P. Machado and L. Paquete and D. Whitley",
booktitle = "Parallel Problem Solving from Nature – PPSN XV",
publisher = "Springer",

}

Tinós, R, Helsgaun, K & Whitley, D 2018, Efficient Recombination in the Lin-Kernighan-Helsgaun Traveling Salesman Heuristic. in A Auger, CM Fonseca, N Lourenco, P Machado, L Paquete & D Whitley (eds), Parallel Problem Solving from Nature – PPSN XV: 15th International Conference, Coimbra, Portugal, September 8–12, 2018, Proceedings, Part I. vol. 1, Springer, Theoretical Computer Science and General Issues, vol. 11101, Lecture Notes in Computer Science, vol. 11101, pp. 95-107, 15th International Conference on Parallel Problem Solving from Nature, Coimbra, Portugal, 08/09/2018. https://doi.org/10.1007/978-3-319-99253-2_8

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

Parallel Problem Solving from Nature – PPSN XV: 15th International Conference, Coimbra, Portugal, September 8–12, 2018, Proceedings, Part I. ed. / A. Auger; C.M. Fonseca; N. Lourenco; P. Machado; L. Paquete; D. Whitley. Vol. 1 Springer, 2018. p. 95-107.

Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearchpeer-review

TY - GEN

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

AU - Tinós, Renato

AU - Helsgaun, Keld

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

KW - Traveling Salesman Problem

KW - Recombination operator

KW - Heuristic search

KW - Evolutionary combinatorial optimization

UR - https://www.springer.com/us/book/9783319992525

U2 - 10.1007/978-3-319-99253-2_8

DO - 10.1007/978-3-319-99253-2_8

M3 - Article in proceedings

SN - 978-3-319-99252-5

VL - 1

SP - 95

EP - 107

BT - Parallel Problem Solving from Nature – PPSN XV

A2 - Auger, A.

A2 - Fonseca, C.M.

A2 - Lourenco, N.

A2 - Machado, P.

A2 - Paquete, L.

A2 - Whitley, D.

PB - Springer

ER -

Tinós R, Helsgaun K, Whitley D. Efficient Recombination in the Lin-Kernighan-Helsgaun Traveling Salesman Heuristic. In Auger A, Fonseca CM, Lourenco N, Machado P, Paquete L, Whitley D, editors, Parallel Problem Solving from Nature – PPSN XV: 15th International Conference, Coimbra, Portugal, September 8–12, 2018, Proceedings, Part I. Vol. 1. Springer. 2018. p. 95-107. (Theoretical Computer Science and General Issues, Vol. 11101). (Lecture Notes in Computer Science, Vol. 11101). https://doi.org/10.1007/978-3-319-99253-2_8