Skip header navigation

University of Stirling

×

Conference Proceeding

Rigorous Performance Analysis of State-of-the-Art TSP Heuristic Solvers

Citation
McMenemy P, Veerapen N, Adair J & Ochoa G (2019) Rigorous Performance Analysis of State-of-the-Art TSP Heuristic Solvers. In: Liefooghe A & Paquete L (eds.) Evolutionary Computation in Combinatorial Optimization. Lecture Notes in Computer Science, 11452. EVOCOP 2019: European Conference on Evolutionary Computation in Combinatorial Optimization, Leipzig, Germany, 24.04.2019-26.04.2019. Cham, Switzerland: Springer International Publishing, pp. 99-114. https://doi.org/10.1007/978-3-030-16711-0_7

Abstract
Understanding why some problems are better solved by one algorithm rather than another is still an open problem, and the symmetric Travelling Salesperson Problem (TSP) is no exception. We apply three state-of-the-art heuristic solvers to a large set of TSP instances of varying structure and size, identifying which heuristics solve specific instances to optimality faster than others. The first two solvers considered are variants of the multi-trial Helsgaun's Lin-Kernighan Heuristic (a form of iterated local search), with each utilising a different form of Partition Crossover; the third solver is a genetic algorithm (GA) using Edge Assembly Crossover. Our results show that the GA with Edge Assembly Crossover is the best solver, shown to significantly outperform the other algorithms in 73% of the instances analysed. A comprehensive set of features for all instances is also extracted, and decision trees are used to identify main features which could best inform algorithm selection. The most prominent features identified a high proportion of instances where the GA with Edge Assembly Crossover performed significantly better when solving to optimality.

Keywords
TSP; Algorithm selection; EAX; GPX; Performance analysis

Journal
Lecture Notes in Computer Science; Theory and Applications of Models of Computation

StatusPublished
Author(s)McMenemy, Paul; Veerapen, Nadarajen; Adair, Jason; Ochoa, Gabriela
FundersEPSRC Engineering and Physical Sciences Research Council and The Leverhulme Trust
Title of seriesLecture Notes in Computer Science
Number in series11452
Publication date31/12/2019
Publication date online28/03/2019
URLhttp://hdl.handle.net/1893/29359
PublisherSpringer International Publishing
Place of publicationCham, Switzerland
eISSN1611-3349
ISSN of series0302-9743
ISBN978-3-030-16710-3
eISBN978-3-030-16711-0
ConferenceEVOCOP 2019: European Conference on Evolutionary Computation in Combinatorial Optimization
Conference locationLeipzig, Germany
Dates
Scroll back to the top