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.

Vendemmia meccanica: aspettative, problematiche e risposte sperimentali

Lo vendemmia meccanica incontra ancora resistenze legate al timore di peggiorare la qualità del prodotto e di avere elevate perdite di raccolta. In questo contesto sono state effettuate quattro prove sperimentali, finalizzate a definire le interazioni macchina, pianta e prodotto raccolto e a valutare nuove possibilità di regolazione delle vendemmiatrici e di gestione del prodotto raccolto. Le prime due sono state realizzate con vendemmiatrici a scuotimento orizzontale e verticale. L’obiettivo è stato quello di individuare l’influenza della frequenza del battitore sull’efficienza di raccolta e sulla qualità del prodotto e di verificare il maltrattamento provocato dagli organi di intercettazione e trasporto della vendemmiatrice. I risultati hanno dimostrato l’importanza della corretta regolazione del battitore delle vendemmiatrici a scuotimento orizzontale che operano direttamente sulla fascia produttiva del vigneto. Questa regolazione risulta più semplice sulle macchine a scuotimento verticale che agiscono indirettamente sui fili di sostegno delle doppie cortine. La misura delle sollecitazioni all’interno della macchina ha evidenziato valori anche elevati, pericolosi per l’integrità del prodotto raccolto, legati alla differente costruzione degli organi d’intercettazione e trasporto. La terza prova ha valutato l’efficacia di due nuovi accessori per le vendemmiatrici: la regolazione dell’ampiezza del battitore e un sensore per misurare in continuo il grado di ammostamento provocato. I risultati hanno dimostrato la loro validità per migliorare le prestazioni operative delle vendemmiatrici e per fornire agli operatori uno strumento di controllo in tempo reale sulla qualità della raccolta. Infine, considerando che le vendemmiatrici producono sempre un ammostamento dell’uva, abbiamo verificato un sistema innovativo che permette di anticipare la protezione del mosto libero già durante il trasporto dal campo. Il sistema si è dimostrato semplice, efficace ed economico. Queste esperienze hanno dimostrano che la vendemmia meccanica, se correttamente gestita, permette di ottenere ottimi risultati sotto il profilo qualitativo, tecnologico ed economico.

Effetti di intaglio in accoppiamenti albero-mozzo per interferenza

L’obiettivo dello studio è quello di determinare le cause della rottura a fatica in un accoppiamento albero–mozzo. Nella prima parte si cerca di costruire un modello FEM (attraverso Ansys Workbench 12.0) che simuli il comportamento del provino albero-mozzo sottoposto a una flessione alterna, come nella macchina di Moore. Con esso si cercherà di individuare le variabili del problema e quali potranno influenzare la σy_max e il Kt. Nella seconda parte si cercherà di stabilire se il fretting sia funzione dalle stesse variabili del Kt, se esiste una transizione tra i due fenomeni e la quantità di usura prodotta dal fretting. Infine si realizzeranno delle prove sperimentali per verificare le ipotesi dedotte dall'analisi FEM.

Nonlinear Control Strategies for Cooperative Control of Multi-Robot Systems

This thesis deals with distributed control strategies for cooperative control of multi-robot systems. Specifically, distributed coordination strategies are presented for groups of mobile robots. The formation control problem is initially solved exploiting artificial potential fields. The purpose of the presented formation control algorithm is to drive a group of mobile robots to create a completely arbitrarily shaped formation. Robots are initially controlled to create a regular polygon formation. A bijective coordinate transformation is then exploited to extend the scope of this strategy, to obtain arbitrarily shaped formations. For this purpose, artificial potential fields are specifically designed, and robots are driven to follow their negative gradient. Artificial potential fields are then subsequently exploited to solve the coordinated path tracking problem, thus making the robots autonomously spread along predefined paths, and move along them in a coordinated way. Formation control problem is then solved exploiting a consensus based approach. Specifically, weighted graphs are used both to define the desired formation, and to implement collision avoidance. As expected for consensus based algorithms, this control strategy is experimentally shown to be robust to the presence of communication delays. The global connectivity maintenance issue is then considered. Specifically, an estimation procedure is introduced to allow each agent to compute its own estimate of the algebraic connectivity of the communication graph, in a distributed manner. This estimate is then exploited to develop a gradient based control strategy that ensures that the communication graph remains connected, as the system evolves. The proposed control strategy is developed initially for single-integrator kinematic agents, and is then extended to Lagrangian dynamical systems.

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.

