A Hybrid Scatter Search Algorithm for QoS Multicast Routing Problem

Quality of service (QoS) multicast routing is non-linear combinatorial optimization problem. It tries to search a multicast routing tree with minimal cost that can meet constraints such as bandwidth, delay, and delay jitter. This paper presents a hybrid scatter search algorithm (ACO&SS) to solve QoS multicast routing problem. The main feature of the hybrid algorithm is to hybridize the solution construction mechanism of the ACO with scatter search (SS). Moreover, the hybrid algorithm considers both solution diversification and solution quality. The method has both the advantages of ant colony optimization, the ability to find the higher performance solutions, and that of scatter search, the ability to explore different parts of the solution space and to find better solutions. Finally, the simulation results show that the ACO&SS algorithm performs well in terms of solution quality.