Cut-first branch-and-price-second for the capacitated arc-routing problem

This paper presents the first full-fledged branch-and-price (bap) algorithm for the capacitated arc-routing problem (CARP). Prior exact solution techniques either rely on cutting planes or the transformation of the CARP into a node-routing problem. The drawbacks are either models with inherent symmetry, dense underlying networks, or a formulation where edge flows in a potential solution do not allow the reconstruction of unique CARP tours. The proposed algorithm circumvents all these drawbacks by taking the beneficial ingredients from existing CARP methods and combining them in a new way. The first step is the solution of the one-index formulation of the CARP in order to produce strong cuts and an excellent lower bound. It is known that this bound is typically stronger than relaxations of a pure set-partitioning CARP model.rnSuch a set-partitioning master program results from a Dantzig-Wolfe decomposition. In the second phase, the master program is initialized with the strong cuts, CARP tours are iteratively generated by a pricing procedure, and branching is required to produce integer solutions. This is a cut-first bap-second algorithm and its main function is, in fact, the splitting of edge flows into unique CARP tours.

Geochronological and structural evolution of the western and central Kaoko Belt in NW Namibia

This thesis focusses on the tectonic evolution and geochronology of part of the Kaoko orogen, which is part of a network of Pan-African orogenic belts in NW Namibia. By combining geochemical, isotopic and structural analysis, the aim was to gain more information about how and when the Kaoko Belt formed. The first chapter gives a general overview of the studied area and the second one describes the basis of the Electron Probe Microanalysis dating method. The reworking of Palaeo- to Mesoproterozoic basement during the Pan-African orogeny as part of the assembly of West Gondwana is discussed in Chapter 3. In the study area, high-grade rocks occupy a large area, and the belt is marked by several large-scale structural discontinuities. The two major discontinuities, the Sesfontein Thrust (ST) and the Puros Shear Zone (PSZ), subdivide the orogen into three tectonic units: the Eastern Kaoko Zone (EKZ), the Central Kaoko Zone (CKZ) and the Western Kaoko Zone (WKZ). An important lineament, the Village Mylonite Zone (VMZ), has been identified in the WKZ. Since plutonic rocks play an important role in understanding the evolution of a mountain belt, zircons from granitoid gneisses were dated by conventional U-Pb, SHRIMP and Pb-Pb techniques to identify different age provinces. Four different age provinces were recognized within the Central and Western part of the belt, which occur in different structural positions. The VMZ seems to mark the limit between Pan-African granitic rocks east of the lineament and Palaeo- to Mesoproterozoic basement to the west. In Chapter 4 the tectonic processes are discussed that led to the Neoproterozoic architecture of the orogen. The data suggest that the Kaoko Belt experienced three main phases of deformation, D1-D3, during the Pan-African orogeny. Early structures in the central part of the study area indicate that the initial stage of collision was governed by underthrusting of the medium-grade Central Kaoko zone below the high-grade Western Kaoko zone, resulting in the development of an inverted metamorphic gradient. The early structures were overprinted by a second phase D2, which was associated with the development of the PSZ and extensive partial melting and intrusion of ~550 Ma granitic bodies in the high-grade WKZ. Transcurrent deformation continued during cooling of the entire belt, giving rise to the localized low-temperature VMZ that separates a segment of elevated Mesoproterozoic basement from the rest of the Western zone in which only Pan-African ages have so far been observed. The data suggest that the boundary between the Western and Central Kaoko zones represents a modified thrust zone, controlling the tectonic evolution of the Kaoko belt. The geodynamic evolution and the processes that generated this belt system are discussed in Chapter 5. Nd mean crustal residence ages of granitoid rocks permit subdivision of the belt into four provinces. Province I is characterised by mean crustal residence ages <1.7 Ga and is restricted to the Neoproterozoic granitoids. A wide range of initial Sr isotopic values (87Sr/86Sri = 0.7075 to 0.7225) suggests heterogeneous sources for these granitoids. The second province consists of Mesoproterozoic (1516-1448 Ma) and late Palaeo-proterozoic (1776-1701 Ma) rocks and is probably related to the Eburnian cycle with Nd model ages of 1.8-2.2 Ga. The eNd i values of these granitoids are around zero and suggest a predominantly juvenile source. Late Archaean and middle Palaeoproterozoic rocks with model ages of 2.5 to 2.8 Ga make up Province III in the central part of the belt and are distinct from two early Proterozoic samples taken near the PSZ which show even older TDM ages of ~3.3 Ga (Province IV). There is no clear geological evidence for the involvement of oceanic lithosphere in the formation of the Kaoko-Dom Feliciano orogen. Chapter 6 presents the results of isotopic analyses of garnet porphyroblasts from high-grade meta-igneous and metasedimentary rocks of the sillimanite-K-feldspar zone. Minimum P-T conditions for peak metamorphism were calculated at 731±10 °C at 6.7±1.2 kbar, substantially lower than those previously reported. A Sm-Nd garnet-whole rock errorchron obtained on a single meta-igneous rock yielded an unexpectedly old age of 692±13 Ma, which is interpreted as an inherited metamorphic age reflecting an early Pan-African granulite-facies event. The dated garnets survived a younger high-grade metamorphism that occurred between ca. 570 and 520 Ma and apparently maintained their old Sm-Nd isotopic systematics, implying that the closure temperature for garnet in this sample was higher than 730 °C. The metamorphic peak of the younger event was dated by electronmicroprobe on monazite at 567±5 Ma. From a regional viewpoint, it is possible that these granulites of igneous origin may be unrelated to the early Pan-African metamorphic evolution of the Kaoko Belt and may represent a previously unrecognised exotic terrane.

