Formulations and Algorithms for Routing Problems

Combinatorial Optimization is a branch of optimization that deals with the problems where the set of feasible solutions is discrete. Routing problem is a well studied branch of Combinatorial Optimization that concerns the process of deciding the best way of visiting the nodes (customers) in a network. Routing problems appear in many real world applications including: Transportation, Telephone or Electronic data Networks. During the years, many solution procedures have been introduced for the solution of different Routing problems. Some of them are based on exact approaches to solve the problems to optimality and some others are based on heuristic or metaheuristic search to find optimal or near optimal solutions. There is also a less studied method, which combines both heuristic and exact approaches to face different problems including those in the Combinatorial Optimization area. The aim of this dissertation is to develop some solution procedures based on the combination of heuristic and Integer Linear Programming (ILP) techniques for some important problems in Routing Optimization. In this approach, given an initial feasible solution to be possibly improved, the method follows a destruct-and-repair paradigm, where the given solution is randomly destroyed (i.e., customers are removed in a random way) and repaired by solving an ILP model, in an attempt to find a new improved solution.

Generazione di istanze difficili per problemi di impaccamento e routing

La presente tesi è il frutto di un lavoro di ricerca sugli aspetti che rendono gli algoritmi esatti per CVRP presenti in letteratura poco efficienti su certi tipi di istanze. L'ipotesi iniziale era che gli algoritmi incontrassero difficoltà di risoluzione su istanze di CVRP dotate di un numero limitato di soluzioni di Bin Packing. Allo scopo di verificare la validità di tale supposizione, sono state create istanze di Bin Packing aventi poche soluzioni ottime e sono stati aggiunti tre differenti schemi di routing. Le istanze CVRP sono state risolte con l'algoritmo del dr. Roberti, già presente in letteratura.

Speciation of tetravalent plutonium in contact with humic substances and kaolinite under environmental conditions

Plutonium represents the major contribution to the radiotoxicity of spent nuclear fuel over storage times of up to several hundred thousand years. The speciation of plutonium in aquifer systems is important in order to assess the risks of high-level nuclear waste disposal and to acquire a deep knowledge of the mobilization and immobilization behavior of plutonium. In aqueous solutions, plutonium can coexist in four oxidation states and each one of them has different chemical and physical behavior. Tetravalent plutonium is the most abundant under natural conditions. Therefore, detailed speciation studies of tetravalent plutonium in contact with humic substances (HS) and kaolinite as a model clay mineral have been performed in this work. Plutonium is present in the environment at an ultratrace level. Therefore, speciation of Pu at the ultratrace level is mandatory. Capillary electrophoresis (CE) coupled to resonance ionization mass spectrometry (RIMS) was used as a new speciation method. CE-RIMS enables to improve the detection limit for plutonium species by 2 to 3 orders of magnitude compared to the previously developed CE-ICP-MS. For understanding the behavior of Pu(IV) in aqueous systems, redox reactions, complexation, and sorption behavior of plutonium were studied. The redox behavior of plutonium in contact with humic acid (HA) and fulvic acid (FA) was investigated. A relatively fast reduction of Pu(VI) in contact with HS was observed. It was mainly reduced to Pu(IV) and Pu(III) within a couple of weeks. The time dependence of the Pu(IV) complexation with Aldrich HA was investigated and a complex constant (logßLC) between 6.4 - 8.4 of Pu(IV) was determined by means of ultrafiltration taking into account the loading capacity (LC). The sorption of tetravalent plutonium onto kaolinite was investigated as a function of pH in batch experiments under aerobic and anaerobic conditions. The sorption edge was found at about pH = 1 and a maximum sorption at around pH = 8.5. In the presence of CO2 at pH > 8.5, the sorption of plutonium was decreased probably due to the formation of soluble carbonate complexes. For comparison, the sorption of Th(IV) onto kaolinite was also investigated and consistent results were found. The Pu(IV) sorption onto kaolinite was studied by XANES and EXAFS at pH 1, 4, 9 and the sorbed species on kaolinite surface was Pu(IV). Depending on the pH, only 1 - 10 % of the sorbed plutonium is desorbed from kaolinite and released into a fresh solution at the same pH value. Furthermore, the sorption of HS onto kaolinite was studied as a function of pH at varying concentrations of HS, as a prerequisite to understand the more complex ternary system. The sorption of HA onto kaolinite was found to be higher than that of FA. The investigation of the ternary systems (plutonium-kaolinite-humic substances) is performed as a function of pH, concentration of HS, and the sequences of adding the reactants. The presence of HS strongly influences the sorption of Pu(IV) onto kaolinite over the entire pH range. For comparison, the influence of HS on the sorption of Th(IV) onto kaolinite was also investigated and a good agreement with the results of Pu(IV) was obtained.

