Abstract | ||
---|---|---|
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 networkbased 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. |
Year | Venue | Keywords |
---|---|---|
2017 | 2017 IEEE SYMPOSIUM SERIES ON COMPUTATIONAL INTELLIGENCE (SSCI) | component, formatting, style, styling, insert |
Field | DocType | Citations |
Heuristic,Mathematical optimization,Combinatorial optimization problem,Computer science,Metaheuristic optimization,Testbed,Travelling salesman problem,Disk formatting,Solver,Metaheuristic | Conference | 0 |
PageRank | References | Authors |
0.34 | 0 | 3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Krömer Pavel | 1 | 330 | 59.99 |
Jan Platos | 2 | 286 | 58.72 |
Milos Kudelka | 3 | 116 | 23.81 |