---
_id: '48874'
abstract:
- lang: eng
  text: State of the Art inexact solvers of the NP-hard Traveling Salesperson Problem
    TSP are known to mostly yield high-quality solutions in reasonable computation
    times. With the purpose of understanding different levels of instance difficulties,
    instances for the current State of the Art heuristic TSP solvers LKH+restart and
    EAX+restart are presented which are evolved using a sophisticated evolutionary
    algorithm. More specifically, the performance differences of the respective solvers
    are maximized resulting in instances which are easier to solve for one solver
    and much more difficult for the other. Focusing on both optimization directions,
    instance features are identified which characterize both types of instances and
    increase the understanding of solver performance differences.
author:
- first_name: Jakob
  full_name: Bossek, Jakob
  id: '102979'
  last_name: Bossek
  orcid: 0000-0002-4121-4668
- first_name: Heike
  full_name: Trautmann, Heike
  last_name: Trautmann
citation:
  ama: 'Bossek J, Trautmann H. Understanding Characteristics of Evolved Instances
    for State-of-the-Art Inexact TSP Solvers with Maximum Performance Difference.
    In: <i>Proceedings of the XV International Conference of the Italian Association
    for Artificial Intelligence on Advances in Artificial Intelligence - Volume 10037</i>.
    AI*IA 2016. Springer-Verlag; 2016:3–12. doi:<a href="https://doi.org/10.1007/978-3-319-49130-1_1">10.1007/978-3-319-49130-1_1</a>'
  apa: Bossek, J., &#38; Trautmann, H. (2016). Understanding Characteristics of Evolved
    Instances for State-of-the-Art Inexact TSP Solvers with Maximum Performance Difference.
    <i>Proceedings of the XV International Conference of the Italian Association for
    Artificial Intelligence on Advances in Artificial Intelligence - Volume 10037</i>,
    3–12. <a href="https://doi.org/10.1007/978-3-319-49130-1_1">https://doi.org/10.1007/978-3-319-49130-1_1</a>
  bibtex: '@inproceedings{Bossek_Trautmann_2016, place={Berlin, Heidelberg}, series={AI*IA
    2016}, title={Understanding Characteristics of Evolved Instances for State-of-the-Art
    Inexact TSP Solvers with Maximum Performance Difference}, DOI={<a href="https://doi.org/10.1007/978-3-319-49130-1_1">10.1007/978-3-319-49130-1_1</a>},
    booktitle={Proceedings of the XV International Conference of the Italian Association
    for Artificial Intelligence on Advances in Artificial Intelligence - Volume 10037},
    publisher={Springer-Verlag}, author={Bossek, Jakob and Trautmann, Heike}, year={2016},
    pages={3–12}, collection={AI*IA 2016} }'
  chicago: 'Bossek, Jakob, and Heike Trautmann. “Understanding Characteristics of
    Evolved Instances for State-of-the-Art Inexact TSP Solvers with Maximum Performance
    Difference.” In <i>Proceedings of the XV International Conference of the Italian
    Association for Artificial Intelligence on Advances in Artificial Intelligence
    - Volume 10037</i>, 3–12. AI*IA 2016. Berlin, Heidelberg: Springer-Verlag, 2016.
    <a href="https://doi.org/10.1007/978-3-319-49130-1_1">https://doi.org/10.1007/978-3-319-49130-1_1</a>.'
  ieee: 'J. Bossek and H. Trautmann, “Understanding Characteristics of Evolved Instances
    for State-of-the-Art Inexact TSP Solvers with Maximum Performance Difference,”
    in <i>Proceedings of the XV International Conference of the Italian Association
    for Artificial Intelligence on Advances in Artificial Intelligence - Volume 10037</i>,
    2016, pp. 3–12, doi: <a href="https://doi.org/10.1007/978-3-319-49130-1_1">10.1007/978-3-319-49130-1_1</a>.'
  mla: Bossek, Jakob, and Heike Trautmann. “Understanding Characteristics of Evolved
    Instances for State-of-the-Art Inexact TSP Solvers with Maximum Performance Difference.”
    <i>Proceedings of the XV International Conference of the Italian Association for
    Artificial Intelligence on Advances in Artificial Intelligence - Volume 10037</i>,
    Springer-Verlag, 2016, pp. 3–12, doi:<a href="https://doi.org/10.1007/978-3-319-49130-1_1">10.1007/978-3-319-49130-1_1</a>.
  short: 'J. Bossek, H. Trautmann, in: Proceedings of the XV International Conference
    of the Italian Association for Artificial Intelligence on Advances in Artificial
    Intelligence - Volume 10037, Springer-Verlag, Berlin, Heidelberg, 2016, pp. 3–12.'
date_created: 2023-11-14T15:58:57Z
date_updated: 2023-12-13T10:47:11Z
doi: 10.1007/978-3-319-49130-1_1
extern: '1'
keyword:
- Combinatorial optimization
- Instance hardness
- Metaheuristics
- Transportation
- TSP
language:
- iso: eng
page: 3–12
place: Berlin, Heidelberg
publication: Proceedings of the XV International Conference of the Italian Association
  for Artificial Intelligence on Advances in Artificial Intelligence - Volume 10037
publication_identifier:
  isbn:
  - 978-3-319-49129-5
publication_status: published
publisher: Springer-Verlag
series_title: AI*IA 2016
status: public
title: Understanding Characteristics of Evolved Instances for State-of-the-Art Inexact
  TSP Solvers with Maximum Performance Difference
