Authors:	Heßler, Katrin
Title:	Contributions to Exact Algorithms for Packing and Routing Problems
Online publication date:	10-Dec-2020
Year of first publication:	2020
Language:	english
Abstract:	In this thesis, we contribute to the development of exact solution approaches to packing and routing problems. In particular, new branch-and-cut and branch-cut-and-price algorithms for the classical vector packing problem, a two-dimensional vector packing problem with additional real-world constraints, the soft-clustered vehicle-routing problem, and a multi-compartment vehicle-routing problem are presented. We exploit problem-specific knowledge in every case to specialize the implementation. For the branch-cut-and-price algorithms, the focus lies on the efficient solution of the pricing problems with labeling algorithms. Moreover, we apply specific branching rules, strengthen the linear relaxations with cutting planes, and add dual inequalities to stabilize the column-generation process. The branch-and-cut algorithms exploit valid inequalities for the capacitated vehicle-routing problem that can be adapted, problem-specific cutting planes, as well as new heuristic and exact separation procedures. Extensive computational experiments show that we outperform the state-of-the-art literature. Die vorliegende Dissertation behandelt exakte Lösungsverfahren für Pack- und Tourenplanungsprobleme. Insbesondere werden neue Branch-and-Cut- und Branch-Cut-and-Price-Algorithmen für das klassische Vector-Packing-Problem, ein zweidimensionales Vector-Packing-Problem mit zusätzlichen Nebenbedingungen aus der Praxis, das Soft-Clustered-Vehicle-Routing-Problem und ein Multi-Compartment-Vehicle-Routing-Problem entwickelt. Wir nutzen bei allen Lösungsansätzen problemspezifisches Wissen, um die Umsetzung zu spezialisieren. Bei den Branch-Cut-and-Price-Algorithmen liegt der Schwerpunkt auf der effizienten Lösung der Pricing-Probleme mit Labeling-Algorithmen. Darüber hinaus wenden wir spezifische Branching-Regeln an, stärken die linearen Relaxationen mit gültigen Schnittebenen und fügen duale Ungleichungen zum Stabilisieren der Spaltengenerierungsverfahren hinzu. Die Branch-and-Cut-Algorithmen nutzen auf die Probleme angepasste, bekannte Schnittebenen des Capacitated-Vehicle-Routing-Problems, problemspezifische Schnittebenen sowie neue heuristische und exakte Separationsverfahren. Umfangreiche Rechenstudien demonstrieren die Effektivität der Algorithmen.
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-5473
URN:	urn:nbn:de:hebis:77-openscience-fa232f36-aa27-4151-bd66-f9f4368ba54d1
Version:	Original work
Publication type:	Dissertation
License:	In Copyright
Information on rights of use:	https://rightsstatements.org/page/InC/1.0/?language=en
Extent:	xvi, 228 pages
Appears in collections:	JGU-Publikationen