A reduction heuristic for the all-colors shortest path problem
RAIRO. Operations Research, Tome 55 (2021), pp. S2071-S2082

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.

DOI : 10.1051/ro/2020078
Classification : 90C59, 90C27, 05C38
Keywords: All-Colors Shortest Path problem, Equality Generalized Traveling Salesman Problem, E-GTSP, heuristic 
@article{RO_2021__55_S1_S2071_0,
     author = {Carrabs, Francesco and Cerulli, Raffaele and Raiconi, Andrea},
     title = {A reduction heuristic for the all-colors shortest path problem},
     journal = {RAIRO. Operations Research},
     pages = {S2071--S2082},
     year = {2021},
     publisher = {EDP-Sciences},
     volume = {55},
     doi = {10.1051/ro/2020078},
     mrnumber = {4223186},
     zbl = {1472.90108},
     language = {en},
     url = {https://www.numdam.org/articles/10.1051/ro/2020078/}
}
TY  - JOUR
AU  - Carrabs, Francesco
AU  - Cerulli, Raffaele
AU  - Raiconi, Andrea
TI  - A reduction heuristic for the all-colors shortest path problem
JO  - RAIRO. Operations Research
PY  - 2021
SP  - S2071
EP  - S2082
VL  - 55
PB  - EDP-Sciences
UR  - https://www.numdam.org/articles/10.1051/ro/2020078/
DO  - 10.1051/ro/2020078
LA  - en
ID  - RO_2021__55_S1_S2071_0
ER  - 
%0 Journal Article
%A Carrabs, Francesco
%A Cerulli, Raffaele
%A Raiconi, Andrea
%T A reduction heuristic for the all-colors shortest path problem
%J RAIRO. Operations Research
%D 2021
%P S2071-S2082
%V 55
%I EDP-Sciences
%U https://www.numdam.org/articles/10.1051/ro/2020078/
%R 10.1051/ro/2020078
%G en
%F RO_2021__55_S1_S2071_0
Carrabs, Francesco; Cerulli, Raffaele; Raiconi, Andrea. A reduction heuristic for the all-colors shortest path problem. RAIRO. Operations Research, Tome 55 (2021), pp. S2071-S2082. doi: 10.1051/ro/2020078

[1] H. Akcan and C. Evrendilek, Complexity of energy efficient localization with the aid of a mobile beacon. IEEE Commun. Lett. 22 (2018) 392–395. | DOI

[2] M. B. Akçay, H. Akcan and C. Evrendilek, All colors shortest path problem on trees. J. Heurist. 24 (2018) 617–644. | DOI

[3] A. Benkouar, Y. Manoussakis, V. Th. Paschos and R. Saad, On the complexity of finding alternating Hamiltonian and Eulerian cycles in edge-coloured graphs. Lect. Notes Comput. Sci. 557 (1991) 190–198. | DOI

[4] A. Benkouar, Y. Manoussakis, V. Th. Paschos and R. Saad, Hamiltonian problems in edge-colored complete graphs and Eulerian cycles in edge-colored graphs: Some complexity results. RAIRO: OR 30 (1996) 417–438. | MR | Zbl | Numdam | DOI

[5] Y. Can Bilge, D. Çağatay, B. Genç, M. Sarı, H. Akcan and C. Evrendilek, All colors shortest path problem. arXiv:1507.06865.

[6] F. Carrabs, R. Cerulli, G. Felici and G. Singh, Exact approaches for the orderly colored longest path problem: Performance comparison. Comput. Oper. Res. 101 (2019) 275–284. | MR | Zbl | DOI

[7] F. Carrabs, R. Cerulli, R. Pentangelo and A. Raiconi, A two-level metaheuristic for the All-Colors Shortest Path problem. Comput. Opt. Appl. 71 (2018) 525–551. | MR | Zbl | DOI

[8] V. Dimitrijević and Z. Šarić, An efficient transformation of the generalized traveling salesman problem into the traveling salesman problem on digraphs. Inform. Sci. 102 (1997) 105–110. | MR | Zbl | DOI

[9] M. Fischetti, J. J. Salazar González and P. Toth, The symmetric generalized traveling salesman polytope. Networks 26 (1995) 113–123. | MR | Zbl | DOI

[10] M. Fischetti, J. J. Salazar González and P. Toth, A branch-and-cut algorithm for the symmetric generalized traveling salesman problem. Oper. Res. 45 (1997) 378–394. | MR | Zbl | DOI

[11] K. Helsgaun, An effective implementation of the Lin–Kernighan traveling salesman heuristic. Eur. J. Oper. Res. 126 (2000) 106–130. | MR | Zbl | DOI

[12] K. Helsgaun, General k -opt submoves for the Lin–Kernighan TSP heuristic. Math. Program. Comput. 1 (2009) 119–163. | MR | Zbl | DOI

[13] K. Helsgaun, Solving the equality generalized traveling salesman problem using the Lin–Kernighan–Helsgaun algorithm. Math. Program. Comput. 7 (2015) 269–287. | MR | Zbl | DOI

[14] I. Kara, H. Guden and O. N. Koc, New formulations for the generalized traveling salesman problem. In Proceedings of the 6th International Conference on Applied Mathematics, Simulation, Modelling (ASM ’12) (2012) 60–65.

[15] G. Laporte and Y. Nobert, Generalized traveling salesman through n sets of nodes: An integer programming approach. Infor. 21 (1983) 61–75. | Zbl

[16] S. Lin and B. W. Kernighan, An effective heuristic algorithm for the traveling-salesman problem. Oper. Res. 21 (1973) 498–516. | MR | Zbl | DOI

[17] X. H. Shi, Y. C. Liang, H. P. Lee, C. Lu and Q. X. Wang, Particle swarm optimization-based algorithms for TSP and generalized TSP. Inf. Process. Lett. 103 (2007) 69–176. | MR | Zbl

[18] J. Silberholz and B. Golden, The generalized traveling salesman problem: A new genetic algorithm approach. In: Vol. 37 of Extending the Horizons: Advances in Computing, Optimization, and Decision Technologies. Operations Research/Computer Science Interfaces Series, edited by E. K. Baker, A. Joseph, A. Mehrotra, and M. A. Trick. Springer, Boston, MA (2007) 165–181. | Zbl

[19] L. V. Snyder and M. S. Daskin, A random-key genetic algorithm for the generalized traveling salesman problem. Eur. J. Oper. Res. 174 (2006) 38–53. | MR | Zbl | DOI

Cité par Sources :