type: conference
user_id: '102979'
year: '2016'
...
---
_id: '46366'
abstract:
- lang: eng
  text: State of the Art inexact solvers of the NP-hard Traveling Salesperson Problem
    (TSP) are known to mostly yield high-quality solutions in reasonable computation
    times. With the purpose of understanding different levels of instance difficulties,
    instances for the current State of the Art heuristic TSP solvers LKH+restart and
    EAX+restart are presented which are evolved using a sophisticated evolutionary
    algorithm. More specifically, the performance differences of the respective solvers
    are maximized resulting in instances which are easier to solve for one solver
    and much more difficult for the other. Focusing on both optimization directions,
    instance features are identified which characterize both types of instances and
    increase the understanding of solver performance differences.
author:
- first_name: Jakob
  full_name: Bossek, Jakob
  id: '102979'
  last_name: Bossek
  orcid: 0000-0002-4121-4668
- first_name: Heike
  full_name: Trautmann, Heike
  id: '100740'
  last_name: Trautmann
  orcid: 0000-0002-9788-8282
citation:
  ama: 'Bossek J, Trautmann H. Understanding Characteristics of Evolved Instances
    for State-of-the-Art Inexact TSP Solvers with Maximum Performance Difference.
    In: Adorni G, Cagnoni S, Gori M, Maratea M, eds. <i>AI*IA 2016 Advances in Artificial
    Intelligence</i>. Vol 10037. Lecture Notes in Computer Science. Springer; 2016:3–12.
    doi:<a href="https://doi.org/10.1007/978-3-319-49130-1_1">10.1007/978-3-319-49130-1_1</a>'
  apa: Bossek, J., &#38; Trautmann, H. (2016). Understanding Characteristics of Evolved
    Instances for State-of-the-Art Inexact TSP Solvers with Maximum Performance Difference.
    In G. Adorni, S. Cagnoni, M. Gori, &#38; M. Maratea (Eds.), <i>AI*IA 2016 Advances
    in Artificial Intelligence</i> (Vol. 10037, pp. 3–12). Springer. <a href="https://doi.org/10.1007/978-3-319-49130-1_1">https://doi.org/10.1007/978-3-319-49130-1_1</a>
  bibtex: '@inproceedings{Bossek_Trautmann_2016, place={Cham}, series={Lecture Notes
    in Computer Science}, title={Understanding Characteristics of Evolved Instances
    for State-of-the-Art Inexact TSP Solvers with Maximum Performance Difference},
    volume={10037}, DOI={<a href="https://doi.org/10.1007/978-3-319-49130-1_1">10.1007/978-3-319-49130-1_1</a>},
    booktitle={AI*IA 2016 Advances in Artificial Intelligence}, publisher={Springer},
    author={Bossek, Jakob and Trautmann, Heike}, editor={Adorni, G and Cagnoni, S
    and Gori, M and Maratea, M}, year={2016}, pages={3–12}, collection={Lecture Notes
    in Computer Science} }'
  chicago: 'Bossek, Jakob, and Heike Trautmann. “Understanding Characteristics of
    Evolved Instances for State-of-the-Art Inexact TSP Solvers with Maximum Performance
    Difference.” In <i>AI*IA 2016 Advances in Artificial Intelligence</i>, edited
    by G Adorni, S Cagnoni, M Gori, and M Maratea, 10037:3–12. Lecture Notes in Computer
    Science. Cham: Springer, 2016. <a href="https://doi.org/10.1007/978-3-319-49130-1_1">https://doi.org/10.1007/978-3-319-49130-1_1</a>.'
  ieee: 'J. Bossek and H. Trautmann, “Understanding Characteristics of Evolved Instances
    for State-of-the-Art Inexact TSP Solvers with Maximum Performance Difference,”
    in <i>AI*IA 2016 Advances in Artificial Intelligence</i>, 2016, vol. 10037, pp.
    3–12, doi: <a href="https://doi.org/10.1007/978-3-319-49130-1_1">10.1007/978-3-319-49130-1_1</a>.'
  mla: Bossek, Jakob, and Heike Trautmann. “Understanding Characteristics of Evolved
    Instances for State-of-the-Art Inexact TSP Solvers with Maximum Performance Difference.”
    <i>AI*IA 2016 Advances in Artificial Intelligence</i>, edited by G Adorni et al.,
    vol. 10037, Springer, 2016, pp. 3–12, doi:<a href="https://doi.org/10.1007/978-3-319-49130-1_1">10.1007/978-3-319-49130-1_1</a>.
  short: 'J. Bossek, H. Trautmann, in: G. Adorni, S. Cagnoni, M. Gori, M. Maratea
    (Eds.), AI*IA 2016 Advances in Artificial Intelligence, Springer, Cham, 2016,
    pp. 3–12.'
date_created: 2023-08-04T15:11:47Z
date_updated: 2024-06-10T11:58:12Z
department:
- _id: '34'
- _id: '819'
doi: 10.1007/978-3-319-49130-1_1
editor:
- first_name: G
  full_name: Adorni, G
  last_name: Adorni
- first_name: S
  full_name: Cagnoni, S
  last_name: Cagnoni
- first_name: M
  full_name: Gori, M
  last_name: Gori
- first_name: M
  full_name: Maratea, M
  last_name: Maratea
intvolume: '     10037'
language:
- iso: eng
page: 3–12
place: Cham
publication: AI*IA 2016 Advances in Artificial Intelligence
publication_identifier:
  isbn:
  - 978-3-319-49129-5
publisher: Springer
series_title: Lecture Notes in Computer Science
status: public
title: Understanding Characteristics of Evolved Instances for State-of-the-Art Inexact
  TSP Solvers with Maximum Performance Difference
type: conference
user_id: '15504'
volume: 10037
year: '2016'
...