Progettazione e sviluppo di una versione distribuita di un algoritmo di subspace clustering

Il task del data mining si pone come obiettivo l'estrazione automatica di schemi significativi da grandi quantità di dati. Un esempio di schemi che possono essere cercati sono raggruppamenti significativi dei dati, si parla in questo caso di clustering. Gli algoritmi di clustering tradizionali mostrano grossi limiti in caso di dataset ad alta dimensionalità, composti cioè da oggetti descritti da un numero consistente di attributi. Di fronte a queste tipologie di dataset è necessario quindi adottare una diversa metodologia di analisi: il subspace clustering. Il subspace clustering consiste nella visita del reticolo di tutti i possibili sottospazi alla ricerca di gruppi signicativi (cluster). Una ricerca di questo tipo è un'operazione particolarmente costosa dal punto di vista computazionale. Diverse ottimizzazioni sono state proposte al fine di rendere gli algoritmi di subspace clustering più efficienti. In questo lavoro di tesi si è affrontato il problema da un punto di vista diverso: l'utilizzo della parallelizzazione al fine di ridurre il costo computazionale di un algoritmo di subspace clustering.

Controllo Vettoriale generalizzato per Macchine Elettriche Trifase

Nell’ambito della presente tesi verrà descritto un approccio generalizzato per il controllo delle macchine elettriche trifasi; la prima parte è incentrata nello sviluppo di una metodologia di modellizzazione generale, ossia in grado di descrivere, da un punto di vista matematico, il comportamento di una generica macchina elettrica, che possa quindi includere in sé stessa tutte le caratteristiche salienti che possano caratterizzare ogni specifica tipologia di macchina elettrica. Il passo successivo è quello di realizzare un algoritmo di controllo per macchine elettriche che si poggi sulla teoria generalizzata e che utilizzi per il proprio funzionamento quelle grandezze offerte dal modello unico delle macchine elettriche. La tipologia di controllo che è stata utilizzata è quella che comunemente viene definita come controllo ad orientamento di campo (FOC), per la quale sono stati individuati degli accorgimenti atti a migliorarne le prestazioni dinamiche e di controllo della coppia erogata. Per concludere verrà presentata una serie di prove sperimentali con lo scopo di mettere in risalto alcuni aspetti cruciali nel controllo delle macchine elettriche mediante un algoritmo ad orientamento di campo e soprattutto di verificare l’attendibilità dell’approccio generalizzato alle macchine elettriche trifasi. I risultati sperimentali confermano quindi l’applicabilità del metodo a diverse tipologie di macchine (asincrone e sincrone) e sono stati verificate nelle condizioni operative più critiche: bassa velocità, alta velocità bassi carichi, dinamica lenta e dinamica veloce.

Studio di classi di sferoidi multicellulari di carcinoma polmonare epidermoidale in radiobiologia

