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.

Oceanic crust and island arc formation in Central Asia during late Neoproterozoic times - evidence from petrological and geochemical studies

Die vorliegende Arbeit behandelt die Entwicklung des 570 Ma alten, neoproterozoischen Agardagh - Tes-Chem Ophioliths (ATCO) in Zentralasien. Dieser Ophiolith liegt südwestlich des Baikalsees (50.5° N, 95° E) und wurde im frühen Stadium der Akkretion des Zentralasiatischen Mobilgürtels auf den nordwestlichen Rand des Tuvinisch-Mongolischen Mikrokontinentes aufgeschoben. Bei dem Zentralasiatische Mobilgürtel handelt es sich um einen riesigen Akkretions-Subduktionskomplex, der heute das größte zusammenhängende Orogen der Erde darstellt. Im Rahmen dieser Arbeit wurden eine Reihe plutonischer und vulkanischer Gesteine, sowie verschiedene Mantelgesteine des ATCO mittels mikroanalytischer und geochemischer Verfahren untersucht (Elektronenstrahlmikrosonde, Ionenstrahlmikrosonde, Spurenelement- und Isotopengeochemie). Die Auswertung dieser Daten ermöglichte die Entwicklung eines geodynamisch-petrologischen Modells zur Entstehung des ATCO. Die vulkanischen Gesteine lassen sich aufgrund ihrer Spurenelement- und Isotopenzusammensetzung in inselbogenbezogene und back-arc Becken bezogene Gesteine (IA-Gesteine und BAB-Gesteine) unterscheiden. Darüber hinaus gibt es eine weitere, nicht eindeutig zuzuordnende Gruppe, die hauptsächlich mafische Gänge umfasst. Der grösste Teil der untersuchen Vulkanite gehört zur Gruppe der IA-Gesteine. Es handelt sich um Al-reiche Basalte und basaltische Andesite, welche aus einem evolvierten Stammmagma mit Mg# 0.60, Cr ~ 180 µg/g und Ni ~ 95 µg/g hauptsächlich durch Klinopyroxenfraktionierung entstanden sind. Das Stammmagma selbst entstand durch Fraktionierung von ca. 12 % Olivin und geringen Anteilen von Cr-Spinell aus einer primären, aus dem Mantel abgeleiteten Schmelze. Die IA-Gesteine haben hohe Konzentrationen an inkompatiblen Spurenelementen (leichte-(L)- Seltenerdelement-(SEE)-Konzentrationen etwa 100-fach chondritisch, chondrit-normierte (La/Yb)c von 14.6 - 5.1), negative Nb-Anomalien (Nb/La = 0.37 - 0.62) und niedrige Zr/Nb Verhältnisse (7 - 14) relativ zu den BAB-Gesteinen. Initiale eNd Werte liegen bei etwa +5.5, initiale Bleiisotopenverhältnisse sind: 206Pb/204Pb = 17.39 - 18.45, 207Pb/204Pb = 15.49 - 15.61, 208Pb/204Pb = 37.06 - 38.05. Die Anreicherung lithophiler inkompatibler Spurenelemente (LILE) in dieser Gruppe ist signifikant (Ba/La = 11 - 130) und zeigt den Einfluss subduzierter Komponenten an. Die BAB-Gesteine repräsentieren Schmelzen, die sehr wahrscheinlich aus der gleichen Mantelquelle wie die IA-Gesteine stammen, aber durch höhere Aufschmelzgrade (8 - 15 %) und ohne den Einfluss subduzierter Komponenten entstanden sind. Sie haben niedrigere Konzentrationen an inkompatiblen Spurenelementen, flache SEE-Muster ((La/Yb)c = 0.6 - 2.4) und höhere initiale eNd Werte zwischen +7.8 und +8.5. Nb Anomalien existieren nicht und Zr/Nb Verhältnisse sind hoch (21 - 48). Um die geochemische Entwicklung der vulkanischen Gesteine des ATCO zu erklären, sind mindestens drei Komponenten erforderlich: (1) eine angereicherte, ozeaninselbasalt-ähnliche Komponente mit hoher Nb Konzentration über ~ 30 µg/g, einem niedrigen Zr/Nb Verhältnis (ca. 6.5), einem niedrigen initialen eNd Wert (um 0), aber mit radiogenen 206Pb/204Pb-, 207Pb/204Pb- und 208Pb/204Pb-Verhältnissen; (2) eine N-MORB ähnliche back-arc Becken Komponente mit flachem SEE-Muster und einem hohen initialen eNd Wert von mindestens +8.5, und (3) eine Inselbogen-Komponente aus einer verarmten Mantelquelle, welche durch die abtauchende Platte geochemisch modifiziert wurde. Die geochemische Entstehung der ATCO Vulkanite lässt sich dann am besten durch eine Kombination aus Quellenkontamination, fraktionierte Kristallisation und Magmenmischung erklären. Geodynamisch gesehen entstand der ATCO sehr wahrscheinlich in einem intraozeanischen Inselbogen - back-arc System. Bei den untersuchten Plutoniten handelt es sich um ultramafische Kumulate (Wehrlite und Pyroxenite) sowie um gabbroische Plutonite (Olivin-Gabbros bis Diorite). Die geochemischen Charakteristika der mafischen Plutonite sind deutlich unterschiedlich zu denen der vulkanischen Gesteine, weshalb sie sehr wahrscheinlich ein späteres Entwicklungsstadium des ATCO repräsentieren. Die Spurenelement-Konzentrationen in den Klinopyroxenen der ultramafischen Kumulate sind extrem niedrig, mit etwa 0.1- bis 1-fach chondritischen SEE-Konzentrationen und mit deutlich LSEE-verarmten Mustern ((La/Yb)c = 0.27 - 0.52). Berechnete Gleichgewichtsschmelzen der ultramafischen Kumulate zeigen grosse Ähnlichkeit zu primären boninitischen Schmelzen. Die primären Magmen waren daher boninitischer Zusammensetzung und entstanden in dem durch vorausgegangene Schmelzprozesse stark verarmten Mantelkeil über einer Subduktionszone. Niedrige Spurenelement-Konzentrationen zeigen einen geringen Einfluss der abtauchenden Platte an. Die Spurenelement-Konzentrationen der Gabbros sind ebenfalls niedrig, mit etwa 0.5 - 10-fach chondritischen SEE-Konzentrationen und mit variablen SEE-Mustern ((La/Yb)c = 0.25 - 2.6). Analog zu den Vulkaniten der IA-Gruppe haben alle Gabbros eine negative Nb-Anomalie mit Nb/La = 0.01 - 0.31. Die initialen eNd Werte der Gabbros variieren zwischen +4.8 und +7.1, mit einem Mittelwert von +5.9, und sind damit identisch mit denen der IA-Vulkanite. Bei den untersuchten Mantelgesteinen handelt es sich um teilweise serpentinisierte Dunite und Harzburgite, die alle durch hohe Mg/Si- und niedrige Al/Si-Verhältnisse gekennzeichnet sind. Dies zeigt einen refraktären Charakter an und steht in guter Übereinstimmung mit den hohen Cr-Zahlen (Cr#) der Spinelle (bis zu Cr# = 0.83), auf deren Basis der Aufschmelzgrad der residuellen Mantelgesteine berechnet wurde. Dieser beträgt etwa 25 %. Die geochemische Zusammensetzung und die petrologischen Daten der Ultramafite und Gabbros lassen sich am besten erklären, wenn man für die Entstehung dieser Gesteine einen zweistufigen Prozess annimmt. In einer ersten Stufe entstanden die ultramafischen Kumulate unter hohem Druck in einer Magmenkammer an der Krustenbasis, hauptsächlich durch Klinopyroxen-Fraktionierung. Bei dieser Magmenkammer handelte es sich um ein offenes System, dem von unten laufend neue Schmelze zugeführt wurde, und aus dem im oberen Bereich evolviertere Schmelzen geringerer Dichte entwichen. Diese evolvierten Schmelzen stiegen in flachere krustale Bereiche auf und bildeten dort meist isolierte Intrusionskörper. Diese Intrusionskörper erstarrten ohne Magmen-Nachschub, weshalb petrographisch sehr unterschiedliche Gesteine entstehen konnten. Eine geochemische Modifikation der abkühlenden Schmelzen erfolgte allerdings durch die Assimilation von Nebengestein. Da innerhalb der Gabbros keine signifikante Variation der initalen eNd Werte existiert, handelte es sich bei dem assimilierten Material hauptsächlich um vulkanische Gesteine des ATCO und nicht um ältere, möglicherweise kontinentale Kruste.

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.