Exact Algorithms for Different Classes of Vehicle Routing Problems

We deal with five problems arising in the field of logistics: the Asymmetric TSP (ATSP), the TSP with Time Windows (TSPTW), the VRP with Time Windows (VRPTW), the Multi-Trip VRP (MTVRP), and the Two-Echelon Capacitated VRP (2E-CVRP). The ATSP requires finding a lest-cost Hamiltonian tour in a digraph. We survey models and classical relaxations, and describe the most effective exact algorithms from the literature. A survey and analysis of the polynomial formulations is provided. The considered algorithms and formulations are experimentally compared on benchmark instances. The TSPTW requires finding, in a weighted digraph, a least-cost Hamiltonian tour visiting each vertex within a given time window. We propose a new exact method, based on new tour relaxations and dynamic programming. Computational results on benchmark instances show that the proposed algorithm outperforms the state-of-the-art exact methods. In the VRPTW, a fleet of identical capacitated vehicles located at a depot must be optimally routed to supply customers with known demands and time window constraints. Different column generation bounding procedures and an exact algorithm are developed. The new exact method closed four of the five open Solomon instances. The MTVRP is the problem of optimally routing capacitated vehicles located at a depot to supply customers without exceeding maximum driving time constraints. Two set-partitioning-like formulations of the problem are introduced. Lower bounds are derived and embedded into an exact solution method, that can solve benchmark instances with up to 120 customers. The 2E-CVRP requires designing the optimal routing plan to deliver goods from a depot to customers by using intermediate depots. The objective is to minimize the sum of routing and handling costs. A new mathematical formulation is introduced. Valid lower bounds and an exact method are derived. Computational results on benchmark instances show that the new exact algorithm outperforms the state-of-the-art exact methods.

Interactive simulation of flexible parts

Computer simulations play an ever growing role for the development of automotive products. Assembly simulation, as well as many other processes, are used systematically even before the first physical prototype of a vehicle is built in order to check whether particular components can be assembled easily or whether another part is in the way. Usually, this kind of simulation is limited to rigid bodies. However, a vehicle contains a multitude of flexible parts of various types: cables, hoses, carpets, seat surfaces, insulations, weatherstrips... Since most of the problems using these simulations concern one-dimensional components and since an intuitive tool for cable routing is still needed, we have chosen to concentrate on this category, which includes cables, hoses and wiring harnesses. In this thesis, we present a system for simulating one dimensional flexible parts such as cables or hoses. The modeling of bending and torsion follows the Cosserat model. For this purpose we use a generalized spring-mass system and describe its configuration by a carefully chosen set of coordinates. Gravity and contact forces as well as the forces responsible for length conservation are expressed in Cartesian coordinates. But bending and torsion effects can be dealt with more effectively by using quaternions to represent the orientation of the segments joining two neighboring mass points. This augmented system allows an easy formulation of all interactions with the best appropriate coordinate type and yields a strongly banded Hessian matrix. An energy minimizing process accounts for a solution exempt from the oscillations that are typical of spring-mass systems. The use of integral forces, similar to an integral controller, allows to enforce exactly the constraints. The whole system is numerically stable and can be solved at interactive frame rates. It is integrated in the DaimlerChrysler in-house Virtual Reality Software veo for use in applications such as cable routing and assembly simulation and has been well received by users. Parts of this work have been published at the ACM Solid and Physical Modeling Conference 2006 and have been selected for the special issue of the Computer-Aided-Design Journal to the conference.

