Contributions to branch-and-price-and-cut algorithms for routing problems
Date issued
Authors
Editors
Journal Title
Journal ISSN
Volume Title
Publisher
License
Abstract
The thesis at hand deals with new exact branch-and-price-and-cut algorithms for the solution of routing problems. Specialized methods for the pickup-and-delivery problem (PDP), the truck-and-trailer routing problem (TTRP), the periodic vehicle routing problem (PVRP), and a service network design and hub location problem (SNDHLP) are presented. Beside the application of specific branching rules and the incorporation of valid inequalities, the focus lies on the efficient solution of the pricing problems with labeling algorithms. We develop a new technique for the acceleration of bidirectional labeling algorithms by a dynamic choice of the merge point. Moreover, for variants of the PDP, the bidirectional labeling can be applied with strong dominance in both directions for the first time. In the TTRP, we model the extension to a two-day planning horizon and the consideration of quantity-dependent transfer times. The PVRP is treated with full flexible schedule structures for the first time. For these two lastmentioned problems, special techniques to tackle the inherent symmetry are presented. The SNDHLP constitutes a new real-world problem in the application area of combined transport and is also solved with a problem-specific branch-and-price-and-cut algorithm. The effectiveness of all algorithms is demonstrated with extensive computational studies.