کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
475860 | 699388 | 2009 | 14 صفحه PDF | دانلود رایگان |
![عکس صفحه اول مقاله: VNS and second order heuristics for the min-degree constrained minimum spanning tree problem VNS and second order heuristics for the min-degree constrained minimum spanning tree problem](/preview/png/475860.png)
Given an undirected graph with weights associated with its edges, the min-degree constrained minimum spanning tree (mdmd-MST) problem consists in finding a minimum spanning tree of the given graph, imposing minimum degree constraints in all nodes except the leaves. This problem was recently proposed in Almeida et al. [Min-degree constrained minimum spanning tree problem: Complexity, proprieties and formulations. Operations Research Center, University of Lisbon, Working-paper no. 6; 2006], where its theoretical complexity was characterized and showed to be NPNP-hard.The present paper discusses variable neighborhood search (VNS) metaheuristics addressing the mdmd-MST. A so-called enhanced version of a second order (ESO) repetitive technique is also considered, in order to guide the search in both shaking and improvement phases of the VNS method. A Kruskal based greedy heuristic adapted to the mdmd-MST is also presented, being used within the ESO framework. VNS randomized methodologies are also discussed. These are the first heuristics to the mdmd-MST ever proposed in the literature. Computational experiments are conducted on instances adapted from benchmark ones used in the context of the well-known degree constraint minimum spanning tree problem. These experiments have shown that randomized VNS methods enclosing an ESO algorithm can produce very interesting results. In particular, that a simpler VNS randomized methodology might be taken into account when very high dimensional instances are under consideration.
Journal: Computers & Operations Research - Volume 36, Issue 11, November 2009, Pages 2969–2982