Der Wandel der bildungspolitischen Ansichten der Weltbank /// Arbeitspapiere / Institut für Ethnologie und Afrikastudien; 82

Der Wandel der bildungspolitischen Ansichten der Weltbank. In dieser Arbeit wird dargestellt, welchen Stellenwert das Thema Bildung in der Politik der Weltbank von 1962 bis heute besessen hat und welche Prioritätensetzung es in der Förderung von Bildungsprojekten zu welchem Zeitpunkt gab. Nach diesen Kriterien werden fünf Phasen in der Bildungspolitik der Weltbank unterschieden. In der ersten Phase (1962 bis Ende der 1970er Jahre) ist ein geringes Interesse der Weltbank am Bildungssektor und ein fehlendes Gesamtkonzept ihrer Bildungspolitik erkennbar. Gefördert wurden in dieser Zeit hauptsächlich Sekundar- und Hochschulbildung. Die zweite Phase (Ende der 1970er Jahre bis 1987) zeichnet sich durch die Förderung von Primarschulbildung und durch einen geringen Bedeutungsgewinn des Themas Bildung als einen entwicklungspolitischen Faktor aus. In der dritten Phase (1987 bis Mitte der 1990er Jahre) wurde der Schwerpunkt der Förderung der Weltbank im Bereich Primarschulförderung um die Bereiche Sekundar- und Hochschulförderung ergänzt. Da Bildung nur als ein Aspekt des Ziels der Armutsbekämpfung betrachtet wurde, mangelte es in der vierten Phase (Mitte bis Ende der 1990er Jahre) an einem eigenständigen Konzept für die Förderung des Bildungssektors. In dieser Zeit war nur eine leichte Schwerpunktsetzung in den Primarschulbereich erkennbar. In der fünften Phase (ab dem Jahre 2000) setzt die Weltbank in der Förderung wieder auf eine Kombination von Primar-, Sekundar- und Hochschulbildung. Bildung wird nun als ein eigenständiges Ziel der Entwicklungszusammenarbeit angesehen. Bei der Betrachtung des Wandels der bildungspolitischen Ansichten der Weltbank wird die additive Politik der Weltbank deutlich. Alte Strategien werden nicht komplett verworfen, sondern lediglich neue Aspekte und Schwerpunktsetzungen in die alten Konzepte eingeflochten. Außerdem sind eine Widersprüchlichkeit in der Bildungspolitik, das Fehlen eines langfristigen Konzeptes, große Unterschiede zwischen den theoretischen Konzepten und der Umsetzung der Bildungspolitik der Weltbank zu erkennen. Festzuhalten ist, dass das Thema Bildung von 1962 bis heute in der Politik der Weltbank stark an Bedeutung hinzugewonnen hat.

Efficient parallel proximity queries and an application to highly complex motion planning problems with many narrow passages