Numerical simulation of interdigitated back contact hetero-junction solar cells

The goal of this thesis is the application of an opto-electronic numerical simulation to heterojunction silicon solar cells featuring an all back contact architecture (Interdigitated Back Contact Hetero-Junction IBC-HJ). The studied structure exhibits both metal contacts, emitter and base, at the back surface of the cell with the objective to reduce the optical losses due to the shadowing by front contact of conventional photovoltaic devices. Overall, IBC-HJ are promising low-cost alternatives to monocrystalline wafer-based solar cells featuring front and back contact schemes, in fact, for IBC-HJ the high concentration doping diffusions are replaced by low-temperature deposition processes of thin amorphous silicon layers. Furthermore, another advantage of IBC solar cells with reference to conventional architectures is the possibility to enable a low-cost assembling of photovoltaic modules, being all contacts on the same side. A preliminary extensive literature survey has been helpful to highlight the specific critical aspects of IBC-HJ solar cells as well as the state-of-the-art of their modeling, processing and performance of practical devices. In order to perform the analysis of IBC-HJ devices, a two-dimensional (2-D) numerical simulation flow has been set up. A commercial device simulator based on finite-difference method to solve numerically the whole set of equations governing the electrical transport in semiconductor materials (Sentuarus Device by Synopsys) has been adopted. The first activity carried out during this work has been the definition of a 2-D geometry corresponding to the simulation domain and the specification of the electrical and optical properties of materials. In order to calculate the main figures of merit of the investigated solar cells, the spatially resolved photon absorption rate map has been calculated by means of an optical simulator. Optical simulations have been performed by using two different methods depending upon the geometrical features of the front interface of the solar cell: the transfer matrix method (TMM) and the raytracing (RT). The first method allows to model light prop-agation by plane waves within one-dimensional spatial domains under the assumption of devices exhibiting stacks of parallel layers with planar interfaces. In addition, TMM is suitable for the simulation of thin multi-layer anti reflection coating layers for the reduction of the amount of reflected light at the front interface. Raytracing is required for three-dimensional optical simulations of upright pyramidal textured surfaces which are widely adopted to significantly reduce the reflection at the front surface. The optical generation profiles are interpolated onto the electrical grid adopted by the device simulator which solves the carriers transport equations coupled with Poisson and continuity equations in a self-consistent way. The main figures of merit are calculated by means of a postprocessing of the output data from device simulation. After the validation of the simulation methodology by means of comparison of the simulation result with literature data, the ultimate efficiency of the IBC-HJ architecture has been calculated. By accounting for all optical losses, IBC-HJ solar cells result in a theoretical maximum efficiency above 23.5% (without texturing at front interface) higher than that of both standard homojunction crystalline silicon (Homogeneous Emitter HE) and front contact heterojuction (Heterojunction with Intrinsic Thin layer HIT) solar cells. However it is clear that the criticalities of this structure are mainly due to the defects density and to the poor carriers transport mobility in the amorphous silicon layers. Lastly, the influence of the most critical geometrical and physical parameters on the main figures of merit have been investigated by applying the numerical simulation tool set-up during the first part of the present thesis. Simulations have highlighted that carrier mobility and defects level in amorphous silicon may lead to a potentially significant reduction of the conversion efficiency.

Heuristic algorithms for the Capacitated Location-Routing Problem and the Multi-Depot Vehicle Routing Problem

