The cutting stock problem in the wood industry

This thesis proposes a solution for board cutting in the wood industry with the aim of usage minimization and machine productivity. The problem is dealt with as a Two-Dimensional Cutting Stock Problem and specific Combinatorial Optimization methods are used to solve it considering the features of the real problem.

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.

Referee Assignment Problem Case: Italian Volleyball Championships

This thesis addresses the formulation of a referee assignment problem for the Italian Volleyball Serie A Championships. The problem has particular constraints such as a referee must be assigned to different teams in a given period of times, and the minimal/maximal level of workload for each referee is obtained by considering cost and profit in the objective function. The problem has been solved through an exact method by using an integer linear programming formulation and a clique based decomposition for improving the computing time. Extensive computational experiments on real-world instances have been performed to determine the effectiveness of the proposed approach.

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.

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.

In vitro maturation: a five-year experience

Although some patients may benefit from reduced follicle-stimulating hormone (FSH) application, in-vitro maturation (IVM) belongs to the rare treatment options in assisted reproduction. We summarize our five-year IVM experience.