Contributions to column-generation approaches in combinatorial optimization

Abstract

The thesis at hand deals with column-generation approaches for four different combinatorial optimization problems: The minimum tour duration problem, the active-passive vehicle routing problem, the vehicle routing and truck driver scheduling problem, and the optimal communication spanning tree problem. While the first three problems belong to the family of vehicle routing problems, the last one is in the family of constrained spanning tree problems. In all approaches, we develop effective column-generation algorithms that fully exploit the individual, problem-specific structures. This task can be roughly divided into two subtasks: Defining appropriate Dantzig-Wolfe decompositions and designing effective algorithms to solve the subproblems. The approaches for the optimal communication spanning tree problem focus on defining and comparing appropriate Dantzig-Wolfe decompositions. For the vehicle routing problems, the focus is on developing effective algorithms for the subproblem and strengthening the linear relaxation with valid inequalities. Moreover, we present a refined bidirectional labeling algorithm for the shortest path problem with resource constraints that often occurs as a subproblem in column-generation approaches for vehicle routing problems. Extensive computational results proving the usefulness of the proposed methods are reported.

Die vorliegende Dissertation behandelt column-generation basierte Lösungsverfahren für vier verschiedene kombinatorische Optimierungsprobleme: das Minimum Tour Duration Problem, das Active-Passive Vehicle Routing Problem, das Vehicle Routing and Truck Driver Scheduling Problem und das Optimal Communication Spanning Tree Problem. Während die ersten drei Probleme zur Klasse der Vehicle Routing Probleme gehören, ist das letztgenannte ein Constrained Spanning Tree Problem. Für alle genannten Probleme werden effektive column-generation basierte Lösungsverfahren entwickelt. Diese Aufgabe kann grob in zwei Teilaufgaben unterteilt werden: Die Definition geeigneter Dantzig-Wolfe Dekompositionen und das Design von effektiven Algorithmen zur Lösung des Subproblems. Während der Fokus für die ersten drei Probleme auf der Entwicklung effektiver Algorithmen zur Lösung des Subproblems und dem Stärken der linearen Relaxation mittels gültiger Ungleichungen liegt, beschäftigt sich die Arbeit über das Optimal Communication Spanning Tree Problem damit, geeignete Dantzig-Wolfe Dekompositionen zu finden und diese zu vergleichen. Weiterhin wird auch ein erweiterter bidirektionaler Labeling-Algorithmus für das Shortest Path Problem with Resource Constraints vorgestellt. Dieses Problem taucht oftmals als Subproblem auf, wenn Vehicle Routing Probleme mit column-generation basierten Ansätzen gelöst werden. Umfangreiche Rechenstudien belegen die Wirksamkeit aller vorgestellten Algorithmen.