.png){kind=icon}
.png){kind=icon}
Return
A two-level solution approach for solving the generalized minimum spanning tree problem
.png){kind=icon}
PRE
AI
DOI：10.1016/j.ejor.2017.08.015.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
In this paper, we are addressing the generalized minimum spanning tree problem, denoted by GMSTP, which is a variant of the classical minimum spanning tree (MST) problem. The main characteristic of this problem is the fact that the vertices of the graph are partitioned into a given number of clusters and we are looking for a minimum-cost tree spanning a subset of vertices which includes exactly one vertex from each cluster. We describe a two-level solution approach for solving the GMSTP obtained by decomposing the problem into two logical and natural smaller subproblems: an upper-level (global) subproblem and a lower-level (local) subproblem and solving them separately. The goal of the first subproblem is to determine (global) trees spanning the clusters using a genetic algorithm with a diploid representation of the individuals, while the goal of the second subproblem is to determine the best tree (w.r.t. cost minimization), for the above mentioned global trees, spanning exactly one vertex from each cluster. The second subproblem is solved optimally using dynamic programming. Extensive computational results are reported and discussed for an often used set of benchmark instances. The obtained results show an improvement in the quality of the achieved solutions, and demonstrate the efficiency of our approach compared to the existing methods from the literature. (C) 2017 Elsevier B.V. All rights reserved.
Keywords:
Combinatorial optimization
Generalized minimum spanning tree problem
Genetic algorithms
Decomposition methods
Dynamic programming
AI Summary
Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.
Journal
IF:
6
Papers:
2.2W
Citations:
6.4W