Network measures and evaluation of traveling salesman instance hardness

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F61989100%3A27240%2F18%3A10241722" target="_blank" >RIV/61989100:27240/18:10241722 - isvavai.cz</a>

Výsledek na webu

<a href="https://ieeexplore.ieee.org/document/8285352" target="_blank" >https://ieeexplore.ieee.org/document/8285352</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1109/SSCI.2017.8285352" target="_blank" >10.1109/SSCI.2017.8285352</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Network measures and evaluation of traveling salesman instance hardness

Popis výsledku v původním jazyce

Assessing the hardness of combinatorial optimization problem instances is not a trivial task. Although it is easy to compute the size of the search space, associated with particular problem instance, its actual shape is usually unknown. Traveling salesman problem (TSP) is an NP-hard combinatorial optimization problem that has been solved by a number of exact and approximate algorithms. It also often serves as a testbed for new heuristic and metaheuristic optimization methods. The hardness of a TSP instance cannot be determined easily. Simple measures such as the number of cities do not capture its internal structure sufficiently. In this work, we propose a new network-based method for the assessment of TSP instance hardness. The new approach is evaluated on a set of randomized TSP instances with different structure and its relation to the performance of a selected metaheuristic TSP solver is studied.

Název v anglickém jazyce

Network measures and evaluation of traveling salesman instance hardness

Popis výsledku anglicky

Assessing the hardness of combinatorial optimization problem instances is not a trivial task. Although it is easy to compute the size of the search space, associated with particular problem instance, its actual shape is usually unknown. Traveling salesman problem (TSP) is an NP-hard combinatorial optimization problem that has been solved by a number of exact and approximate algorithms. It also often serves as a testbed for new heuristic and metaheuristic optimization methods. The hardness of a TSP instance cannot be determined easily. Simple measures such as the number of cities do not capture its internal structure sufficiently. In this work, we propose a new network-based method for the assessment of TSP instance hardness. The new approach is evaluated on a set of randomized TSP instances with different structure and its relation to the performance of a selected metaheuristic TSP solver is studied.

Druh

D - Stať ve sborníku

CEP obor

—

OECD FORD obor

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Projekt

<a href="/cs/project/GJ16-25694Y" target="_blank" >GJ16-25694Y: Mnohoparadigmatické algoritmy dolování z dat založené na vyhledávání, fuzzy technologiích a bio-inspirovaných výpočtech</a><br>

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Rok uplatnění

2018

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název statě ve sborníku

IEEE SSCI 2017 : proceedings : November 27 – December 1, 2017, Honolulu, USA

ISBN

978-1-5386-2726-6

ISSN

—

e-ISSN

neuvedeno

Počet stran výsledku

7

Strana od-do

1-7

Název nakladatele

IEEE

Místo vydání

Piscataway

Místo konání akce

Honolulu

Datum konání akce

27. 11. 2017

Typ akce podle státní příslušnosti

WRD - Celosvětová akce

Kód UT WoS článku

—