Multilevel Heuristiken für das Rooted Delay-Constrained Minimum Spanning Tree Problem

Abstract

Viele kombinatorische Optimierungsprobleme sind NP-schwer und können deshalb höchstwahrscheinlich nicht effizient exakt gelöst werden.<br />Aus diesem Grund bedient man sich oft Heuristiken um gute Näherungslösungen für derartige Probleme zu finden. In dieser Arbeit wird das Rooted Delay-Constrained Minimum Spanning Tree Problem (RDCMSTP) behandelt. Es handelt sich hierbei um ein NP-schweres Problem, wobei für einen gegebenen Graphen, dessen Kanten über Kosten und einen Delaywert verfügen, ein kostenminimaler Spannbaum gesucht wird. Jedoch besteht die Einschränkung, dass der Pfad zwischen einem beliebigen Knoten und einer definierten Wurzel nicht länger als eine gegebene Delaygrenze sein darf. Eine praktische Anwendung für dieses Problem ist eine Form von Vertrieb mit einer Lieferzeitgarantie, beispielsweise ein Paketversand mit 24 Stunden Liefergarantie. Im Zuge dieser Arbeit werden drei Multilevel-Heuristiken für das RDCMSTP vorgestellt. Eine Multilevel-Heuristik besteht grundsätzlich aus zwei Teilen, dem Coarsening und dem Refinement. Während des Coarsenings werden Knoten und/oder Kanten systematisch zusammengefasst um so den Graph zu vereinfachen. Der Graph wird in mehreren Iterationen vereinfacht und es entstehen verschiedene Ebenen des Graphen, sogenannte Levels. Im zweiten Schritt, dem Refinement, wird, mit Hilfe der Informationen aus dem Coarsening, sukzessiv der gesuchte Spannbaum erstellt. Während des Refinements kann der Graph, mit Hilfe von lokalem Improvement, unter Verwendung geeigneter Nachbarschaftsstrukturen untersucht werden, um so eine Verbesserung der Gesamtlösung zu erzielen.

Many combinatorial optimization problems are NP-hard and can not be solved exactly in an efficient way commonly. Therefore heuristics are often applied to generate good approximations for such problems. This thesis discusses the Rooted Delay-Constrained Minimum Spanning Tree Problem (RDCMSTP) which is NP-hard. The task is to find a minimum spanning tree for a given graph where the edges have cost and delay values minimizing the sum of costs. However, an additional constraint is applied that no path from a specied root node to any other node may exceed a given delay bound. An application for the given problem is a form of distribution with a guarantee of timely delivery, for example a shipment service with a guarantee for delivery within 24 hours. In this document three multilevel heuristics for the RDCMSTP are introduced. A multilevel heuristic basically consists of two steps, the coarsening and the refinement step. During the coarsening step vertices and/or edges are systematically merged in order to create a reduced graph. The graph is reduced in multiple iterations thus creating multiple levels of detail.<br />In the second step, the refinement, a solution tree is constructed using the information acquired during the coarsening. While constructing the solution the graph can be searched for local improvements using appropriate neighborhoods thus increasing the quality of the solution.