Contributions to exact approaches in combinatorial optimization

The focus of this thesis is to contribute to the development of new, exact solution approaches to different combinatorial optimization problems. In particular, we derive dedicated algorithms for a special class of Traveling Tournament Problems (TTPs), the Dial-A-Ride Problem (DARP), and the Vehicle Routing Problem with Time Windows and Temporal Synchronized Pickup and Delivery (VRPTWTSPD). Furthermore, we extend the concept of using dual-optimal inequalities for stabilized Column Generation (CG) and detail its application to improved CG algorithms for the cutting stock problem, the bin packing problem, the vertex coloring problem, and the bin packing problem with conflicts. In all approaches, we make use of some knowledge about the structure of the problem at hand to individualize and enhance existing algorithms. Specifically, we utilize knowledge about the input data (TTP), problem-specific constraints (DARP and VRPTWTSPD), and the dual solution space (stabilized CG). Extensive computational results proving the usefulness of the proposed methods are reported.

Der Kern der vorliegenden Arbeit ist es, zur Entwicklung neuer, exakter Lösungsverfahren für verschiedene kombinatorische Optimierungsprobleme beizutragen. Insbesondere werden dabei maßgeschneiderte Algorithmen für eine spezielle Klasse von Traveling Tournament Problems (TTP), dem Dial-A-Ride Problem (DARP) und dem Vehicle Routing Problem with Time Windows and Temporal Synchronized Pickup and Delivery (VRPTWTSPD) ausgearbeitet. Darüber hinaus wird das Prinzip der Verwendung dual-optimaler Ungleichungen zum Stabilisieren von Spaltengenerierungsverfahren erweitert und der Nutzen des Verfahrens anhand verbesserter Spaltengenerierungsverfahren für das Cutting Stock Problem, das Bin Packing Problem, das Vertex Coloring Problem und das Bin Packing Problem with Conflicts aufgezeigt. Alle Lösungsansätze nutzen spezifisches Wissen über die Struktur des jeweiligen Problems um bestehende Algorithmen zu individualisieren und zu verbessern. Insbesondere werden Kenntnisse über die Eingangsdaten (TTP), problemspezifische Nebenbedingungen (DARP und VRPTWTSPD) und den dualen Lösungsraum (stabilisierte Spaltengenerierung) ausgenutzt. Die Leistungsfähigkeit der entwickelten Lösungsansätze wird durch umfangreiche Rechenstudien belegt.