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

Renato Tinós, Keld Helsgaun, Darrell Whitley

Publikation: Bidrag til bog/antologi/rapportKonferencebidrag i proceedingsForskningpeer review


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.
TitelParallel Problem Solving from Nature – PPSN XV : 15th International Conference, Coimbra, Portugal, September 8–12, 2018, Proceedings, Part I
RedaktørerA. Auger, C.M. Fonseca, N. Lourenco, P. Machado, L. Paquete, D. Whitley
Antal sider13
ISBN (Trykt)978-3-319-99252-5
ISBN (Elektronisk)978-3-319-99253-2
StatusUdgivet - 2018
Begivenhed15th International Conference on Parallel Problem Solving from Nature - University of Coimbra, Coimbra, Portugal
Varighed: 8 sep. 201812 sep. 2018
Konferencens nummer: 15


Konference15th International Conference on Parallel Problem Solving from Nature
LokationUniversity of Coimbra
AndetThe 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.
NavnTheoretical Computer Science and General Issues
NavnLecture Notes in Computer Science


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

Citer dette