Algorithms for UAS insertion in civil air space

One of the most interesting challenge of the next years will be the Air Space Systems automation. This process will involve different aspects as the Air Traffic Management, the Aircrafts and Airport Operations and the Guidance and Navigation Systems. The use of UAS (Uninhabited Aerial System) for civil mission will be one of the most important steps in this automation process. In civil air space, Air Traffic Controllers (ATC) manage the air traffic ensuring that a minimum separation between the controlled aircrafts is always provided. For this purpose ATCs use several operative avoidance techniques like holding patterns or rerouting. The use of UAS in these context will require the definition of strategies for a common management of piloted and piloted air traffic that allow the UAS to self separate. As a first employment in civil air space we consider a UAS surveillance mission that consists in departing from a ground base, taking pictures over a set of mission targets and coming back to the same ground base. During all mission a set of piloted aircrafts fly in the same airspace and thus the UAS has to self separate using the ATC avoidance as anticipated. We consider two objective, the first consists in the minimization of the air traffic impact over the mission, the second consists in the minimization of the impact of the mission over the air traffic. A particular version of the well known Travelling Salesman Problem (TSP) called Time-Dependant-TSP has been studied to deal with traffic problems in big urban areas. Its basic idea consists in a cost of the route between two clients depending on the period of the day in which it is crossed. Our thesis supports that such idea can be applied to the air traffic too using a convenient time horizon compatible with aircrafts operations. The cost of a UAS sub-route will depend on the air traffic that it will meet starting such route in a specific moment and consequently on the avoidance maneuver that it will use to avoid that conflict. The conflict avoidance is a topic that has been hardly developed in past years using different approaches. In this thesis we purpose a new approach based on the use of ATC operative techniques that makes it possible both to model the UAS problem using a TDTSP framework both to use an Air Traffic Management perspective. Starting from this kind of mission, the problem of the UAS insertion in civil air space is formalized as the UAS Routing Problem (URP). For this reason we introduce a new structure called Conflict Graph that makes it possible to model the avoidance maneuvers and to define the arc cost function of the departing time. Two Integer Linear Programming formulations of the problem are proposed. The first is based on a TDTSP formulation that, unfortunately, is weaker then the TSP formulation. Thus a new formulation based on a TSP variation that uses specific penalty to model the holdings is proposed. Different algorithms are presented: exact algorithms, simple heuristics used as Upper Bounds on the number of time steps used, and metaheuristic algorithms as Genetic Algorithm and Simulated Annealing. Finally an air traffic scenario has been simulated using real air traffic data in order to test our algorithms. Graphic Tools have been used to represent the Milano Linate air space and its air traffic during different days. Such data have been provided by ENAV S.p.A (Italian Agency for Air Navigation Services).

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.

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.

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.

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.

