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.

Networks, Uncertainty, Applications and a Crusade for Optimality

In this thesis we address a collection of Network Design problems which are strongly motivated by applications from Telecommunications, Logistics and Bioinformatics. In most cases we justify the need of taking into account uncertainty in some of the problem parameters, and different Robust optimization models are used to hedge against it. Mixed integer linear programming formulations along with sophisticated algorithmic frameworks are designed, implemented and rigorously assessed for the majority of the studied problems. The obtained results yield the following observations: (i) relevant real problems can be effectively represented as (discrete) optimization problems within the framework of network design; (ii) uncertainty can be appropriately incorporated into the decision process if a suitable robust optimization model is considered; (iii) optimal, or nearly optimal, solutions can be obtained for large instances if a tailored algorithm, that exploits the structure of the problem, is designed; (iv) a systematic and rigorous experimental analysis allows to understand both, the characteristics of the obtained (robust) solutions and the behavior of the proposed algorithm.

Heuristic algorithms for the travelling deliveryman problem

Algoritmi euristici per la risoluzione del Travelling DEliveryman Problem

Algoritmi per la soluzione del problema dell'assegnamento generalizzato

La tesi analizza gli algoritmi per risolvere il problema dell'assegnamento generalizzato, e valuta in particolare le prestazioni dell'algoritmo di Posta ed altri.

I neologismi autoriali e la loro traduzione nella saga di Harry Potter: il caso dello spagnolo e dell'italiano

L'elaborato analizza i neologismi autoriali creati nella saga di Harry Potter, dapprima nella loro versione originale studiando i meccanismi di formazione di neologismi più utilizzati. In seguito, i neologismi originali vengono messi a confronto con le loro traduzioni in italiano e spagnolo, studiando le strategie traduttive messe in atto dai rispettivi team di traduttori. I dati analizzati vengono poi ricondotti alla teoria della traduzione della letteratura per l'infanzia e ai distinti filoni individuabili nei due Paesi.

Censimento, raccolta e analisi delle serie di altezze di precipitazione mensili nelle stazioni storiche del territorio romagnolo

Estrapolazione dati riguardanti le altezze di precipitazione dagli Annali Idrografici, relativi a 34 stazioni pluviometriche della Romagna. Elaborazione ed analisi di istogrammi che rappresentano le altezze di precipitazione annuale delle stazioni, dal 1924 al 2014, con l’aggiunta di grafici inerenti il totale delle precipitazioni mensili, con relativa linea di media. Utilizzo del test di Mann-kendall attraverso il quale si è tracciata la linea di tendenza, per ogni singola stazione, con calcolo successivo della pendenza di Sen e del p-value. Valutazione stazioni con p-value molto piccoli (Brisighella, Predappio, Strada San Zeno, San Benedetto in Alpe), attraverso i totali stagionali, e successivo istogramma, utile per verificare l'effettiva coerenza tra il trend annuale e quello stagionale. Considerazioni finali sui trend significativi.

Germanismen in der slowakischen Sprache: Analyse und praktische Glossare für Dolmetscher.

