Variable Neighborhood Search and Ant Colony Optimization for the Rooted Delay-Constrained Minimum Spanning Tree Problem

摘要

The rooted delay-constrained minimum spanning tree problem is an NP-hard combinatorial optimization problem arising for example in the design of centralized broadcasting networks where quality of service constraints are of concern. We present two new approaches to solve this problem heuristically following the concepts of ant colony optimization (ACO) and variable neighborhood search (VNS). The ACO uses a fast construction heuristic based on node delays and local improvement exploiting two different neighborhood structures. The VNS employs the same neighborhood structures but additionally applies various kinds of shaking moves. Experimental results indicate that both metaheuristics outperform existing approaches whereas the ACO produces mostly the best solutions.