Algorithms for network design and routing problems

In this thesis we study three combinatorial optimization problems belonging to the classes of Network Design and Vehicle Routing problems that are strongly linked in the context of the design and management of transportation networks: the Non-Bifurcated Capacitated Network Design Problem (NBP), the Period Vehicle Routing Problem (PVRP) and the Pickup and Delivery Problem with Time Windows (PDPTW). These problems are NP-hard and contain as special cases some well known difficult problems such as the Traveling Salesman Problem and the Steiner Tree Problem. Moreover, they model the core structure of many practical problems arising in logistics and telecommunications. The NBP is the problem of designing the optimum network to satisfy a given set of traffic demands. Given a set of nodes, a set of potential links and a set of point-to-point demands called commodities, the objective is to select the links to install and dimension their capacities so that all the demands can be routed between their respective endpoints, and the sum of link fixed costs and commodity routing costs is minimized. The problem is called non- bifurcated because the solution network must allow each demand to follow a single path, i.e., the flow of each demand cannot be splitted. Although this is the case in many real applications, the NBP has received significantly less attention in the literature than other capacitated network design problems that allow bifurcation. We describe an exact algorithm for the NBP that is based on solving by an integer programming solver a formulation of the problem strengthened by simple valid inequalities and four new heuristic algorithms. One of these heuristics is an adaptive memory metaheuristic, based on partial enumeration, that could be applied to a wider class of structured combinatorial optimization problems. In the PVRP a fleet of vehicles of identical capacity must be used to service a set of customers over a planning period of several days. Each customer specifies a service frequency, a set of allowable day-combinations and a quantity of product that the customer must receive every time he is visited. For example, a customer may require to be visited twice during a 5-day period imposing that these visits take place on Monday-Thursday or Monday-Friday or Tuesday-Friday. The problem consists in simultaneously assigning a day- combination to each customer and in designing the vehicle routes for each day so that each customer is visited the required number of times, the number of routes on each day does not exceed the number of vehicles available, and the total cost of the routes over the period is minimized. We also consider a tactical variant of this problem, called Tactical Planning Vehicle Routing Problem, where customers require to be visited on a specific day of the period but a penalty cost, called service cost, can be paid to postpone the visit to a later day than that required. At our knowledge all the algorithms proposed in the literature for the PVRP are heuristics. In this thesis we present for the first time an exact algorithm for the PVRP that is based on different relaxations of a set partitioning-like formulation. The effectiveness of the proposed algorithm is tested on a set of instances from the literature and on a new set of instances. Finally, the PDPTW is to service a set of transportation requests using a fleet of identical vehicles of limited capacity located at a central depot. Each request specifies a pickup location and a delivery location and requires that a given quantity of load is transported from the pickup location to the delivery location. Moreover, each location can be visited only within an associated time window. Each vehicle can perform at most one route and the problem is to satisfy all the requests using the available vehicles so that each request is serviced by a single vehicle, the load on each vehicle does not exceed the capacity, and all locations are visited according to their time window. We formulate the PDPTW as a set partitioning-like problem with additional cuts and we propose an exact algorithm based on different relaxations of the mathematical formulation and a branch-and-cut-and-price algorithm. The new algorithm is tested on two classes of problems from the literature and compared with a recent branch-and-cut-and-price algorithm from the literature.

Liquid crystal polymers: macromolecular design for enhanced performances

