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.

Liquid crystalline cellulose derivatives for mirrorless lasing

In this thesis cholesteric films made of liquid crystalline cellulose derivatives with improved optical properties were prepared. The choice of the solvent, hydrogen bond influencing additives, the synthetic realization of a very high degree of substitution on the cellulosic polymer and the use of mechanical stirring at the upper concentration limit of the liquid crystalline range were the basis for an improved alignment of the applied cellulose tricarbamates. In combination with a tuned substrate treatment and film preparation method, cholesteric films were obtained, with optical properties that were theoretically predicted and only known from low molecular weight liquid crystals so far. Subsequent polymerization allowed a permanent fixing of the alignment and the fabrication of free standing and insensitive films.rnThe incorporation of inorganic nanorods into the cholesteric host material was mediated with tailored block copolymers, available via controlled radical polymerization methods. In addition to the shape match between the rodlike mesogens of the host and the nanorods it was possible to increase the miscibility of both materials. Nevertheless, the size of the nanorods, in comparison to the mesogens, in these densely packed liquid crystalline phases as well as their long equilibration times were the reasons for phase separation. Nanorods are, in principle, valuable substitutes for organics, but their utilization in cellulosic CLC was not to be combined with a high quality alignment of the cholesteric structure.rnA swelling process of polymerized films in a dye solution or dissolving dyes in non-polymerized CLC was used for incorporation of the organic chromophores. With the first method the CLC could be aligned and polymerized without any disturbance due to dye molecules. The optical properties of dye and CLC were matched, with regard to mirrorless lasing devices. The dye was optically excited and laser emission supported by the cholesteric cavity was obtained. The polarization and wavelength of the emitted radiation as well as its bandwidth, the obtained interference pattern and threshold behavior of the emission proofed the feedback mechanism that was not believed to be realizable in liquid crystalline polymers. rnUtilization of a microfluidic co-flow injection device enabled us to transfer the properties of cellulosic CLC from the planar film shape to spherical micrometer sized particles. The pure material yielded particles with distorted mesogen alignment similar to films prepared by capillary flow. Dilution of the CLC with a solvent that migrated into the carrier phase during particle preparation provided the basis for particles with well ordered areas. rnAlthough cellulose derivatives were known for their liquid crystalline behavior for decades and synthesized in mass production, their application as feedback material was affected by bad optical properties. In comparison to low molar mass compounds, the low degree of order in the CLC phase was the cause. With the improved material, defined lasing emission was shown and characterized. Derivatives of cellulose are desirable materials, because, as a renewable resource, they are available in large amounts for a low price and need only simple derivatization reactions. The fabrication of CLC films with tunable lasing emission, for which this thesis can provide a starting point, is in good agreement with today's requirements of modern technology and its miniaturization.rn

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.