Contributions to Exact Algorithms for Packing and Routing Problems

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.