Network measures and evaluation of traveling salesman instance hardness
The result's identifiers
Result code in 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>
Result on the web
<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>
Alternative languages
Result language
angličtina
Original language name
Network measures and evaluation of traveling salesman instance hardness
Original language description
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.
Czech name
—
Czech description
—
Classification
Type
D - Article in proceedings
CEP classification
—
OECD FORD branch
10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
Result continuities
Project
<a href="/en/project/GJ16-25694Y" target="_blank" >GJ16-25694Y: Multi-paradigm data mining algorithms based on information retrieval, fuzzy, and bio-inspired methods</a><br>
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)
Others
Publication year
2018
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Article name in the collection
IEEE SSCI 2017 : proceedings : November 27 – December 1, 2017, Honolulu, USA
ISBN
978-1-5386-2726-6
ISSN
—
e-ISSN
neuvedeno
Number of pages
7
Pages from-to
1-7
Publisher name
IEEE
Place of publication
Piscataway
Event location
Honolulu
Event date
Nov 27, 2017
Type of event by nationality
WRD - Celosvětová akce
UT code for WoS article
—