[Zurück]

A. Pagacz:
"Heuristic methods for solving two generalized network problems";
Betreuer/in(nen): G. Raidl, B. Hu; Institut für Computergraphik und Algorithmen, 2010; Abschlussprüfung: 02/2010.

Diese Arbeit setzt sich mit zwei kombinatorischen Optimierungsproblemen auseinander: das Prob-
lem des generalisierten minimalen knotenzweifachzusammenhängenden Netzwerks (GMVBCNP) und das Problem des generalisierten minimalen Spannbaums mit Gradbeschränkung (d-GMSTP).
Beide Optimierungsprobleme sind NP-vollständig. Gegeben sind Graphen, deren Knoten in Cluster unterteilt sind. Das Ziel besteht jeweils darin, einen Teilgraphen mit minimalen Kosten zu
finden, der genau einen Knoten von jedem Cluster verbindet und andere Zusatzbedingungen berücksichtigt. Beim d-GMSTP ist die Zusatzbedingung die Gradbeschränkung der Knoten. In
der Praxis findet sich diese Problemstellung in der Telekommunikation wieder, wo Netzwerkknoten in mehrere Cluster unterteilt sind und auf Basis einer Baumarchitektur miteinander ver-
bunden sind. Von jedem Cluster wird genau ein Knoten zum Rückgrat verbunden und durch die Gradbeschränkung wird die Transferqualität gewährleistet. Das GMVBCNP hingegen wird bei
fehlertoleranten Backbone-Netzen angewendet. Um sicherzustellen, dass durch den Ausfall einer
einzelnen Komponente andere Dienste nicht beeinflusst werden, müssen die Verbindungen redundant sein. Diese Arbeit stellt zwei Lösungsansätze für das d-GMSTP vor. Ein Ansatz basiert
auf variable Nachbarschaftssuche (VNS), bei der verschiedene Arten von Nachbarschaftsstrukturen komplementär arbeiten und dadurch die Effizienz bei der Zusammenarbeit maximiert wird.
Ein anderer Ansatz basiert auf einen memetischen Algorithmus (MA). Das GMVBCNP wird in dieser Arbeit ebenfalls mit einem memetischen Algorithmus (MA) gelöst. Dabei werden für die
Zusammensetzung der Knoten zwei verschiedene Ansätze betrachtet. Ausserdem werden mit Hilfe von Graph-Reduzierungstechniken, die den Suchraum signifi kant verkleinern, lokale Verbesserungen erzielt. Beide Problemstellungen wurden auf euklidischen Instanzen mit bis zu 442 Knoten getestet.

This thesis examines two combinatorial optimization problems: the Generalized Degree Constrained Minimum Spanning Tree Problem (d-GMSTP) and the Generalized Minimum Vertex
Bi-connected Network Problem (GMVBCNP). Both problems are NP- hard. Given a clustered graph where nodes are partitioned into clusters, the goal is to find a minimal cost subgraph containing exactly one node from each cluster and satisfying other constraints. For the d-GMSTP the subgraph has to ful ll degree constraint. It plays an important role in telecommunication areas
where network nodes are divided into clusters and they need to be connected via tree architecture using exactly one node per cluster and satisfying degree constraint for transfer quality. The
GMVBCNP can be applied to the design of survivable backbone networks that should be fault tolerant to the single component outage. In order to ensure that the failure of a single service vertex would not lead to disconnection of other services, redundant connections need to be created.
For solving the d-GMSTP two approaches are proposed: Variable Neighborhood Search (VNS)
which uses di fferent types of neighborhoods, which work in complementary ways to maximize the
collaboration efficiency and a Memetic Algorithm (MA) involving local improvement. For solving
the GMVBCNP a Memetic Algorithm (MA) is proposed. Two di fferent population management
approaches are considered, as well as local improvement involving graph reduction technique that
reduces the search space signi cantly. Both problems are tested on Euclidean instances with up
to 442 nodes.

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