A k-minimum spanning tree (k-MST) problem is one of combinatorial optimization problems formulated in networks, and the objective of the problem is to find a subtree with exactly k edges such that the sum of the weights attached to edges is minimal, called k-minimum spanning tree. The k-MST problem is a generalized version of minimum spanning tree (MST) problems; when k = ∣V∣ − 1 where ∣V∣ is a cardinality of vertices in a graph, the k-MST problem corresponds to the MST problem. The wide varieties of decision making problems in the real world can be formulated as k-MST problems, e.g. telecommunications (Garg & Hochbaum, 1997), facility layout (Foulds, Hamacher, & Wilson, 1998), open pit mining (Philpott & Wormald, 1997), oil-field leasing (Hamacher, Jörnsten, & Maffioli, 1991), matrix decomposition ( Börndorfer et al., 1997 and Börndorfer et al., 1998) and quorum-cast routing (Cheung & Kumar, 1994).
The k-MST problem was firstly introduced by Hamacher et al. (1991). Since the k-MST problem is NP-hard ( Fischetti et al., 1994 and Marathe et al., 1996), it is difficult to solve large-scale problems within a practically acceptable time. Therefore, it is very important to construct approximate solution methods which quickly find a near optimal solution ( Jörnsten and Løkketangen, 1997 and Katagiri et al., 2010). Blum and Blesa (2005) proposed several approximate solution methods including metaheuristics such as evolutionary computation, ant colony optimization (ACO) and tabu search (TS). They compared their performances through benchmark instances (KCTLIB, 2003) and showed that an ACO approach is the best for relatively small ks, whereas a TS-based approach has an advantage for large ks with respect to solution accuracy. Recently, it is shown that both ACO and TS are promising approaches to solving not only k-MST problems but also other combinatorial optimization problems ( Abdallah et al., 2009, Aladag et al., 2009, Li et al., 2010, Öncan et al., 2008 and Tseng et al., 2008). Moreover, in order to construct more efficient solution method by combining some effective approximate ones, hybrid algorithms ( Chen et al., 2008, Chen and Chien, 2011, Liu and Zeng, 2009 and Naimi and Taherinejad, 2009) have been highly attracted attention to many researchers.
In this paper, we propose a new hybrid approximate solution algorithm based on TS and ACO. In order to demonstrate efficiency of the proposed solution method, we compare the performances of the proposed method with those of existing algorithms using the well-known benchmark instances (KCTLIB, 2003) that are easily accessible through the internet. The numerical experimental results show that the proposed method updates some of the best known solutions and values with very short computational times, and that the proposed method provides a better performance with solution accuracy over existing algorithms.
2. Problem formulation and existing solution methods
Given that a graph G = (V, E) where V is a set of vertices and E is a set of edges, a subtree with exactly k edges, called k-subtree Tk, is defined as
View the MathML sourceTk∈G,k⩽|V|-1.
View the MathML sourceminimize∑e∈E(Tk)w(e)subject toTk∈Tk,
where TkTk is the set of all possible k-subtrees Tk in G, E(Tk) denotes the edges of Tk and w(e) is a weight attached to an edge e. The above problem is to seek a k-subtree with the minimum sum of weights. If the problem size is small, the problem can be easily solved by finding an optimal solution after enumerating all possible k-subtrees in a given graph. If the size of problem is not so large, it can be solved by some exact solution algorithm such as a branch and bound method (Cheung & Kumar, 1994) and a branch and cut algorithm (Freitag, 1993). However, it has been shown that the k-MST problem is NP-hard even if the edge weight is in {1, 2, 3} for all edges, or if a graph is fully connected. The problem is also NP-hard for planar graphs and for points in the plane (Marathe et al., 1996). Therefore, it is important to construct not only exact solution methods but also efficient approximate solution methods