Il tumore del polmone rappresenta la prima causa di morte nei paesi industrializzati. Le possibilità di trapianto ed intervento chirurgico risultano molto limitate pertanto lo standard di cura risulta essere la radioterapia, a volte abbinata alla chemioterapia. Sebbene trattando radioterapicamente il tumore si ottengano ottimi risultati, attualmente non esistono solide linee guida per la personalizzazione del trattamento al paziente. Il poter eseguire in laboratorio test radioterapici su un elevato numero di campioni risulterebbe un valido approccio sperimentale d’indagine, ma la carenza di materiale su cui poter condurre gli esperimenti limita questa possibilità. Tipicamente, per ovviare al problema vengono utilizzati sferoidi multicellulari tridimensionali creati in laboratorio partendo da singole cellule del tumore in esame. In particolare, l’efficacia del trattamento viene tipicamente correlata alla riduzione volumetrica media stimata utilizzando un set di sferoidi teoricamente identici. In questo studio vengono messe in discussione la validità delle affermazioni tipicamente sostenute attraverso l’analisi di volumi medi. Abbiamo utilizzando un set di circa 100 sferoidi creati in laboratorio partendo da singole cellule di carcinoma epidermoidale polmonare e trattati secondo sette differenti modalità di trattamento radioterapico (variando intensità di radiazione e numero di frazioni). In una prima fase abbiamo analizzato le singole immagini, acquisite al microscopio ottico circa ogni 48 ore, per identificare features morfometriche significative da affiancare all’analisi volumetrica. Sulla base dell’andamento temporale di queste features abbiamo suddiviso gli sferoidi in sottoclassi con evoluzioni completamente differenti che fanno supporre un differente “stato” biologico. Attraverso algoritmi di estrazione di features e classificazione e analizzando riduzione volumetrica, grado di frastagliatura del bordo e quantità di cellule liberate nel terreno di coltura abbiamo definito un protocollo per identificare in maniera automatica le sottopopolazioni di sferoidi. Infine, abbiamo ricercato con successo alcune features morfometriche in grado di predire, semplicemente analizzando immagini acquisite nei giorni seguenti all’ultimo trattamento, lo “stato di salute” del tumore a medio/lungo periodo. Gli algoritmi realizzati e le features identificate se opportunamente validate potrebbero risultare un importante strumento non invasivo di ausilio per il radioterapista per valutare nel breve periodo gli effetti a lungo periodo del trattamento e quindi poter modificare parametri di cura al fine di raggiungere uno stato desiderato del tumore.

I drammi per musica di Giacomo Antonio Perti per il teatro della Villa medicea di Pratolino (1700-01; 1707-10)

L’attività nel teatro della Villa medicea di Pratolino, presso Firenze, giunse al culmine nel primo decennio del ’700, quando il principe Ferdinando de’ Medici commissionò e vi fece rappresentare, una per anno, opere in musica di Alessandro Scarlatti e di Giacomo Antonio Perti. Benché le partiture siano perdute, sopravvive un’ingente quantità di materiale documentario, in massima parte inedito, il quale dà un eccezionale resoconto sul mecenatismo del Principe e sul funzionamento della macchina teatrale. La dissertazione si concentra sulle sei opere poste in musica da Perti ("Lucio Vero", 1700, in collaborazione con Martino Bitti; "Astianatte", 1701; "Dionisio re di Portogallo", 1707; "Ginevra principessa di Scozia", 1708; "Berenice regina d’Egitto", 1709; "Rodelinda regina de’ Longobardi", 1710), sui rapporti del compositore col Principe, col librettista Antonio Salvi, col rivale Scarlatti, coi cantanti e con la corte medicea, sullo stile da lui perseguito e – per quanto è dato sapere o lecito ipotizzare – sulla fisionomia dei suoi lavori (strutture e risorse letterarie, teatrali e musicali).

Systematic investigation of automated plan generation for breast cancer including beam angle and isocenter selection