During this work, done mainly in the laboratories of the department of Industrial Chemistry and Materials of the University of Bologna but also in the laboratories of the Carnegie Mellon University in collaboration with prof. K. Matyjaszewski and at the university of Zaragoza in collaboration with prof. J. Barberá, was focused mainly on the synthesis and characterization of new functional polymeric materials. In the past years our group gained a deep knowledge about the photomodulation of azobenzene containing polymers. The aim of this thesis is to push forward the performances of these materials by the synthesis of well defined materials, in which, by a precise control over the macromolecular structures, better or even new functionality can be delivered to the synthesized material. For this purpose, besides the rich photochemistry of azoaromatic polymers that brings to the application, the control offered from the recent techniques of controlled radical polymerization, ATRP over all, gives an enormous range of opportunity for the developing of a new generation of functional materials whose properties are determinate not only by the chemical nature of the functional center (e.g. azoaromatic chromophore) but are tuned and even amplified by a synergy with the whole macromolecular structure. Old materials in new structures. In this contest the work of this thesis was focused mainly on the synthesis and characterization of well defined azoaromatic polymers in order to establish, for the first time, precise structure-properties correlation. In fact a series of well defined different azopolymers, chiral and achiral, with different molecular weight and highly monodisperse were synthesized and their properties were studied, in terms of photoexpansion and photomodulation of chirality. We were then able to study the influence of the macromolecular structure in terms of molecular weight and ramification on the studied properties. The huge amount of possibility offered by the tailoring of the macromolecular structure were exploited for the synthesis of new cholesteric photochromic polymers that can be used as a smart label for the certification of the thermal history of any thermosensitive product. Finally the ATRP synthesis allowed us to synthesize a total new class of material, named molecular brushes: a flat surface covered with an ultra thin layer of polymeric chain covalently bond onto the surface from one end. This new class of materials is of extreme interest as they offer the possibility to tune and manage the interaction of the surface with the environment. In this contest we synthesized both azoaromatic surfaces, growing directly the polymer from the surface, and mixed brushes: surfaces covered with incompatible macromolecules. Both type of surfaces acts as “smart” surfaces: the first it is able to move the orientation of a LC cell by simply photomodulation and, thanks to the robustness of the covalent bond, can be used as a command surface overcoming all the limitation due to the dewetting of the active layer. The second type of surface, functionalized by a grafting-to method, can self assemble the topmost layer responding to changed environmental conditions, exposing different functionality according to different environment.

Design and development of new green catalytic methodologies for the synthesis of enantiomerically enriched molecules

The following Ph.D work was mainly focused on catalysis, as a key technology, to achieve the objectives of sustainable (green) chemistry. After introducing the concepts of sustainable (green) chemistry and an assessment of new sustainable chemical technologies, the relationship between catalysis and sustainable (green) chemistry was briefly discussed and illustrated via an analysis of some selected and relevant examples. Afterwards, as a continuation of the ongoing interest in Dr. Marco Bandini’s group on organometallic and organocatalytic processes, I addressed my efforts to the design and development of novel catalytic green methodologies for the synthesis of enantiomerically enriched molecules. In the first two projects the attention was focused on the employment of solid supports to carry out reactions that still remain a prerogative of omogeneous catalysis. Firstly, particular emphasis was addressed to the discovery of catalytic enantioselective variants of nitroaldol condensation (commonly termed Henry reaction), using a complex consisting in a polyethylene supported diamino thiopene (DATx) ligands and copper as active species. In the second project, a new class of electrochemically modified surfaces with DATx palladium complexes was presented. The DATx-graphite system proved to be efficient in promoting the Suzuki reaction. Moreover, in collaboration with Prof. Wolf at the University of British Columbia (Vancouver), cyclic voltammetry studies were reported. This study disclosed new opportunities for carbon–carbon forming processes by using heterogeneous, electrodeposited catalyst films. A straightforward metal-free catalysis allowed the exploration around the world of organocatalysis. In fact, three different and novel methodologies, using Cinchona, Guanidine and Phosphine derivatives, were envisioned in the three following projects. An interesting variant of nitroaldol condensation with simple trifluoromethyl ketones and also their application in a non-conventional activation of indolyl cores by Friedel-Crafts-functionalization, led to two novel synthetic protocols. These approaches allowed the preparation of synthetically useful trifluoromethyl derivatives bearing quaternary stereocenters. Lastly, in the sixth project the first γ-alkylation of allenoates with conjugated carbonyl compounds was envisioned. In the last part of this Ph.D thesis bases on an extra-ordinary collaboration with Prof. Balzani and Prof. Gigli, I was involved in the synthesis and characterization of a new type of heteroleptic cyclometaled-Ir(III) complexes, bearing bis-oxazolines (BOXs) as ancillary ligands. The new heteroleptic complexes were fully characterized and in order to examine the electroluminescent properties of FIrBOX(CH2), an Organic Light Emitting Device was realized.

