Solving the clustered minimum routing tree problem using Prüfer-coding based hybrid genetic algorithms
Cosmin Sabo, Bogdan Teglaș, Petrică C. Pop, Adrian Petrovan

Abstract. The clustered minimum routing tree problem (CluMRTP) extends the classical minimum routing tree problem by considering a graph with vertices divided into a given number of clusters. The scope of the CluMRTP is to find a minimum-cost routing tree ensuring that each cluster forms a connected subgraph. In this work, we present Prüfer encoding-based hybrid genetic algorithms (HGAs) developed to address the CluMRTP. Our approach involves a macro-level genetic algorithm (GA) framework, employing the Prüfer code to generate trees linking the clusters, which is coupled with local-level algorithms to derive a feasible solution for the CluMRTP corresponding to a tree which spans the clusters. Preliminary computational results are reported on a set of 78 benchmark instances. These results serve to showcase the efficiency of our novel solution approaches. The achieved computational results demonstrate that our innovative hybrid genetic algorithms are strongly competitive compared with the current state-of-the-art algorithms.

Keywords: hybrid genetic algorithms; minimum routing tree problem; clustered minimum routing tree problem; Prüfer encoding

Cosmin Sabo, Bogdan Teglaș, Petrică C. Pop, Adrian Petrovan, "Solving the clustered minimum routing tree problem using Prüfer-coding based hybrid genetic algorithms", Proc. 19th Int. Conf. on Hybrid Artificial Intelligence Systems (HAIS 2024), Springer, 2025, pp. 312–323, 2023. DOI: https://doi.org/10.1007/978-3-031-74183-8_26.

Reference: Proc. 19th Int. Conf. on Hybrid Artificial Intelligence Systems (HAIS 2024), Springer, 2025, pp. 312–323. DOI: 10.1007/978-3-031-74183-8_26

Other publications