Il tumore al seno è il più comune tra le donne nel mondo. La radioterapia è comunemente usata dopo la chirurgia per distruggere eventuali cellule maligne rimaste nel volume del seno. Nei trattamenti di radioterapia bisogna cercare di irradiare il volume da curare limitando contemporaneamente la tossicità nei tessuti sani. In clinica i parametri che definiscono il piano di trattamento radioterapeutico sono selezionati manualmente utilizzando un software di simulazione per trattamenti. Questo processo, detto di trial and error, in cui i differenti parametri vengono modificati e il trattamento viene simulato nuovamente e valutato, può richiedere molte iterazioni rendendolo dispendioso in termini di tempo. Lo studio presentato in questa tesi si concentra sulla generazione automatica di piani di trattamento per irradiare l'intero volume del seno utilizzando due fasci approssimativamente opposti e tangenti al paziente. In particolare ci siamo concentrati sulla selezione delle direzioni dei fasci e la posizione dell'isocentro. A questo scopo, è stato investigata l'efficacia di un approccio combinatorio, nel quale sono stati generati un elevato numero di possibili piani di trattamento utilizzando differenti combinazioni delle direzioni dei due fasci. L'intensità del profilo dei fasci viene ottimizzata automaticamente da un algoritmo, chiamato iCycle, sviluppato nel ospedale Erasmus MC di Rotterdam. Inizialmente tra tutti i possibili piani di trattamento generati solo un sottogruppo viene selezionato, avente buone caratteristiche per quel che riguarda l'irraggiamento del volume del seno malato. Dopo di che i piani che mostrano caratteristiche ottimali per la salvaguardia degli organi a rischio (cuore, polmoni e seno controlaterale) vengono considerati. Questi piani di trattamento sono matematicamente equivalenti quindi per selezionare tra questi il piano migliore è stata utilizzata una somma pesata dove i pesi sono stati regolati per ottenere in media piani che abbiano caratteristiche simili ai piani di trattamento approvati in clinica. Questo metodo in confronto al processo manuale oltre a ridurre considerevol-mente il tempo di generazione di un piano di trattamento garantisce anche i piani selezionati abbiano caratteristiche ottimali nel preservare gli organi a rischio. Inizialmente è stato utilizzato l'isocentro scelto in clinica dal tecnico. Nella parte finale dello studio l'importanza dell'isocentro è stata valutata; ne è risultato che almeno per un sottogruppo di pazienti la posizione dell'isocentro può dare un importante contributo alla qualità del piano di trattamento e quindi potrebbe essere un ulteriore parametro da ottimizzare. 

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.

Valutazione economica e funzionale dell'applicazione di un motore asincrono e di un motore coppia ad un estrusore di materie plastiche

Il concetto di “direct drive”, cioè l’applicazione diretta del motore all’utilizzatore, in modo da eliminare elementi di connessione intermedi (riduttori, pulegge, ecc…) con il vantaggio di migliorare il rendimento, ridurre gli ingombri, semplificare l’intera struttura, ridurre la manutenzione, è applicato con sempre maggior frequenza. L’azienda Graham Packaging Company Italia s.r.l. produce macchinari industriali per la produzione di packaging plastico, i quali montano un gruppo di estrusione a monte della macchina che alimenta il gruppo di soffiaggio: si possono, quindi, intuire alcuni vantaggi derivanti dall’applicazione del “direct drive”. Nella soluzione attualmente adottata dall’azienda la vite di estrusione, che gira a velocità relativamente basse, è collegata tramite un riduttore ad un motore asincrono trifase, che ruota a velocità significativamente superiori. L’ipotesi di una soluzione differente prevederebbe l’accoppiamento della vite ad un motore coppia (torque motor) caratterizzato da una elevata coppia e giri relativamente bassi. I vantaggi di tale accoppiamento sarebbero fondamentalmente il risparmio energetico derivante dall’esclusione del riduttore dal meccanismo e la maggiore facilità di regolazione della velocità e di conseguenza anche della portata dell’estrusore. La tesi ha lo scopo di analizzare nel particolare l’attuale situazione dal punto di vista del consumo energetico delle 11 taglie di estrusori, di valutare una soluzione con motore coppia consultando diversi fornitori di motori, di comparare le due varianti dal punto di vista dell’efficienza e dei vantaggi economici.

Messa a punto di un modello analitico generale ed efficiente per la verifica strutturale dell'anello rotante di macchine cellofanatrici

Partendo da un precedente studio, realizzato su di una macchina cellofanatrice ad asse verticale, si è arrivati ad ottenere un modello analitico per la verifica strutturale dell’anello rotante di tali macchine. Si è cercato cioè, di fornire un valido strumento per il dimensionamento di anelli rotanti nelle moderne macchine cellofanatrici, aventi geometria coerente con quella presentata nelle ipotesi iniziali. Per fare ciò, si sono determinate, ove possibile, equazioni normalizzate e adimensionalizzate, che godono quindi di una più ampia validità di impiego; a partire dalle equazioni del precedente studio, che erano appunto finalizzate alla risoluzione del caso specifico preso in considerazione. Vengono presentate in questo elaborato le equazioni che descrivono la struttura precedentemente studiata ed il procedimento che si è effettuato per rendere il nuovo lavoro indipendente dalle caratteristiche delle sollecitazioni esterne e della geometria dell’anello stesso. Sono mostrate le equazioni ottenute per le varie incognite iperstatiche, per i momenti flettenti e sforzo normale normalizzati e assoluti, ed i relativi grafici. Grazie appunto ad alcuni di questi, si ottengono rapidamente, tramite l’applicazione di semplici formule, informazioni sullo stato di sollecitazione dell’anello. Sono infine presentati alcuni esempi per sottolineare la validità dei risultati ottenuti e la semplicità di utilizzo dei grafici ricavati.

