Please use this identifier to cite or link to this item: http://doi.org/10.25358/openscience-2907
Authors: Gschwind, Timo
Title: Contributions to exact approaches in combinatorial optimization
Online publication date: 26-Nov-2014
Year of first publication: 2014
Language: english
Abstract: 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.
DDC: 330 Wirtschaft
330 Economics
Institution: Johannes Gutenberg-Universität Mainz
Department: FB 03 Rechts- und Wirtschaftswissenschaften
Place: Mainz
ROR: https://ror.org/023b0x485
DOI: http://doi.org/10.25358/openscience-2907
URN: urn:nbn:de:hebis:77-38839
Version: Original work
Publication type: Dissertation
License: In Copyright
Information on rights of use: https://rightsstatements.org/vocab/InC/1.0/
Extent: 162 S.
Appears in collections:JGU-Publikationen

Files in This Item:
  File Description SizeFormat
Thumbnail
3883.pdf1.79 MBAdobe PDFView/Open