Heuristic methods for solving two Generalized Network Problems

Abstract

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 />

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.