The integration of curriculum and assessment in interpreter education

In dieser interdisziplinären, translationswissenschaftlichen Studie wird die Integration von Curriculum und Evaluierung in der Dolmetscherausbildung theoretisch fundiert und im Rahmen einer Fallstudie empirisch untersucht. Dolmetschkompetenz wird als ein durch zweckgerechte und messgenaue (valid and reliable) Bewertungsmethoden dokumentiertes Ergebnis der Curriculumanwendung betrachtet. Definitionen, Grundlagen, Ansätze, Ausbildungs- und Lernziele werden anhand der Curriculumtheorie und Dolmetschwissenschaft beschrieben. Traditionelle und alternative Evaluierungsmethoden werden hinsichtlich ihrer Anwendbarkeit in der Dolmetscherausbildung erprobt. In der Fallstudie werden die Prüfungsergebnisse zweier Master-Studiengänge-MA Konferenzdolmetschen und MA Dolmetschen und Übersetzen-quantitativ analysiert. Die zur Dokumentation der Prüfungsergebnisse eingesetzte Bewertungsmethodik wird qualitativ untersucht und zur quantitativen Analyse in Bezug gesetzt. Die Fallstudie besteht aus 1) einer chi-square-Analyse der Abschlussprüfungsnoten getrennt nach Sprachkombination und Prüfungskategorie (n=260), 2) einer Umfrage unter den Jurymitgliedern hinsichtlich der Evaluierungsansätze, -verfahren, und -kriterien (n = 45; 62.22% Rücklaufrate); und 3) einer Analyse des ausgangssprachlichen Prüfungsmaterials ebenfalls nach Sprachkombination und Prüfungskategorie. Es wird nachgewiesen, dass Studierende im MA Dolmetschen und Übersetzen tendenziell schlechtere Prüfungsleistungen erbringen als Studierende im MA Konferenzdolmetschen. Die Analyseergebnisse werden jedoch als aussageschwach betrachtet aufgrund mangelnder Evaluierungsvalidität. Schritte zur Curriculum- und Evaluierungsoptimierung sowie ein effizienteres Curriculummodell werden aus den theoretischen Ansätzen abgeleitet. Auf die Rolle der Ethik in der Evaluierungsmethodik wird hingewiesen.

Structural design, manufacturing and testing of the new wing for the CSIR's Modular UAS in composite materials

In the framework of an international collaboration with South Africa CSIR, the structural design, manufacturing and testing of the new wing for the Modular UAS in composite materials has been performed.

Optical Design for Automatic Identification and Portable Systems

This thesis proposes design methods and test tools, for optical systems, which may be used in an industrial environment, where not only precision and reliability but also ease of use is important. The approach to the problem has been conceived to be as general as possible, although in the present work, the design of a portable device for automatic identification applications has been studied, because this doctorate has been funded by Datalogic Scanning Group s.r.l., a world-class producer of barcode readers. The main functional components of the complete device are: electro-optical imaging, illumination and pattern generator systems. For what concerns the electro-optical imaging system, a characterization tool and an analysis one has been developed to check if the desired performance of the system has been achieved. Moreover, two design tools for optimizing the imaging system have been implemented. The first optimizes just the core of the system, the optical part, improving its performance ignoring all other contributions and generating a good starting point for the optimization of the whole complex system. The second tool optimizes the system taking into account its behavior with a model as near as possible to reality including optics, electronics and detection. For what concerns the illumination and the pattern generator systems, two tools have been implemented. The first allows the design of free-form lenses described by an arbitrary analytical function exited by an incoherent source and is able to provide custom illumination conditions for all kind of applications. The second tool consists of a new method to design Diffractive Optical Elements excited by a coherent source for large pattern angles using the Iterative Fourier Transform Algorithm. Validation of the design tools has been obtained, whenever possible, comparing the performance of the designed systems with those of fabricated prototypes. In other cases simulations have been used.