[Zurück]

M. Ruthmair, G. Raidl:
"Variable neighborhood search and ant colony optimization for the rooted delay-constrained minimum spanning tree problem";
Vortrag: International Conference on Parallel Problem Solving From Nature (PPSN), Krakow, Poland; 11.09.2010 - 15.09.2010; in: "Parallel Problem Solving from Nature - PPSN XI", (2010), S. 391 - 400.

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.

http://publik.tuwien.ac.at/files/PubDat_189097.pdf