Il presente elaborato finale ha l’obiettivo di effettuare una ricerca, un’analisi e una catalogazione in glossari dei germanismi all’interno della lingua slovacca, la quale presenta all’incirca tremila termini provenienti dalle lingue germano-tedesche. Sulla base del lavoro svolto precedentemente da numerosi linguisti slovacchi (tra cui Petrovič, Žilová, Adamcová, Dolník, Decsy, Habovštiak, Habovštiaková, Žigo, Múcsková, Blanár, Doruľa, Palkovič, Papsonová, Kozmová) e altri linguisti germanofoni e ungheresi (tra cui Ziegler, Greule, Meier, Toth, Rudolf, Muhr) è stato raccolto il materiale fondamentale per la stesura della presente tesi di laurea. Tuttavia l’opera che getta le basi per l’analisi è Sprachontakte Deutsch - Tschechisch - Slowakisch dello slavista e professore presso l’Università di Vienna Stephan Michael Newerkla, il quale ha stilato un vero e proprio dizionario dei germanismi presenti nello slovacco e nel ceco suddividendoli in categorie temporali, a cominciare dal gotico per finire con il nuovo tedesco standard. All’interno della sua opera l’autore austriaco ha inserito anche le parole che solo presumibilmente o secondo alcuni precedenti linguisti avrebbero origine germanica e i termini la cui presunta provenienza dal tedesco è stata riconosciuta come erronea; nel presente elaborato sono state prese in considerazione invece solo le parole di certa origine tedesca. Le parole sono state selezionate e suddivise in quattordici categorie semantico-lessicali: 1. Industria mineraria, utensili, numismatica e minerali, 2. Edifici, locali e arredamento, 3. Tessuti e stoffe, 4. Strumenti musicali, 5. Vestiti, 6. Alimentari e consumo, 7. Termini bellici, 8. Persone e funzioni, 9. Piante ed elementi chimici, 10. Religione e costumi, 11. Animali e le loro parti del corpo, 12. Verbi, 13. Aggettivi, 14. Parole rimanenti In ogni singolo glossario vi sono tre colonne: nella prima si trova il termine slovacco accompagnato dalla sua definizione, nella seconda vi è la traduzione della parola in italiano e nella terza il significato e la spiegazione dell’origine in tedesco. Al presente elaborato viene allegato un appendice finale in cui sono riportati in ordine alfabetico tutti i germanismi analizzati assieme a quelli non più in uso.

Metodi per la stima spaziale della temperatura in territori ad orografia complessa e parametrizzazione di un modello idrologico semi-distribuito su alcuni bacini appenninici

I bacini idrografici appenninici romagnoli rappresentano una fonte idropotabile di essenziale importanza per la Romagna, grazie alla regolazione stagionale svolta dall’invaso artificiale di Ridracoli. Nel presente elaborato si è implementato un modello per lo studio e la valutazione del regime idrologico dei bacini idrografici allacciati all’invaso, affrontando sia gli aspetti relativi alla miglior spazializzazione dei dati metereologici in ingresso al modello (in particolare in relazione alla stima della temperatura, fondamentale per la rappresentazione dei processi di evapotraspirazione e dei fenomeni di accumulo e scioglimento nevoso), sia gli aspetti di calibrazione dei parametri, confrontando le simulazioni ottenute a partire da diverse configurazioni del modello in termini di rappresentazione spaziale e temporale dei fenomeni. Inoltre si è eseguita una regionalizzazione del modello su due sezioni fluviali che sono al momento oggetto di indagini idrologiche, fornendo supporto alla valutazione della possibilità di realizzazione di una nuova opera di presa. A partire dai dati puntuali dei sensori termometrici disponibili si è ricercata la migliore tecnica di interpolazione della temperatura sull’area di studio, ottenendo una discreta precisione, con un errore in procedura di ricampionamento jack-knife raramente superiore al grado centigrado. La calibrazione del modello TUWien in approccio semi-distribuito, sia quando applicato a scala oraria sia quando applicato a scala giornaliera, ha portato a buoni risultati. La complessità del modello, dovuta in gran parte alla presenza di uno specifico modulo per la gestione di accumulo e scioglimento nivale, è stata ripagata dalle buone prestazioni delle simulazioni ottenute, sia sul periodo di calibrazione sia su quello di validazione. Tuttavia si è osservato che l’approccio semi-distribuito non ha portato benefici sostanziali rispetto a quello concentrato, soprattutto in relazione al forte aumento di costo computazionale.

Analisi del sistema idraulico e di monitoraggio dei Consorzi dei canali di Reno e Savena e caratterizzazione degli eventi storici di siccita meteorologica ed idrologica del Fiume Reno a Casalecchio

