Contributions to branch-and-price-and-cut algorithms for routing problems

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.

Die vorliegende Dissertation behandelt neue, exakte Branch-and-Price-and-Cut-Algorithmen zur Lösung von Routing-Problemen. Spezialisierte Methoden für das Pickup-and-Delivery-Problem (PDP), das Truck-and-Trailer-Routing-Problem (TTRP), das periodische Vehicle-Routing-Problem (PVRP) und ein Service-Netzwerk-Design-und-Hub-Location-Problem (SNDHLP) werden präsentiert. Neben der Anwendung spezifischer Branching-Regeln und der Einbeziehung gültiger Schnittebenen, liegt der Fokus auf der effizienten Lösung der Pricing-Probleme mit Labeling-Algorithmen. Wir entwickeln eine neue Technik für die Beschleunigung bidirektionaler Labeling-Algorithmen durch eine dynamische Wahl des Merge-Punktes. Darüber hinaus kann bidirektionales Labeling erstmalig mit einer starken Dominanz in beiden Richtungen für Varianten des PDP angewandt werden. Im TTRP modellieren wir die Erweiterung zu einem zweitägigen Planungshorizont und die Betrachtung mengenabhängiger Umladezeiten. Das PVRP wird erstmals mit vollständig flexiblen Schedule-Strukturen betrachtet. Für die beiden letztgenannten Probleme werden spezielle Techniken zur Behandlung der inhärenten Symmetrie präsentiert. Das SNDHLP stellt ein neues Problem der realen Welt im Anwendungsbereich des kombinierten Verkehrs dar und wird erneut durch einen problemspezifischen Branch-and-Price-and-Cut-Algorithmus gelöst. Die Effektivität aller Algorithmen wird durch umfangreiche Rechenstudien demonstriert.