Diese Arbeit setzt sich mit zwei kombinatorischen Optimierungsproblemen auseinander: das Problem 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.<br />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.<br />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 verbunden sind. Von jedem Cluster wird genau ein Knoten zum Rückgrat verbunden und durch die Gradbeschränkung wird die Transferqualität gewährleistet.<br />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.<br />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).<br />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 signifikant verkleinern, lokale Verbesserungen erzielt. Beide Problemstellungen wurden auf euklidischen Instanzen mit bis zu 442 Knoten getestet.<br />
de
dc.description.abstract
This thesis examines two combinatorial optimization problems:<br />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 fulfill 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.<br />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.<br />For solving the d-GMSTP two approaches are proposed: Variable Neighborhood Search (VNS) which uses different types of neighborhoods, which work in complementary ways to maximize the collaboration efficiency and a Memetic Algorithm (MA) involving local improvement.<br />For solving the GMVBCNP a Memetic Algorithm (MA) is proposed. Two different population management approaches are considered, as well as local improvement involving graph reduction technique that reduces the search space significantly.<br />Both problems are tested on Euclidean instances with up to 442 nodes.
en
dc.language
English
-
dc.language.iso
en
-
dc.rights.uri
http://rightsstatements.org/vocab/InC/1.0/
-
dc.subject
knotenzweifachzusammenhängend
de
dc.subject
gradbeschränkung
de
dc.subject
memetisch Algorithm
de
dc.subject
VNS
de
dc.subject
biconnectivity
en
dc.subject
degree constraint
en
dc.subject
memetic algorithm
en
dc.subject
VNS
en
dc.title
Heuristic methods for solving two Generalized Network Problems
en
dc.type
Thesis
en
dc.type
Hochschulschrift
de
dc.rights.license
In Copyright
en
dc.rights.license
Urheberrechtsschutz
de
dc.contributor.affiliation
TU Wien, Österreich
-
dc.rights.holder
Anna Pagacz
-
tuw.version
vor
-
tuw.thesisinformation
Technische Universität Wien
-
tuw.publication.orgunit
E186 - Institut für Computergraphik und Algorithmen