A reduction heuristic for the all-colors shortest path problem
| Autor: | Raffaele Cerulli, Andrea Raiconi, Francesco Carrabs |
|---|---|
| Jazyk: | angličtina |
| Rok vydání: | 2021 |
| Předmět: |
021103 operations research
Optimization problem Computer science All-Colors Shortest Path Problem Equality Generalized Traveling Salesman Problem E-GTSP Heuristic 0211 other engineering and technologies 020206 networking & telecommunications Heuristic 02 engineering and technology E-GTSP Management Science and Operations Research Travelling salesman problem Graph Computer Science Applications Theoretical Computer Science Vertex (geometry) Combinatorics All-Colors Shortest Path Problem Equality Generalized Traveling Salesman Problem Shortest path problem 0202 electrical engineering electronic engineering information engineering MathematicsofComputing_DISCRETEMATHEMATICS |
| Popis: | The All-Colors Shortest Path (ACSP) is a recently introduced NP-Hard optimization problem, in which a color is assigned to each vertex of an edge weighted graph, and the aim is to find the shortest path spanning all colors. The solution path can be not simple, that is it is possible to visit multiple times the same vertices if it is a convenient choice. The starting vertex can be constrained (ACSP) or not (ACSP-UE). We propose a reduction heuristic based on the transformation of any ACSP-UE instance into an Equality Generalized Traveling Salesman Problem one. Computational results show the algorithm to outperform the best previously known one. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|