On arc-routing problems

Das Basisproblem von Arc-Routing Problemen mit mehreren Fahrzeugen ist das Capacitated Arc-Routing Problem (CARP). Praktische Anwendungen des CARP sind z.B. in den Bereichen Müllabfuhr und Briefzustellung zu finden. Das Ziel ist es, einen kostenminimalen Tourenplan zu berechnen, bei dem alle erforderlichen Kanten bedient werden und gleichzeitig die Fahrzeugkapazität eingehalten wird. In der vorliegenden Arbeit wird ein Cut-First Branch-and-Price Second Verfahren entwickelt. In der ersten Phase werden Schnittebenen generiert, die dem Master Problem in der zweiten Phase hinzugefügt werden. Das Subproblem ist ein kürzeste Wege Problem mit Ressourcen und wird gelöst um neue Spalten für das Master Problem zu liefern. Ganzzahlige CARP Lösungen werden durch ein neues hierarchisches Branching-Schema garantiert. Umfassende Rechenstudien zeigen die Effektivität dieses Algorithmus. Kombinierte Standort- und Arc-Routing Probleme ermöglichen eine realistischere Modellierung von Zustellvarianten bei der Briefzustellung. In dieser Arbeit werden jeweils zwei mathematische Modelle für Park and Loop und Park and Loop with Curbline vorgestellt. Die Modelle für das jeweilige Problem unterscheiden sich darin, wie zulässige Transfer Routen modelliert werden. Während der erste Modelltyp Subtour-Eliminationsbedingungen verwendet, werden bei dem zweiten Modelltyp Flussvariablen und Flusserhaltungsbedingungen eingesetzt. Die Rechenstudie zeigt, dass ein MIP-Solver den zweiten Modelltyp oft in kürzerer Rechenzeit lösen kann oder bei Erreichen des Zeitlimits bessere Zielfunktionswerte liefert.

The basic multiple-vehicle arc-routing problem is called Capacitated Arc-Routing Problem (CARP). Applications of the CARP are in waste collection and mail delivery, for example. The goal is to find a cost-minimal set of tours that service all required edges and meet the capacity restriction. In this work, a cut-first branch-and-price second approach is developed. In phase one, cutting planes are generated that are introduced to the master problem in the second phase. The subproblem is a shortest path problem with resource constraints. It is solved in order to generate new columns for the master problem. Integer CARP solutions are guaranteed by a new hierarchical branching scheme. Comprehensive computational results show the effectiveness of the algorithm. Combining location problems with arc-routing problems enables one to model more realistic mail delivery applications. In this work, two mathematical formulations for each park and loop, and park and loop with curbline are introduced. The two models for each problem differ in how they model feasible transfer routes. While the first type of model uses subtour-elimination constraints, the second type uses flow variables and flow conservation constraints. The computational study shows that a MIP-Solver often needs less computation time to solve the latter type of model or results in better lower bounds when reaching the time limit.