Bitte benutzen Sie diese Kennung, um auf die Ressource zu verweisen: http://doi.org/10.25358/openscience-2907
Autoren: Gschwind, Timo
Titel: Contributions to exact approaches in combinatorial optimization
Online-Publikationsdatum: 26-Nov-2014
Erscheinungsdatum: 2014
Sprache des Dokuments: Englisch
Zusammenfassung/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-Sachgruppe: 330 Wirtschaft
330 Economics
Veröffentlichende Institution: Johannes Gutenberg-Universität Mainz
Organisationseinheit: FB 03 Rechts- und Wirtschaftswissenschaften
Veröffentlichungsort: Mainz
ROR: https://ror.org/023b0x485
DOI: http://doi.org/10.25358/openscience-2907
URN: urn:nbn:de:hebis:77-38839
Version: Original work
Publikationstyp: Dissertation
Nutzungsrechte: Urheberrechtsschutz
Informationen zu den Nutzungsrechten: https://rightsstatements.org/vocab/InC/1.0/
Umfang: 162 S.
Enthalten in den Sammlungen:JGU-Publikationen

Dateien zu dieser Ressource:
  Datei Beschreibung GrößeFormat
Miniaturbild
3883.pdf1.79 MBAdobe PDFÖffnen/Anzeigen