Gutenberg Open Science: Contributions to Exact Algorithms for Packing and Routing Problems

Please use this identifier to cite or link to this item: http://doi.org/10.25358/openscience-5473

Full metadata record

DC Field	Value	Language
dc.contributor.author	Heßler, Katrin	-
dc.date.accessioned	2020-12-10T13:27:33Z	-
dc.date.available	2020-12-10T13:27:33Z	-
dc.date.issued	2020	-
dc.identifier.uri	https://openscience.ub.uni-mainz.de/handle/20.500.12030/5477	-
dc.description.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.	en_GB
dc.description.abstract	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.	de_DE
dc.language.iso	eng	de
dc.rights	InCopyright	*
dc.rights.uri	https://rightsstatements.org/page/InC/1.0/?language=en	*
dc.subject.ddc	330 Wirtschaft	de_DE
dc.subject.ddc	330 Economics	en_GB
dc.title	Contributions to Exact Algorithms for Packing and Routing Problems	en_GB
dc.type	Dissertation	de
dc.identifier.urn	urn:nbn:de:hebis:77-openscience-fa232f36-aa27-4151-bd66-f9f4368ba54d1	-
dc.identifier.doi	http://doi.org/10.25358/openscience-5473	-
jgu.type.dinitype	doctoralThesis	en_GB
jgu.type.version	Original work	de
jgu.type.resource	Text	de
jgu.date.accepted	2020-10-01	-
jgu.description.extent	xvi, 228 pages	de
jgu.organisation.department	FB 03 Rechts- und Wirtschaftswissenschaften	de
jgu.organisation.number	2300	-
jgu.organisation.name	Johannes Gutenberg-Universität Mainz	-
jgu.rights.accessrights	openAccess	-
jgu.organisation.place	Mainz	-
jgu.subject.ddccode	330	de
jgu.organisation.ror	https://ror.org/023b0x485
Appears in collections:	JGU-Publikationen

Files in This Item:

	File	Description	Size	Format
	heßler_katrin-contributions_-20201207173711263.pdf		2.03 MB	Adobe PDF	View/Open

Show simple item record