Crescita e analisi strutturale di film nanoparticellari di titania

Il lavoro di questa tesi è incentrato sulla crescita e lo studio delle proprietà strutturali di sistemi nanostrutturati di titanio e ossido di titanio, prodotti mediante la tecnica della condensazione in gas inerte. Lo studio è finalizzato in particolare ad ottenere un materiale idoneo per la produzione di idrogeno tramite la foto-elettrolisi. Nel primo capitolo viene descritto a livello teorico il processo di scissione dell’acqua all’interno di celle foto-elettrochimiche, in cui viene impiegato il TiO2 (titania) come foto-anodo. Nel secondo capitolo viene introdotta la tecnica di crescita, viene descritta la macchina utilizzata illustrandone vantaggi e limitazioni. Inoltre viene fornita una descrizione teorica del tipo di crescita che avviene all’interno della camera di evaporazione. Allo scopo di comprendere meglio questi processi, vengono riportati nel capitolo 3 alcuni studi, basati su principi primi, riguardanti la stabilità di fase e le trasformazioni di fase per i tre principali polimorfi del TiO2. Nel capitolo 4 sono illustrate le tecniche impiegate per l’indagine strutturale: diffrazione e assorbimento di raggi X con relativa analisi dati, microscopia elettronica a scansione. Prima di misurare l’attività fotocatalitica dei campioni di nanoparticelle di titania, è necessario condurre delle misure di fotocorrente in una cella foto-elettrochimica, i risultati di queste analisi di tipo funzionale sono presentati nel capitolo 5. Nel capitolo 6 sono riportate le conclusioni del lavoro di tesi.

Analisi dell’influenza dei moti rigidi di una trattrice agricola sulle vibrazioni a corpo intero trasmesse all’operatore

L’esposizione degli operatori in campo agricolo alle vibrazioni trasmesse al corpo intero, produce effetti dannosi alla salute nel breve e nel lungo termine. Le vibrazioni che si generano sulle trattrici agricole hanno una elevata intensità e una bassa frequenza. Le componenti orizzontali, amplificate dalla posizione elevata della postazione di guida dall’asse di rollio, presentano maggiori criticità per quanto riguarda i sistemi di smorzamento rispetto alle componenti verticali. Queste caratteristiche rendono difficoltosa la progettazione dei sistemi dedicati alla riduzione del livello vibrazionale per questa categoria di macchine agricole. Nonostante l’installazione di diversi sistemi di smorzamento, il livello di vibrazioni a cui è sottoposto l’operatore può superare, in diverse condizioni di impiego, i livelli massimi imposti dalla legge per la salvaguardia della salute. L’obiettivo di questo lavoro è quello di valutare l’influenza dei moti rigidi di una trattrice (beccheggio, rollio e saltellamento) dotata di sospensione assale anteriore, sospensione cabina e sospensione sedile, sul livello vibrazionale trasmesso all’operatore.E’ stata pertanto strumenta una trattrice con accelerometri e inclinometri installati su telaio, cabina e sedile e utilizzata in diverse condizioni di lavoro in campo e di trasporto su strada. Dall’analisi delle prove effettuate emerge che durante il trasporto su strada è predominante l’accelerazione longitudinale, a causa dell’elevata influenza del beccheggio. La sospensione riduce notevolmente il moto rigido di beccheggio mentre l’effetto della sospensione della cabina è quello di incrementare, in ogni condizione di lavoro, il livello di accelerazione trasmesso dal telaio della macchina.