[Zurück]

M. Ruthmair, A. Hubmer, G. Raidl:
"Using a Solution Archive to Enhance Metaheuristics for the Rooted Delay-Constrained Minimum Spanning Tree Problem";
Vortrag: International Conference on Computer Aided Systems Theory (Eurocast), Gran Canaria, Spain; 06.02.2011 - 11.02.2011; in: "Extended Abstracts of EUROCAST 2011 - 13th International Conference on Computer Aided Systems Theory", (2011), ISBN: 978-84-693-9560-8; S. 285 - 287.

When designing a communication network with a central server broadcasting
information to all the participants of the network, some applications, such as
video conferences, require a limitation of the maximal delay from the server to
each client. Beside this delay-constraint minimizing the cost of establishing the
network is in most cases an important design criterion. This network design
problem can be modeled as an NP-hard combinatorial optimization problem
called rooted delay-constrained minimum spanning tree (RDCMST) problem. The
objective is to find a minimum cost spanning tree of a given graph with the
additional constraint that the sum of delays along the paths from a specified
root node to any other node must not exceed a given delay-bound.
More formally, we are given an undirected graph G = (V;E) with a set V
of n nodes, a set E of m edges, a cost function c : E ! R+
0 , a delay function
d : E ! R+, a fixed root node s 2 V , and a delay-bound B > 0. An optimal
solution to the RDCMST problem is a spanning tree T = (V;E0); E0 E, with
minimum cost c(T) =
Σ
e2E0 c(e), satisfying the constraints
Σ
e2P(s;v) d(e)
B; 8v 2 V , where P(s; v) denotes the unique path from root s to node v.
Exact approaches to the RDCMST problem have been examined by Gouveia
et al. in [1] based on the concept of constrained shortest paths utilized in column
generation, Lagrangian relaxation methods and a flow-based reformulation of the
problem on layered acyclic graphs. All these methods can only solve small instances
with significantly less than 100 nodes to proven optimality in reasonable
time when considering complete graphs. A constructive heuristic approach based
on Prim´s algorithm to find a minimum spanning tree is described by Salama
et al. in [6]. In [4] we present a more de-centralized approach by applying the
basic concept of Kruskal´s minimum spanning tree algorithm to the RDCMST
problem. Two metaheuristics based on GRASP and variable neighborhood descent
(VND) improve the constructed solution. In [5] we reuse this VND as the
local search component in a general variable neighborhood search (GVNS) and
a MAX 􀀀 MIN ant system (MMAS). The MMAS mostly obtains the best
results in the performed tests.

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