Please use this identifier to cite or link to this item: http://doi.org/10.25358/openscience-2786
Full metadata record
DC FieldValueLanguage
dc.contributor.authorTilk, Christian
dc.date.accessioned2017-01-18T09:40:09Z
dc.date.available2017-01-18T10:40:09Z
dc.date.issued2017
dc.identifier.urihttps://openscience.ub.uni-mainz.de/handle/20.500.12030/2788-
dc.description.abstractThe 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.en_GB
dc.description.abstractDie 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.de_DE
dc.language.isoeng
dc.rightsInCopyrightde_DE
dc.rights.urihttps://rightsstatements.org/vocab/InC/1.0/
dc.subject.ddc330 Wirtschaftde_DE
dc.subject.ddc330 Economicsen_GB
dc.titleContributions to column-generation approaches in combinatorial optimizationen_GB
dc.typeDissertationde_DE
dc.identifier.urnurn:nbn:de:hebis:77-diss-1000009459
dc.identifier.doihttp://doi.org/10.25358/openscience-2786-
jgu.type.dinitypedoctoralThesis
jgu.type.versionOriginal worken_GB
jgu.type.resourceText
jgu.description.extent184 Seiten
jgu.organisation.departmentFB 03 Rechts- und Wirtschaftswissenschaften-
jgu.organisation.year2016
jgu.organisation.number2300-
jgu.organisation.nameJohannes Gutenberg-Universität Mainz-
jgu.rights.accessrightsopenAccess-
jgu.organisation.placeMainz-
jgu.subject.ddccode330
opus.date.accessioned2017-01-18T09:40:09Z
opus.date.modified2017-01-23T09:01:18Z
opus.date.available2017-01-18T10:40:09
opus.subject.dfgcode00-000
opus.organisation.stringFB 03: Rechts- und Wirtschaftswissenschaften: Abteilung Wirtschaftswissenschaftende_DE
opus.identifier.opusid100000945
opus.institute.number0302
opus.metadataonlyfalse
opus.type.contenttypeDissertationde_DE
opus.type.contenttypeDissertationen_GB
jgu.organisation.rorhttps://ror.org/023b0x485
Appears in collections:JGU-Publikationen

Files in This Item:
  File Description SizeFormat
Thumbnail
100000945.pdf2 MBAdobe PDFView/Open