TSP Algorithm Selection

The Travelling Salesperson Problem (TSP) is arguably the most prominent NP-hard combinatorial optimisation problem. Given a set of n cities and pairwise distances between those, the objective in the TSP is to find the shortest round-trip or tour through all cities, i.e., a sequence in which every city is visited exactly once, the start and end cities are identical, and the total length of the tour is minimal. The Euclidean TSP has important applications, e.g., in the fabrication of printed circuit boards as well as in transportation and logistics. We aim at constructing an instance-based algorithm selection model in order to improve the current state-of-the-art solver.

People

This work originally used to be joint work between researchers from the University of British Columbia (UBC) in Canada and the University of Muenster in Germany.
Over the years, some of the involved researchers changed their affiliations, and additional researchers joined the project.
A list with the most recent affiliations of all involved people is given below:

• Jakob Bossek, Postdoctoral Researcher (University of Muenster, Germany)
• Jonathan Heins, Graduate Student Assistant (TU Dresden, Germany)
• Holger H. Hoos, Professor (LIACS, Leiden University, The Netherlands)
• Pascal Kerschke, Professor (TU Dresden, Germany)
• Lars Kotthoff, Professor (University of Wyoming, WY, USA)
• Aneta Neumann, Postdoctoral Researcher (University of Adelaide, Australia)
• Frank Neumann, Professor (University of Adelaide, Australia)
• Janina Pohl, Graduate Student Assistant (University of Muenster, Germany)
• Heike Trautmann, Professor (University of Muenster, Germany)
• Moritz Seiler, Research Associate (University of Muenster, Germany)
• Markus Wagner, Senior Lecturer (University of Adelaide, Australia)

Software

Contributed software

The following software packages for the R programming language were implemented alongside the project:

• R package netgen [GitHub, CRAN]
  Methods for generating random or clustered networks in order to benchmark algorithms for combinatorial optimization problems on graphs, e.g. the Travelling-Salesperson-Problem (TSP) or the Vehicle-Routing-Problem (VRP). Furthermore, this package contains methods for morphing networks, importing from and exporting into the TSPlib format, as well as various visualization techniques.
• R package salesperson [GitHub]
  Comprehensive collection of functions for solving and analyzing the symmetric Traveling Salesperson Problem (TSP) by means of instance characteristics, frequently termed instance features.
• R package tspgen [GitHub]
  Sophisticated benchmark problem generator, which produces TSP instances by a sequential random process adopting a variety of problem tailored mutations.

Other software used

TSP Optimization Algorithms

• Concorde [Official website]
• state-of-the-art exact TSP solver

• Applegate, David L. and Bixby, Robert E. and Chvátal, Vasek and Cook, William J. (2007).
  The Traveling Salesman Problem: A Computational Study. Princeton University Press.

• EAX [GitHub]
• Genetic algorithm with a powerful edge assembly crossover (EAX) operator for solving the TSP.

• Nagata, Yuichi and Kobayashi, Shigenobu (2013).
  A Powerful Genetic Algorithm Using Edge Assembly Crossover for the Traveling Salesman Problem.
  INFORMS Journal on Computing, Vol. 25(2):346-363. INFORMS.

• LKH [Official website]
• Helsgaun's variant of the Lin-Kernighan heuristic (LKH).

• Helsgaun, Keld (2009).
  General k-opt Submoves for the Lin-Kernighan TSP Heuristic.
  Mathematical Programming Computation, Vol. 1(2-3):119-163. Springer.

• MAOS [GitHub]
• The multiagent optimization system (MAOS) TSP solver.

• Xie, Xiao-Feng and Liu, Jiming (2009).
  Multiagent Optimization System for Solving the Traveling Salesman Problem (TSP).
  IEEE Transactions on Systems, Man, and Cybernetics, Part B: Cybernetics, Vol. 39(2):489-502. IEEE.

TSP Feature Calculation

• R package tspmeta [GitHub, CRAN]
• Instance feature calculation and evolutionary instance generation for the traveling salesman problem (This is the predecessor of our R package salesperson).

• Mersmann, Olaf and Bischl, Bischl and Trautmann, Heike and Wagner, Markus and Bossek, Jakob and Neumann, Frank (2013).
  A Novel Feature-Based Approach to Characterize Algorithm Performance for the Traveling Salesperson Problem.
  Annals of Mathematics and Artificial Intelligence, Vol. 69(2):151-182. Springer.