The Capacitated Location-Routing Problem (CLRP) is a NP-hard problem since it generalizes two well known NP-hard problems: the Capacitated Facility Location Problem (CFLP) and the Capacitated Vehicle Routing Problem (CVRP). The Multi-Depot Vehicle Routing Problem (MDVRP) is known to be a NP-hard since it is a generalization of the well known Vehicle Routing Problem (VRP), arising with one depot. This thesis addresses heuristics algorithms based on the well-know granular search idea introduced by Toth and Vigo (2003) to solve the CLRP and the MDVRP. Extensive computational experiments on benchmark instances for both problems have been performed to determine the effectiveness of the proposed algorithms. This work is organized as follows: Chapter 1 describes a detailed overview and a methodological review of the literature for the the Capacitated Location-Routing Problem (CLRP) and the Multi-Depot Vehicle Routing Problem (MDVRP). Chapter 2 describes a two-phase hybrid heuristic algorithm to solve the CLRP. Chapter 3 shows a computational comparison of heuristic algorithms for the CLRP. Chapter 4 presents a hybrid granular tabu search approach for solving the MDVRP.

La misura dell'impedenza locale con tecnologia Contact nello studio elettrofisiologico

Questo lavoro di Tesi Magistrale, si focalizza sulla più importante delle aritmie atriali, ovvero la Fibrillazione Atriale, e sul trattamento della stessa attraverso le procedure di ablazione a radio frequenza (RF). Il lavoro di tesi, svolto presso l'Ospedale 'M. Bufalini' di Cesena, affronta in particolare l'uso della tecnologia EnSite NavX (un sistema di mappaggio elettroanatomico delle cavità cardiache) ed EnSite Contact (un sistema basato sulla misura dell'impedenza locale per la valutazione del contatto elettrodo tessuto). L'acquisizione e l'analisi dei dati di ECI (indice di accoppiamento elettrico), forniti dal modulo Contact, hanno permesso di comprendere come questo parametro, derivato dalla misura dell'impedenza locale, possa contribuire a fornire importanti informazioni in real-time all'elettrofisiologo e come lo studio della sua dinamica, con particolare attenzione alle variazioni tra pre e post ablazione, possa risultare utile per verificare l'avvenuta erogazione di energia ai tessuti.

Metodi euristici per il Vehicle Routing Problem

Il problema della consegna di prodotti da un deposito/impianto ai clienti mediante una flotta di automezzi è un problema centrale nella gestione di una catena di produzione e distribuzione (supply chain). Questo problema, noto in letteratura come Vehicle Routing Problem (VRP), nella sua versione più semplice consiste nel disegnare per ogni veicolo disponibile presso un dato deposito aziendale un viaggio (route) di consegna dei prodotti ai clienti, che tali prodotti richiedono, in modo tale che (i) la somma delle quantità richieste dai clienti assegnati ad ogni veicolo non superi la capacità del veicolo, (ii) ogni cliente sia servito una ed una sola volta, (iii) sia minima la somma dei costi dei viaggi effettuati dai veicoli. Il VRP è un problema trasversale ad una molteplicità di settori merceologici dove la distribuzione dei prodotti e/o servizi avviene mediante veicoli su gomma, quali ad esempio: distribuzione di generi alimentari, distribuzione di prodotti petroliferi, raccolta e distribuzione della posta, organizzazione del servizio scuolabus, pianificazione della manutenzione di impianti, raccolta rifiuti, etc. In questa tesi viene considerato il Multi-Trip VRP, in cui ogni veicolo può eseguire un sottoinsieme di percorsi, chiamato vehicle schedule (schedula del veicolo), soggetto a vincoli di durata massima. Nonostante la sua importanza pratica, il MTVRP ha ricevuto poca attenzione in letteratura: sono stati proposti diversi metodi euristici e un solo algoritmo esatto di risoluzione, presentato da Mingozzi, Roberti e Toth. In questa tesi viene presentato un metodo euristico in grado di risolvere istanze di MTVRP in presenza di vincoli reali, quali flotta di veicoli non omogenea e time windows. L’euristico si basa sul modello di Prins. Sono presentati inoltre due approcci di local search per migliorare la soluzione finale. I risultati computazionali evidenziano l’efficienza di tali approcci.

Teoria dei giochi e Multi-criteria decision-making per reti mobili Ad-hoc: un protocollo di routing

Nell'elaborato si analizzano aspetti della teoria dei giochi e della multi-criteria decision-making. La riflessione serve a proporre le basi per un nuovo modello di protocollo di routing in ambito Mobile Ad-hoc Networks. Questo prototipo mira a generare una rete che riesca a gestirsi in maniera ottimale grazie ad un'acuta tecnica di clusterizzazione. Allo stesso tempo si propone come obiettivo il risparmio energetico e la partecipazione collaborativa di tutti i componenti.

Tailoring molecule nanostructures on insulating surfaces investigated by non-contact atomic force microscopy

Self-assembled molecular structures were investigated on insulating substrate surfaces using non-contact atomic force microscopy. Both, substrate preparation and molecule deposition, took place under ultra-high vacuum conditions. First, C60 molecules were investigated on the TiO2 (110) surface. This surface exhibits parallel running troughs at the nanometer scale, which strongly steer the assembly of the molecules. This is in contrast to the second investigated surface. The CaF2 (111) surface is atomically flat and the molecular assemblyrnwas observed to be far less affected by the surface. Basically different island structures were observed to what is typically know. Based on extensive experimental studies and theoretical considerations, a comprehensive picture of the processes responsible for the island formation of C60 molecules on this insulating surfaces was developed. The key process for the emergence of the observed novel island structures was made out to be the dewetting of molecules from the substrate. This new knowledge allows to further understand andrnexploit self-assembly techniques in structure fabrication on insulating substrate surfaces. To alter island formation and island structure, C60 molecules were codeposited with second molecule species (PTCDI and SubPc) on the CaF2 (111) surface. Depending on the order of deposition, quiet different structures were observed to arise. Thus, these are the first steps towards more complex functional arrangements consisting of two molecule species on insulating surfaces.

Una rassegna degli algoritmi di routing in reti veicolari

Nell'elaborato sono analizzati diversi tipi di algoritmi di routing per reti VANET. Nel secondo capitolo verrà fornita una panoramica delle reti MANET e VANET. Nel terzo capitolo sono viste le caratteristiche delle reti VANET. Nel quarto verranno esposte le peculiarità di classificazione dei protocolli di routing routing e nel quinto capitolo saranno analizzati diversi protocolli di routing proposti fino ad ora nella letteratura.

Opportunistic Data Gathering and Dissemination in Urban Scenarios

In the era of the Internet of Everything, a user with a handheld or wearable device equipped with sensing capability has become a producer as well as a consumer of information and services. The more powerful these devices get, the more likely it is that they will generate and share content locally, leading to the presence of distributed information sources and the diminishing role of centralized servers. As of current practice, we rely on infrastructure acting as an intermediary, providing access to the data. However, infrastructure-based connectivity might not always be available or the best alternative. Moreover, it is often the case where the data and the processes acting upon them are of local scopus. Answers to a query about a nearby object, an information source, a process, an experience, an ability, etc. could be answered locally without reliance on infrastructure-based platforms. The data might have temporal validity limited to or bounded to a geographical area and/or the social context where the user is immersed in. In this envisioned scenario users could interact locally without the need for a central authority, hence, the claim of an infrastructure-less, provider-less platform. The data is owned by the users and consulted locally as opposed to the current approach of making them available globally and stay on forever. From a technical viewpoint, this network resembles a Delay/Disruption Tolerant Network where consumers and producers might be spatially and temporally decoupled exchanging information with each other in an adhoc fashion. To this end, we propose some novel data gathering and dissemination strategies for use in urban-wide environments which do not rely on strict infrastructure mediation. While preserving the general aspects of our study and without loss of generality, we focus our attention toward practical applicative scenarios which help us capture the characteristics of opportunistic communication networks.