Solving the clustered minimum routing tree problem using Prüfer-coding based hybrid genetic algorithms
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
📋 Cite this publication
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
A comparative study of different genetic algorithms approaches to capacitated vehicle routing problem for collection of agricultural products
A comparative study of different genetic algorithms approaches to capacitated vehicle routing...
Using Machine Learning for Identifying the Intrinsic Economic Specializations of Localities
Using Machine Learning for Identifying the Intrinsic Economic Specializations of LocalitiesOliviu...
Embedding GIS in crop field bonitation computation
Embedding GIS in crop field bonitation computationBogdan Văduva, Oliviu Matei, Anca Avram, Laura...
A comparative study of machine learning models for plant disease identification
A comparative study of machine learning models for plant disease identificationMăcelaru Mara,...
Evaluation of Feature Selection Methods in Estimation of Precipitation Based on Deep Learning Artificial Neural Networks
Precipitation is the most important element of the water cycle and an indispensable element of water resources management. This paper aims to model the monthly precipitation in 8 precipitation observation stations. The effects and role of different feature weights pre-processing methods (Weight by deviation, Weight by PCA, Weight by correlation, and Weight by Support Vector Machine) on artificial intelligence modeling were investigated.
A Comparison of different crossover operators in genetic algorithms for clusters shortest-path tree problem
The clustered shortest-path tree (CluSPT) problem is an extension of the classical shortest path problem, given a graph with the nodes partitioned into several mutually exclusive and collectively exhaustive clusters looks for a shortest-path spanning tree from a predefined source node to all the other nodes of the graph, with the property that every cluster should generate a connected subgraph.
A comprehensive survey on the generalized traveling salesman problem
The generalized traveling salesman problem (GTSP) is an extension of the classical traveling salesman
problem (TSP), and it is among the most researched combinatorial optimization problems due to its theoretical properties, complexity aspects, and real-life applications in various areas: location-routing problems, material flow design problem, distribution of medical supplies, urban waste collection management, airport selection and routing the courier airplanes, image retrieval and ranking, digital garment manufacturing, etc.
A hybrid based genetic algorithm for solving the clustered generalized traveling salesman problem
We study the clustered generalized traveling salesman problem (CGTSP), which is an extension of the generalized traveling salesman problem (GTSP), which in turn generalizes the well-known traveling salesman problem (TSP).
0 Comments