In vielen Bereichen der industriellen Fertigung, wie zum Beispiel in der Automobilindustrie, wer- den digitale Versuchsmodelle (sog. digital mock-ups) eingesetzt, um die Entwicklung komplexer Maschinen m ̈oglichst gut durch Computersysteme unterstu ̈tzen zu k ̈onnen. Hierbei spielen Be- wegungsplanungsalgorithmen eine wichtige Rolle, um zu gew ̈ahrleisten, dass diese digitalen Pro- totypen auch kollisionsfrei zusammengesetzt werden k ̈onnen. In den letzten Jahrzehnten haben sich hier sampling-basierte Verfahren besonders bew ̈ahrt. Diese erzeugen eine große Anzahl von zuf ̈alligen Lagen fu ̈r das ein-/auszubauende Objekt und verwenden einen Kollisionserken- nungsmechanismus, um die einzelnen Lagen auf Gu ̈ltigkeit zu u ̈berpru ̈fen. Daher spielt die Kollisionserkennung eine wesentliche Rolle beim Design effizienter Bewegungsplanungsalgorith- men. Eine Schwierigkeit fu ̈r diese Klasse von Planern stellen sogenannte “narrow passages” dar, schmale Passagen also, die immer dort auftreten, wo die Bewegungsfreiheit der zu planenden Objekte stark eingeschr ̈ankt ist. An solchen Stellen kann es schwierig sein, eine ausreichende Anzahl von kollisionsfreien Samples zu finden. Es ist dann m ̈oglicherweise n ̈otig, ausgeklu ̈geltere Techniken einzusetzen, um eine gute Performance der Algorithmen zu erreichen.rnDie vorliegende Arbeit gliedert sich in zwei Teile: Im ersten Teil untersuchen wir parallele Kollisionserkennungsalgorithmen. Da wir auf eine Anwendung bei sampling-basierten Bewe- gungsplanern abzielen, w ̈ahlen wir hier eine Problemstellung, bei der wir stets die selben zwei Objekte, aber in einer großen Anzahl von unterschiedlichen Lagen auf Kollision testen. Wir im- plementieren und vergleichen verschiedene Verfahren, die auf Hu ̈llk ̈operhierarchien (BVHs) und hierarchische Grids als Beschleunigungsstrukturen zuru ̈ckgreifen. Alle beschriebenen Verfahren wurden auf mehreren CPU-Kernen parallelisiert. Daru ̈ber hinaus vergleichen wir verschiedene CUDA Kernels zur Durchfu ̈hrung BVH-basierter Kollisionstests auf der GPU. Neben einer un- terschiedlichen Verteilung der Arbeit auf die parallelen GPU Threads untersuchen wir hier die Auswirkung verschiedener Speicherzugriffsmuster auf die Performance der resultierenden Algo- rithmen. Weiter stellen wir eine Reihe von approximativen Kollisionstests vor, die auf den beschriebenen Verfahren basieren. Wenn eine geringere Genauigkeit der Tests tolerierbar ist, kann so eine weitere Verbesserung der Performance erzielt werden.rnIm zweiten Teil der Arbeit beschreiben wir einen von uns entworfenen parallelen, sampling- basierten Bewegungsplaner zur Behandlung hochkomplexer Probleme mit mehreren “narrow passages”. Das Verfahren arbeitet in zwei Phasen. Die grundlegende Idee ist hierbei, in der er- sten Planungsphase konzeptionell kleinere Fehler zuzulassen, um die Planungseffizienz zu erh ̈ohen und den resultierenden Pfad dann in einer zweiten Phase zu reparieren. Der hierzu in Phase I eingesetzte Planer basiert auf sogenannten Expansive Space Trees. Zus ̈atzlich haben wir den Planer mit einer Freidru ̈ckoperation ausgestattet, die es erlaubt, kleinere Kollisionen aufzul ̈osen und so die Effizienz in Bereichen mit eingeschr ̈ankter Bewegungsfreiheit zu erh ̈ohen. Optional erlaubt unsere Implementierung den Einsatz von approximativen Kollisionstests. Dies setzt die Genauigkeit der ersten Planungsphase weiter herab, fu ̈hrt aber auch zu einer weiteren Perfor- mancesteigerung. Die aus Phase I resultierenden Bewegungspfade sind dann unter Umst ̈anden nicht komplett kollisionsfrei. Um diese Pfade zu reparieren, haben wir einen neuartigen Pla- nungsalgorithmus entworfen, der lokal beschr ̈ankt auf eine kleine Umgebung um den bestehenden Pfad einen neuen, kollisionsfreien Bewegungspfad plant.rnWir haben den beschriebenen Algorithmus mit einer Klasse von neuen, schwierigen Metall- Puzzlen getestet, die zum Teil mehrere “narrow passages” aufweisen. Unseres Wissens nach ist eine Sammlung vergleichbar komplexer Benchmarks nicht ̈offentlich zug ̈anglich und wir fan- den auch keine Beschreibung von vergleichbar komplexen Benchmarks in der Motion-Planning Literatur.

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.