Two phases of metaheuristic techniques for the minimum conflict weighted spanning tree problem

The minimum conflict weighted spanning tree (MCWST) problem is a variant of spanning tree problem with conflicting edge pairs whose primary goal is to find a spanning tree (T) that contains the minimum number of conflicting edge-pairs, and the secondary goal is to minimize the weight of T, iff T is a conflict free spanning tree. Being NP-hard, very few studies have been carried out in the domain of metaheuristic techniques. This paper develops an approach consisting of two phases of metaheuristic techniques (TPMT) in order to tackle the two goals of this problem, where a hybrid artificial bee colony algorithm (hABC) is used as the first phase of TPMT to tackle the first goal of the problem, and as soon as hABC returns a conflict free solution, an iterated local search (ILS) that starts with this conflict free solution is used as the second phase to tackle the second goal. The components of hABC such as neighborhood operator, local search and operator in scout bee phase coordinate effectively in finding a spanning tree with minimum number of conflicts, whereas the components of ILS such as perturbation procedures, local seas and strong perturbation integrated with memory in acceptance criterion coordinate effectively in finding a minimum cost conflict free spanning tree based on the initial conflict free solution returned by hABC. Experimental results on available two types of benchmark instances (type 1 and type 2) show that the proposed TPMT overall is superior to state-of-the-art approaches, not only in terms of solution quality, but also in terms of computational time. Also, TPMT finds some improved results.