On Clustered Vehicle-Routing Problems

The thesis at hand tackles two variants of the vehicle-routing problem (VRP) in which customers are partitioned into clusters: The clustered VRP (CluVRP) and the soft-clustered VRP (SoftCluVRP). Both versions arise in practical scenarios where the routing decision must respect already taken clustering decisions. An example is parcel/small-package delivery in courier companies, where a large number of customers is divided into regional zones. For the heuristic solution, we develop two new large multiple neighborhood searches, one for each of the two problem variants. A major novelty is a generalization of the Balas-Simonetti neighborhood for the CluVRP. It is able to decide on the permutation of the clusters in a route and the routing through each cluster simultaneously. Furthermore, for the exact solution of the SoftCluVRP, we design and analyze different branch-and-price algorithms that differ in the way the column-generation subproblem is solved (either by dynamic-programming based labeling algorithms or with a branch-and-cut algorithm). Extensive computational studies prove the usefulness of the proposed solution methods.Die vorliegende Dissertation behandelt zwei Varianten des Vehicle Routing Problems (VRP) bei denen Kunden in Cluster gruppiert sind: Das clustered VRP (CluVRP) sowie das soft-clustered VRP (SoftCluVRP). Beide Versionen treten in der Praxis auf wenn das Routing eine bereits zuvor getroffene Clustereinteilung der Kunden berücksichtigen muss. Ein Beispiel ist die Paketzustellung. Bei dieser ist eine große Menge an Kunden in Postleitzahlengebiete aufgeteilt. Zur heuristischen Lösung beider Problemvarianten wird jeweils eine neue Large Multiple Neighborhood Search präsentiert. Eine Besonderheit ist dabei die Verallgemeinerung der Balas-Simonetti Nachbarschaft für das CluVRP. Diese ermöglicht es, die Positionen der Cluster innerhalb einer Route sowie das Routing innerhalb eines Clusters simultan zu bestimmen. Des Weiteren werden verschiedene Branch-and-Price Algorithmen für die exakte Lösung des SoftCluVRP entwickelt und analysiert. Sie unterscheiden sich durch die Lösungsmethode für das Column-Generation Subproblem. Dieses wird entweder durch einen auf dynamischer Programmierung basierenden Labeling Algorithmus oder mit einem Branch-and-Cut Algorithmus gelöst. Ausführliche Rechenstudien zeigen die Effektivität der vorgestellten Verfahren