Abstract
The clustered shortest-path tree (CluSPT) problem is a generalization of the popular shortest path problem, in which, given a graph with the set of vertices divided into a given set of clusters, we look for a shortest-path spanning tree from a predefined source vertex to all the other vertices of the graph, with the property that every cluster should generate a connected subgraph. In this paper, we describe a two-level hybrid algorithm to solve the CluSPT problem, in which a framework with a macro-level genetic algorithm (GA) used to generate trees connecting the clusters using Prüfer code, is combined with a micro-level algorithm based on dynamic programming (DP) that determines the best corresponding feasible solution of the CluSPT problem associated to a given tree spanning the clusters. Finally, some preliminary computational results are stated on a set of 40 standard benchmark non-euclidean instances from the literature to illustrate the performance of our developed two-level hybrid algorithm. The obtained computational results demonstrate that our novel hybrid algorithm is highly competitive against the existing algorithms.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Binh, H.T.T., Thanh, P.D., Thang, T.B.: New approach to solving the clustered shortest-path tree problem based on reducing the search space of evolutionary algorithm. Knowl.-Based Syst. 180, 12–25 (2019)
Huynh Thi Thanh, B., Pham Dinh, T.: Two levels approach based on multifactorial optimization to solve the clustered shortest path tree problem. Evol. Intell. 15(1), 185–213 (2020). https://doi.org/10.1007/s12065-020-00501-w
Cosma, O., Pop, P.C., Zelina, I.: An effective genetic algorithm for solving the clustered shortest-path tree problem. IEEE Access 9, 15570–15591 (2021)
Cosma, O., Pop, P.C., Zelina, I.: A novel genetic algorithm for solving the clustered shortest-path tree problem. Carpathian J. Math. 36(3), 401–414 (2020)
D’Emidio, M., Forlizzi, L., Frigioni, D., Leucci, S., Proietti, G.: On the clustered shortest-path tree problem. In: Proceedings of Italian Conference on Theoretical Computer Science, pp. 263–268 (2016)
D’Emidio, M., Forlizzi, L., Frigioni, D., Leucci, S., Proietti, G.: Hardness, approximability and fixed-parameter tractability of the clustered shortest-path tree problem. J. Comb. Optim. 38, 165–184 (2019). https://doi.org/10.1007/s10878-018-00374-x
Demange, M., Monnot, J., Pop, P.C., Ries, B.: On the complexity of the selective graph coloring problem in some special classes of graphs. Theor. Comput. Sci. 540–541, 82–102 (2014)
Feremans, C., Labbe, M., Laporte, G.: Generalized network design problems. Eur. J. Oper. Res. 148(1), 1–13 (2003)
Fidanova, S., Pop, P.C.: An improved hybrid ant-local search for the partition graph coloring problem. J. Comput. Appl. Math. 293, 55–61 (2016)
Fischetti, M., Salazar-Gonzales, J.J., Toth, P.: A branch-and-cut algorithm for the symmetric generalized traveling salesman problem. Oper. Res. 45(3), 378–394 (1997)
Ghiani, G., Improta, G.: An efficient transformation of the generalized vehicle routing problem. Eur. J. Oper. Res. 122, 11–17 (2000)
Hanh, P.T.H., Thanh, P.D., Binh, H.T.T.: Evolutionary algorithm and multifactorial evolutionary algorithm on clustered shortest-path tree problem. Inf. Sci. 553, 280–304 (2021)
Mestria, M., Ochi, L.S., de Lima Martins, S.: GRASP with path relinking for the symmetric Euclidean clustered traveling salesman problem. Comput. Oper. Res. 40(12), 3218–3229 (2013)
Myung, Y.S., Lee, C.H., Tcha, D.W.: On the generalized minimum spanning tree problem. Networks 26, 231–241 (1995)
Pop, P.C., Matei, O., Sabo, C., Petrovan, A.: A two-level solution approach for solving the generalized minimum spanning tree problem. Eur. J. Oper. Res. 265(2), 478–487 (2018)
Pop, P.C., Fuksz, L., Horvat Marc, A., Sabo, C.: A novel two-level optimization approach for clustered vehicle routing problem. Comput. Ind. Eng. 115, 304–318 (2018)
Pop, P.C.: The generalized minimum spanning tree problem: an overview of formulations, solution procedures and latest advances. Eur. J. Oper. Res. 283(1), 1–15 (2020)
Pop, P.C.: Generalized Network Design Problems. Modeling and Optimization. De Gruyter Series in Discrete Mathematics and Applications, Germany (2012)
Thanh, P.D.: CluSPT instances, Mendeley Data v2. https://doi.org/10.17632/b4gcgybvt6.2
Thanh, P.D., Binh, H.T.T., Dac, D.D., Binh Long N., Hai Phong, L.M.: A Heuristic Based on Randomized Greedy Algorithms for the Clustered Shortest-Path Tree Problem. In Proceedings of IEEE Congress on Evolutionary Computation (CEC), pp. 2915–2922 (2019)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2022 Springer Nature Switzerland AG
About this paper
Cite this paper
Petrovan, A., Pop, P.C., Sabo, C., Zelina, I. (2022). A Two-Level Hybrid Based Genetic Algorithm to Solve the Clustered Shortest-Path Tree Problem Using the Prüfer Code. In: García Bringas, P., et al. Hybrid Artificial Intelligent Systems. HAIS 2022. Lecture Notes in Computer Science(), vol 13469. Springer, Cham. https://doi.org/10.1007/978-3-031-15471-3_28
Download citation
DOI: https://doi.org/10.1007/978-3-031-15471-3_28
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-15470-6
Online ISBN: 978-3-031-15471-3
eBook Packages: Computer ScienceComputer Science (R0)