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...
详细信息
ISBN:
(纸本)9783031741821;9783031741838
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 routingtree ensuring that each cluster forms a connected subgraph. In this work, we present Prufer encoding-based hybrid genetic algorithms (HGAs) developed to address the CluMRTP. Our approach involves a macro-level genetic algorithm (GA) framework, employing the Prufer 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.
暂无评论