---
_id: '48884'
abstract:
- lang: eng
  text: The Travelling Salesperson Problem (TSP) is one of the best-studied NP-hard
    problems. Over the years, many different solution approaches and solvers have
    been developed. For the first time, we directly compare five state-of-the-art
    inexact solvers\textemdash namely, LKH, EAX, restart variants of those, and MAOS\textemdash
    on a large set of well-known benchmark instances and demonstrate complementary
    performance, in that different instances may be solved most effectively by different
    algorithms. We leverage this complementarity to build an algorithm selector, which
    selects the best TSP solver on a per-instance basis and thus achieves significantly
    improved performance compared to the single best solver, representing an advance
    in the state of the art in solving the Euclidean TSP. Our in-depth analysis of
    the selectors provides insight into what drives this performance improvement.
author:
- first_name: Pascal
  full_name: Kerschke, Pascal
  last_name: Kerschke
- first_name: Lars
  full_name: Kotthoff, Lars
  last_name: Kotthoff
- first_name: Jakob
  full_name: Bossek, Jakob
  id: '102979'
  last_name: Bossek
  orcid: 0000-0002-4121-4668
- first_name: Holger H.
  full_name: Hoos, Holger H.
  last_name: Hoos
- first_name: Heike
  full_name: Trautmann, Heike
  last_name: Trautmann
citation:
  ama: Kerschke P, Kotthoff L, Bossek J, Hoos HH, Trautmann H. Leveraging TSP Solver
    Complementarity through Machine Learning. <i>Evolutionary Computation</i>. 2018;26(4):597–620.
    doi:<a href="https://doi.org/10.1162/evco_a_00215">10.1162/evco_a_00215</a>
  apa: Kerschke, P., Kotthoff, L., Bossek, J., Hoos, H. H., &#38; Trautmann, H. (2018).
    Leveraging TSP Solver Complementarity through Machine Learning. <i>Evolutionary
    Computation</i>, <i>26</i>(4), 597–620. <a href="https://doi.org/10.1162/evco_a_00215">https://doi.org/10.1162/evco_a_00215</a>
  bibtex: '@article{Kerschke_Kotthoff_Bossek_Hoos_Trautmann_2018, title={Leveraging
    TSP Solver Complementarity through Machine Learning}, volume={26}, DOI={<a href="https://doi.org/10.1162/evco_a_00215">10.1162/evco_a_00215</a>},
    number={4}, journal={Evolutionary Computation}, author={Kerschke, Pascal and Kotthoff,
    Lars and Bossek, Jakob and Hoos, Holger H. and Trautmann, Heike}, year={2018},
    pages={597–620} }'
  chicago: 'Kerschke, Pascal, Lars Kotthoff, Jakob Bossek, Holger H. Hoos, and Heike
    Trautmann. “Leveraging TSP Solver Complementarity through Machine Learning.” <i>Evolutionary
    Computation</i> 26, no. 4 (2018): 597–620. <a href="https://doi.org/10.1162/evco_a_00215">https://doi.org/10.1162/evco_a_00215</a>.'
  ieee: 'P. Kerschke, L. Kotthoff, J. Bossek, H. H. Hoos, and H. Trautmann, “Leveraging
    TSP Solver Complementarity through Machine Learning,” <i>Evolutionary Computation</i>,
    vol. 26, no. 4, pp. 597–620, 2018, doi: <a href="https://doi.org/10.1162/evco_a_00215">10.1162/evco_a_00215</a>.'
  mla: Kerschke, Pascal, et al. “Leveraging TSP Solver Complementarity through Machine
    Learning.” <i>Evolutionary Computation</i>, vol. 26, no. 4, 2018, pp. 597–620,
    doi:<a href="https://doi.org/10.1162/evco_a_00215">10.1162/evco_a_00215</a>.
  short: P. Kerschke, L. Kotthoff, J. Bossek, H.H. Hoos, H. Trautmann, Evolutionary
    Computation 26 (2018) 597–620.
date_created: 2023-11-14T15:58:58Z
date_updated: 2023-12-13T10:51:26Z
department:
- _id: '819'
doi: 10.1162/evco_a_00215
intvolume: '        26'
issue: '4'
keyword:
- automated algorithm selection
- machine learning.
- performance modeling
- Travelling Salesperson Problem
language:
- iso: eng
page: 597–620
publication: Evolutionary Computation
publication_identifier:
  issn:
  - 1063-6560
status: public
title: Leveraging TSP Solver Complementarity through Machine Learning
type: journal_article
user_id: '102979'
volume: 26
year: '2018'
...