HAN Jun, FANG Qingan, MAO Liyong, HUANG Yaling. A Hybrid Optimization Algorithm for the CMST Problem[J]. Chinese Journal of Electronics, 2011, 20(4): 583-589.
Citation:
HAN Jun, FANG Qingan, MAO Liyong, HUANG Yaling. A Hybrid Optimization Algorithm for the CMST Problem[J]. Chinese Journal of Electronics, 2011, 20(4): 583-589.
HAN Jun, FANG Qingan, MAO Liyong, HUANG Yaling. A Hybrid Optimization Algorithm for the CMST Problem[J]. Chinese Journal of Electronics, 2011, 20(4): 583-589.
Citation:
HAN Jun, FANG Qingan, MAO Liyong, HUANG Yaling. A Hybrid Optimization Algorithm for the CMST Problem[J]. Chinese Journal of Electronics, 2011, 20(4): 583-589.
The Capacitated minimum spanning tree (CMST) problem is one of the most fundamental and significant problems in the optimal design of networks. It is also a classical combinatorial optimization problem which has been tackled by researchers for centuries using various methods. In this paper, a new NS-TS hybrid optimization algorithm that combines neighborhood search and tabu search is proposed. A novel neighborhood structure and associate tabu strategy is proposed and implemented. Computational experiments showing the effectiveness and efficiency of the algorithm on benchmark instances are given.