La tesi è suddivisa in tre parti. Nella prima parte si descrive il sistema dei canali bolognesi che derivano acqua dal bacino montano del Fiume Reno e dal Torrente Savena, e il sistema di gestione e di monitoraggio utilizzato dal Consorzio dei canali di Reno e Savena. Nella seconda parte si illustra una proposta di sistema di visualizzazione dei dati idro-pluviometrici che si sta valutando, assieme al Presidente del Consorzio e ad Arpa, per il monitor che il Consorzio intende installare al fine di illustrare al pubblico il monitoraggio e l’evoluzione degli eventi di piena e di scarsità idrica/siccità. Nella terza parte, infine, si effettuano la stima e un’analisi della correlazione tra due diversi indici di siccità, meteorologica ed idrologica, per il bacino del Reno chiuso a Casalecchio. Il sistema dell’intero bacino del Reno e della rete dei canali cittadini risulta molto complesso. Vista tale complessità del sistema, si è proposto di distinguere uno scenario di piena e uno scenario di magra. Tra le diverse informazioni da visualizzare nel monitor si intendono anche visualizzare informazioni relative alla disponibilità idrica alla scala del bacino in esame. Per questo è stata svolta l’analisi sugli indici di siccità Standard Precipitation Index (SPI) e Streamflow Drought Index per il bacino del Reno chiuso a Casalecchio . Tali indici hanno portato a dei risultati consistenti con le condizioni idro-metereologiche e con le informazioni sugli impatti al suolo disponibili per alcuni degli eventi più significativi presi in esame. In base ai risultati ottenuti è possibile affermare che gli indici SPI e SDI a scala di bacino hanno una buona correlazione che permette di poter considerare anche la sola caratterizzazione pluviometrica per identificare la situazione della disponibilità idrica del fiume a monte dell’opera di presa del Canale di Reno.

Accurate relative pKa calculations for carboxylic acids using complete basis set and Gaussian-n models combined with continuum solvation methods

The complete basis set methods CBS-4, CBS-QB3, and CBS-APNO, and the Gaussian methods G2 and G3 were used to calculate the gas phase energy differences between six different carboxylic acids and their respective anions. Two different continuum methods, SM5.42R and CPCM, were used to calculate the free energy differences of solvation for the acids and their anions. Relative pKa values were calculated for each acid using one of the acids as a reference point. The CBS-QB3 and CBS-APNO gas phase calculations, combined with the CPCM/HF/6-31+G(d)//HF/6-31G(d) or CPCM/HF/6-31+G(d)//HF/6-31+G(d) continuum solvation calculations on the lowest energy gas phase conformer, and with the conformationally averaged values, give results accurate to ½ pKa unit. © 2001 American Institute of Physics.

Equivariant inverse spectral theory and toric orbifolds

Let O-2n be a symplectic toric orbifold with a fixed T-n-action and with a tonic Kahler metric g. In [10] we explored whether, when O is a manifold, the equivariant spectrum of the Laplace Delta(g) operator on C-infinity(O) determines O up to symplectomorphism. In the setting of tonic orbifolds we shmilicantly improve upon our previous results and show that a generic tone orbifold is determined by its equivariant spectrum, up to two possibilities. This involves developing the asymptotic expansion of the heat trace on an orbifold in the presence of an isometry. We also show that the equivariant spectrum determines whether the toric Kahler metric has constant scalar curvature. (C) 2012 Elsevier Inc. All rights reserved.

Hearing Delzant Polytopes From the Equivariant Spectrum

Let M^{2n} be a symplectic toric manifold with a fixed T^n-action and with a toric K\"ahler metric g. Abreu asked whether the spectrum of the Laplace operator $\Delta_g$ on $\mathcal{C}^\infty(M)$ determines the moment polytope of M, and hence by Delzant's theorem determines M up to symplectomorphism. We report on some progress made on an equivariant version of this conjecture. If the moment polygon of M^4 is generic and does not have too many pairs of parallel sides, the so-called equivariant spectrum of M and the spectrum of its associated real manifold M_R determine its polygon, up to translation and a small number of choices. For M of arbitrary even dimension and with integer cohomology class, the equivariant spectrum of the Laplacian acting on sections of a naturally associated line bundle determines the moment polytope of M.