Sperimentazione di protocolli di routing ip su piattaforme raspberry pi.

Tesi mirata allo studio dei protocolli di routing IP utilizzati per l'inoltro dei pacchetti in una topologia non banale. Sono state utilizzate macchine Linux Raspberry Pi per il loro costo e ingombro per costruire la rete. In particolare, è stata implementata una rete caratterizzata da sette router divisi in tre aree distinte, ai quali sono state connesse sette LAN. Si è installato e utilizzato il software quagga per attivare il protocollo OSPF (Open Shortest Path First). Per limitare i dispositivi fisici si è utilizzato il software Mininet per virtualizzare switch e LAN. Infine, sono stati trattati elementi teorici del routing su Internet, applicati alla rete creata per verificarne il funzionamento.

DTN discovery and routing: from space applications to terrestrial networks.

L'argomento di questa tesi è l'architettura di rete Delay-/Disruption-Tolerant Networking (DTN), progettata per operare nelle reti “challenged”, dove la suite di protocolli TCP/IP risulta inefficace a causa di lunghi ritardi di propagazione del segnale, interruzioni e disturbi di canale, ecc. Esempi di reti “challenged” variano dalle reti interplanetarie alle Mobile Ad-Hoc Networks (MANETs). Le principali implementazioni dell'architettura DTN sono DTN2, implementazione di riferimento, e ION, sviluppata da NASA JPL per applicazioni spaziali. Una grande differenza tra reti spaziali e terrestri è che nello spazio i movimenti dei nodi sono deterministici, mentre non lo sono per i nodi mobili terrestri, i quali generalmente non conoscono la topologia della rete. Questo ha portato allo sviluppo di diversi algoritmi di routing: deterministici per le reti spaziali e opportunistici per quelle terrestri. NASA JPL ha recentemente deciso di estendere l'ambito di applicazione di ION per supportare anche scenari non deterministici. Durante la tesi, svolta presso NASA JPL, mi sono occupato di argomenti diversi, tutti finalizzati a questo obiettivo. Inizialmente ho testato la nuova implementazione dell'algoritmo IP Neighbor Discovery (IPND) di ION, corretti i bug e prodotta la documentazione ufficiale. Quindi ho contribuito ad integrare il Contact Graph Routing (CGR) di ION nel simulatore DTN “ONE” utilizzando la Java Native Interface (JNI) come ponte tra il codice Java di ONE e il codice C di ION. In particolare ho adattato tutte le librerie di ION necessarie per far funzionare CGR all'interno dell'ambiente di ONE. Infine, dopo aver analizzato un dataset di tracce reali di nodi mobili, ho contribuito a progettare e a sviluppare OCGR, estensione opportunistica del CGR, quindi ne ho curato l'integrazione in ONE. I risultati preliminari sembrano confermare la validità di OCGR che, una volta messo a punto, può diventare un valido concorrente ai più rinomati algoritmi opportunistici.