Contributions to Exact Algorithms for Packing and Routing Problems
Date issued
Authors
Editors
Journal Title
Journal ISSN
Volume Title
Publisher
License
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.