• UBC feature calculation [Download]
• C-code for the computation of the UBC feature set.

• Hutter, Frank and Xu, Lin and Hoos, Holger H. and Leyton-Brown, Kevin (2014).
  Algorithm Runtime Prediction: Methods & Evaluation.
  Artificial Intelligence (AIJ), Vol. 206:79-111. Elsevier.

• Pihera & Musliu feature calculation [Download 1, Download 2]
• C#-code for the computation of the feature set introduced by Pihera and Musliu.

• Pihera, Josef and Musliu, Nysret (2014).
  Application of Machine Learning to Algorithm Selection for TSP.
  Proceedings of the IEEE 26th International Conference on Tools with Artificial Intelligence (ICTAI). IEEE Press.

Data

In the following we provide data used in our publications:

• Set of clustered, morphed and RUE instances (The archive contains the instances in TSPlib format and lengths of the corresponding optimal TSP tours computed with the concorde solver).

Publications

Algorithm Selection

• Heins, Jonathan and Bossek, Jakob and Pohl, Janina and Seiler, Moritz and Trautmann, Heike and Kerschke, Pascal (2021).
  On the Potential of Normalized TSP Features for Automated Algorithm Selection.
  Proceedings of the 16th ACM/SIGEVO Workshop on Foundations of Genetic Algorithms (FOGA XVI), pp. 1-15. ACM (Nominated for Best Paper Award).
  [View Publication, BibTeX]

• Kerschke, Pascal and Hoos, Holger H. and Neumann, Frank and Trautmann, Heike (2019).
  Automated Algorithm Selection: Survey and Perspectives.
  Evolutionary Computation (ECJ), Vol. 27(1):3-45. MIT Press.
  [View Publication]

• Kerschke, Pascal and Kotthoff, Lars and Bossek, Jakob and Hoos, Holger H. and Trautmann, Heike (2018).
  Leveraging TSP Solver Complementarity through Machine Learning.
  Evolutionary Computation (ECJ), Vol. 26(4):597-620. MIT Press.
  [View Publication]

• Kotthoff, Lars and Kerschke, Pascal and Hoos, Holger H. and Trautmann, Heike (2015).
  Improving the State of the Art in Inexact TSP Solving using Per-Instance Algorithm Selection.
  Dhaenens, Clarisse and Jourdan, Laetitia and Marmion, Marie-Eléonore (Eds.),
  Proceedings of the 9th International Conference Learning and Intelligent Optimization (LION), pp. 202-217. Springer.
  [View Publication, BibTeX]

• Seiler, Moritz and Pohl, Janina and Bossek, Jakob and Kerschke, Pascal and Trautmann, Heike (2020).
  Deep Learning as a Competitive Feature-Free Approach for Automated Algorithm Selection on the Traveling Salesperson Problem.
  Bäck, Thomas and Preuss, Mike and Deutz, André and Wang, Hao and Doerr, Carola and Emmerich, Michael and Trautmann, Heike (Eds.),
  Proceedings of the 16th International Conference on Parallel Problem Solving from Nature (PPSN XVI), pp. 48-64. Springer.
  [View Publication, BibTeX]

Generation of TSP Instances

• Bossek, Jakob and Kerschke, Pascal and Neumann, Aneta and Wagner, Markus and Neumann, Frank and Trautmann, Heike (2019).
  Evolving Diverse TSP Instances by Means of Novel and Creative Mutation Operators.
  Proceedings of the 15th ACM/SIGEVO Conference on Foundations of Genetic Algorithms (FOGA XV), pp. 58-71. ACM.
  [View Publication, BibTeX]

Performance Assessment

• Bossek, Jakob and Kerschke, Pascal and Trautmann, Heike (2019).
  A Multi-Objective Perspective on Performance Assessment and Automated Selection of Single-objective Optimization Algorithms.
  Applied Soft Computing. Elsevier (in press).
  [View Publication]

• Kerschke, Pascal and Bossek, Jakob and Trautmann, Heike (2018).
  Parameterization of State-of-the-Art Performance Indicators: A Robustness Study Based on Inexact TSP Solvers.
  Proceedings of the Genetic and Evolutionary Computation Conference (GECCO) Companion, pp. 1737-1744. ACM.
  [View Publication, BibTeX]