A Memetic Algorithm and a Solution Archive for the Rooted Delay-Constrained Minimum Spanning Tree Problem

We present a memetic algorithm for a combinatorial optimization problem called rooted delay-constrained minimum spanning tree problem arising for example in centralized broadcasting networks where quality of service constraints are of concern. The memetic algorithm is based on a specialized solution representation and a simple and effective decoding mechanism. Solutions are locally improved by a variable neighborhood descent in two neighborhood structures. Furthermore, to tackle the problem of repeated examination of already visited solutions we investigate a simple hash-based method to only detect duplicates or, alternatively, a trie-based complete solution archive to additionally derive new unvisited solutions. Experimental results show that our memetic algorithm outperforms existing heuristic approaches for this problem in most cases. Including the hash-based duplicate detection mostly further improves solution quality whereas the solution archive can only rarely obtain better results due to its operational overhead.