Progetto e sviluppo di un algoritmo per la pianificazione ottimizzata della distribuzione con viaggi sincronizzati

Il lavoro di tesi svolto riguarda la progettazione e lo sviluppo di un algoritmo per la pianificazione ottimizzata della distribuzione con viaggi sincronizzati; il metodo sviluppato è un algoritmo mateuristico. I metodi mateuristici nascono dall’integrazione di algoritmi esatti, utilizzati all’interno di un framework metaeuristico, scelto come paradigma di soluzione del problema. La combinazione di componenti esatte e algoritmi metaeuristici ha lo scopo di sfruttare i vantaggi di entrambi gli approcci: grazie all'uso di componenti esatte, è possibile operare in modo efficace e di concentrarsi su alcuni dei vincoli del problema, mentre, con l'utilizzo di un framework metaeuristico, si può efficacemente esplorare grandi aree dello spazio di ricerca in tempi accettabili. Il problema analizzato nel lavoro di tesi è un problema di trasporto, ovvero il Vehicle Routing Problem con finestre temporali e vincoli di sincronizzazione a coppie (VRPTWPS). Il problema richiede di individuare un piano di organizzazione ottimizzato per i viaggi di consegna merci presso un insieme di clienti; ogni cliente richiede che la consegna avvenga all’interno di orari predefiniti; un sottoinsieme di essi richiede, inoltre, che la consegna venga effettuata con la presenza di esattamente due addetti. La presenza di quest’ultimo vincolo richiede, dunque, che due incaricati, indipendentemente dai viaggi di visita che questi effettuano, si incontrino presso uno stesso cliente nello stesso istante. Il vincolo di sincronizzazione rende il problema difficile da risolvere in maniera ottimizzata con i tradizionali metodi di ricerca locale; da ciò nasce l’uso dei metodi mateuristici per la risoluzione ottimizzata del problema. Grazie all’utilizzo di algoritmi esatti, i metodi mateuristici riescono a trattare in maniera più efficace alcuni vincoli dei problemi da risolvere.

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.

Un Algoritmo di controllo ottimo di un sistema di aerodinamica mobile per una vettura sportiva

Approfondimento di tecniche di controllo ottimo per problemi di regolazione e di inseguimento di modello. Sintesi e implementazione di un algoritmo che si occupi del controllo della dinamica laterale di una vettura attraverso il sistema di aerodinamica mobile.

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.

Contributo dell'algoritmo euristico ghest nella caratterizzazione energetica di una rete di distribuzione idrica

Un sistema di distribuzione idropotabile (Water Distribution Network -WDN), data la sua complessità strutturale e funzionale, per l' ordinario esercizio richiede elevati quantitativi di energia. L'attuale trend tecnico/scientifico incoraggia la loro gestione e progettazione nell'ottica di un generale risparmio di energia che, oltre ad un indiscusso vantaggio economico, implica sopratutto una razionalizzazione dell'impiego di risorsa idrica. Questo è il contesto scientifico/culturale in cui il presente elaborato si colloca. Nello specifico, ci si propone la caratterizzazione energetica di la rete di distribuzione idrica Cabrera_network.(rivisitazione della rete presentata da E.Cabrera e M.Pardo nel loro studio del 2010) . Si sono quindi qualificati i legami tra i consumi energetici ed aspetti, quali: dimensionamento dei condotti, perdite idriche, tipologia di pompa centrifuga sfruttata e livello idrico massimo del serbatoio di compenso. Ciò è stato esplicato in due fasi di analisi. In una primo momento, si sono impiegati strumenti classi quali il simulatore idraulico Epanet2 e i fogli di calcolo Excel. In un secondo momento, il problema dell'ottimizzazione energetica della rete è stato risolto a mezzo l'algoritmo euristico GHEST. Al di là delle specifiche conclusioni, cui si rinvia, l'elaborato consente di cogliere un più generale profilo di ordine metodologico: l'importanza di una visione d'insieme del problema energetico in un sistema di distribuzione idropotabile, dalla quale, nel caso di specie, emerge che la scelta più ragionevole, al fine dell'ottimizzazione energetica, consiste nell'individuazione del più idoneo modello di pompa alimentante la rete. Per poi, data l'onere progettuale e applicativo che comporta, provvedere al reinvestimento dei capitali risparmiati in attività volte alla riduzione delle perdite idriche. Sono questi infatti, i due aspetti che più incidono sui consumi energetici nel caso di studio.

Integrazione di algoritmi di visione basati su flusso ottico per il controllo di un velivolo senza pilota

Il lavoro svolto in questa tesi si colloca nell’area della robotica aerea e della visione artificiale attraverso l’integrazione di algoritmi di visione per il controllo di un velivolo senza pilota. Questo lavoro intende dare un contributo al progetto europeo SHERPA (Smart collaboration between Humans and ground-aErial Robots for imProving rescuing activities in Alpine environments), coordinato dall’università di Bologna e con la compartecipazione delle università di Brema, Zurigo, Twente, Leuven, Linkopings, del CREATE (Consorzio di Ricerca per l’Energia e le Applicazioni Tecnologiche dell’Elettromagnetismo), di alcune piccole e medie imprese e del club alpino italiano, che consiste nel realizzare un team di robots eterogenei in grado di collaborare con l’uomo per soccorrere i dispersi nell’ambiente alpino. L’obiettivo di SHERPA consiste nel progettare e integrare l’autopilota all’interno del team. In tale contesto andranno gestiti problemi di grande complessità, come il controllo della stabilità del velivolo a fronte di incertezze dovute alla presenza di vento, l’individuazione di ostacoli presenti nella traiettoria di volo, la gestione del volo in prossimità di ostacoli, ecc. Inoltre tutte queste operazioni devono essere svolte in tempo reale. La tesi è stata svolta presso il CASY (Center for Research on Complex Automated Systems) dell’università di Bologna, utilizzando per le prove sperimentali una PX4FLOW Smart Camera. Inizialmente è stato studiato un autopilota, il PIXHAWK, sul quale è possibile interfacciare la PX4FLOW, in seguito sono stati studiati e simulati in MATLAB alcuni algoritmi di visione basati su flusso ottico. Infine è stata studiata la PX4FLOW Smart Camera, con la quale sono state svolte le prove sperimentali. La PX4FLOW viene utilizzata come interfaccia alla PIXHAWK, in modo da eseguire il controllo del velivolo con la massima efficienza. E’ composta da una telecamera per la ripresa della scena, un giroscopio per la misura della velocità angolare, e da un sonar per le misure di distanza. E’ in grado di fornire la velocità di traslazione del velivolo, e quest’ultima, integrata, consente di ricostruire la traiettoria percorsa dal velivolo.

Principi e metodi della robotica evolutiva

L’intelligenza artificiale, ovvero lo studio e la progettazione di sistemi intelligenti, mira a riprodurre alcuni aspetti dell’intelligenza umana, come il linguaggio e il ragionamento deduttivo, nei computer. La robotica, invece, cerca spesso di ricreare nei robot comportamenti adattativi, come l’abilità di manipolare oggetti o camminare, mediante l’utilizzo di algoritmi in grado di generare comportamenti desiderati. Una volta realizzato uno di questi algoritmi specificamente per una certa abilità, si auspica che tale algoritmo possa essere riutilizzato per generare comportamenti più complessi fino a che il comportamento adattativo del robot non si mostri ad un osservatore esterno come intelligente; purtroppo questo non risulta sempre possibile e talvolta per generare comportamenti di maggiore complessità è necessario riscrivere totalmente gli algoritmi. Appare quindi evidente come nel campo della robotica l’attenzione sia incentrata sul comportamento, perché le azioni di un robot generano nuove stimolazioni sensoriali, che a loro volta influiscono sulle sue azioni future. Questo tipo di intelligenza artificiale (chiamata propriamente embodied cognition) differisce da quella propriamente detta per il fatto che l’intelligenza non emerge dall’introspezione ma dalle interazioni via via più complesse che la macchina ha con l’ambiente circostante. Gli esseri viventi presenti in natura mostrano, infatti, alcuni fenomeni che non sono programmati a priori nei geni, bensì frutto dell’interazione che l’organismo ha con l’ambiente durante le varie fasi del suo sviluppo. Volendo creare una macchina che sia al contempo autonoma e adattativa, si devono affrontare due problemi: il primo è relativo alla difficoltà della progettazione di macchine autonome, il secondo agli ingenti costi di sviluppo dei robot. Alla fine degli anni ’80 nasce la robotica evolutiva che, traendo ispirazione dall’evoluzione biologica, si basa sull’utilizzo di software in grado di rappresentare popolazioni di robot virtuali e la capacità di farli evolvere all’interno di un simulatore, in grado di rappresentare le interazioni tra mente e corpo del robot e l’ambiente, per poi realizzare fisicamente solo i migliori. Si utilizzano algoritmi evolutivi per generare robot che si adattano, anche dal punto di vista della forma fisica, all’ambiente in cui sono immersi. Nel primo capitolo si tratterà di vita ed evoluzione artificiali, concetti che verranno ripresi nel secondo capitolo, dedicato alle motivazioni che hanno portato alla nascita della robotica evolutiva, agli strumenti dei quali si avvale e al rapporto che ha con la robotica tradizionale e le sue declinazioni. Nel terzo capitolo si presenteranno i tre formalismi mediante i quali si sta cercando di fornire un fondamento teorico a questa disciplina. Infine, nel quarto capitolo saranno mostrati i problemi che ancora oggi non hanno trovato soluzione e le sfide che si devono affrontare trattando di robotica evolutiva.

Approcci innovativi per future simulazioni HPC verso l'exascale computing con applicazioni alla fisica dei materiali

In questo lavoro di tesi sono state evidenziate alcune problematiche relative alle macchine exascale (sistemi che sviluppano un exaflops di Potenza di calcolo) e all'evoluzione dei software che saranno eseguiti su questi sistemi, prendendo in esame principalmente la necessità del loro sviluppo, in quanto indispensabili per lo studio di problemi scientifici e tecnologici di più grandi dimensioni, con particolare attenzione alla Material Science, che è uno dei campi che ha avuto maggiori sviluppi grazie all'utilizzo di supercomputer, ed ad uno dei codici HPC più utilizzati in questo contesto: Quantum ESPRESSO. Dal punto di vista del software sono state presentate le prime misure di efficienza energetica su architettura ibrida grazie al prototipo di cluster EURORA sul software Quantum ESPRESSO. Queste misure sono le prime ad essere state pubblicate nel contesto software per la Material Science e serviranno come baseline per future ottimizzazioni basate sull'efficienza energetica. Nelle macchine exascale infatti uno dei requisiti per l'accesso sarà la capacità di essere energeticamente efficiente, così come oggi è un requisito la scalabilità del codice. Un altro aspetto molto importante, riguardante le macchine exascale, è la riduzione del numero di comunicazioni che riduce il costo energetico dell'algoritmo parallelo, poiché in questi nuovi sistemi costerà di più, da un punto di vista energetico, spostare i dati che calcolarli. Per tale motivo in questo lavoro sono state esposte una strategia, e la relativa implementazione, per aumentare la località dei dati in uno degli algoritmi più dispendiosi, dal punto di vista computazionale, in Quantum ESPRESSO: Fast Fourier Transform (FFT). Per portare i software attuali su una macchina exascale bisogna iniziare a testare la robustezza di tali software e i loro workflow su test case che stressino al massimo le macchine attualmente a disposizione. In questa tesi per testare il flusso di lavoro di Quantum ESPRESSO e WanT, un software per calcolo di trasporto, è stato caratterizzato un sistema scientificamente rilevante costituito da un cristallo di PDI - FCN2 che viene utilizzato per la costruzione di transistor organici OFET. Infine è stato simulato un dispositivo ideale costituito da due elettrodi in oro con al centro una singola molecola organica.

Sviluppo e verifica di un framework basato su logica computazionale per la selezione dinamica di web services tramite informazioni

La presenza sempre più massiccia di fornitori di servizi basati su web service ha portato in rilievo uno dei limiti di questo approccio, l’impossibilità di rendere automatizzabili i task di ricerca, invocazione e orchestrazione dei servizi. Il raggiungimento di questo obiettivo risulta impossibile a causa della mancanza di informazioni comprensibili ad una macchina attraverso le quali un agente software può effettuare delle scelte tra vari servizi esposti. Il fallimento della “ricerca intelligente” di un servizio pubblicato sta nella stessa modellazione dei servizi. I linguaggi attualmente disponibili permettono di modellare un servizio solo dal punto di vista sintattico. Definire le operazioni proposte, il tipo di parametri accettati e il tipo di output prodotto non è sufficiente a comprendere cosa il servizio può fare. I web services semantici consentono di superare questo limite fornendo uno stack semantico, il quale ha il compito di racchiudere le informazioni relative ai servizi, il loro funzionamento e gli obiettivi raggiungibili organizzando la conoscenza in ontologie. La formalizzazione dei modelli ontologici e la loro integrazione con i servizi esistenti è uno dei problemi più interessanti che ha catturato l’attenzione di numerosi studi di settore. Negli ultimi anni numerose sono state le soluzioni proposte. Tra queste si possono considerare due principali vie di sviluppo che hanno visto un’intensa attività sperimentale. Il primo scenario è volto a modellare in maniera formale la conoscenza legata ai servizi esposti, il secondo integra i servizi già esistenti con nuove strutture semantiche in modo da conservare le infrastrutture presenti. Entrambi i filoni hanno come scopo quello di fornire la conoscenza adatta a sistemi esperti che consentano di automatizzare la ricerca dei servizi in base ai desideri dei clienti, permettendo la loro composizione dinamica basata su un’interazione utile e indipendente dai protocolli che vincolano il trasporto delle informazioni.

Implementazione dell'algoritmo filtered back-projection (FBP) per architetture low-power di tipo systems-on-chip

Il presente lavoro di tesi, svolto presso i laboratori dell'X-ray Imaging Group del Dipartimento di Fisica e Astronomia dell'Università di Bologna e all'interno del progetto della V Commissione Scientifica Nazionale dell'INFN, COSA (Computing on SoC Architectures), ha come obiettivo il porting e l’analisi di un codice di ricostruzione tomografica su architetture GPU installate su System-On-Chip low-power, al fine di sviluppare un metodo portatile, economico e relativamente veloce. Dall'analisi computazionale sono state sviluppate tre diverse versioni del porting in CUDA C: nella prima ci si è limitati a trasporre la parte più onerosa del calcolo sulla scheda grafica, nella seconda si sfrutta la velocità del calcolo matriciale propria del coprocessore (facendo coincidere ogni pixel con una singola unità di calcolo parallelo), mentre la terza è un miglioramento della precedente versione ottimizzata ulteriormente. La terza versione è quella definitiva scelta perché è la più performante sia dal punto di vista del tempo di ricostruzione della singola slice sia a livello di risparmio energetico. Il porting sviluppato è stato confrontato con altre due parallelizzazioni in OpenMP ed MPI. Si è studiato quindi, sia su cluster HPC, sia su cluster SoC low-power (utilizzando in particolare la scheda quad-core Tegra K1), l’efficienza di ogni paradigma in funzione della velocità di calcolo e dell’energia impiegata. La soluzione da noi proposta prevede la combinazione del porting in OpenMP e di quello in CUDA C. Tre core CPU vengono riservati per l'esecuzione del codice in OpenMP, il quarto per gestire la GPU usando il porting in CUDA C. Questa doppia parallelizzazione ha la massima efficienza in funzione della potenza e dell’energia, mentre il cluster HPC ha la massima efficienza in velocità di calcolo. Il metodo proposto quindi permetterebbe di sfruttare quasi completamente le potenzialità della CPU e GPU con un costo molto contenuto. Una possibile ottimizzazione futura potrebbe prevedere la ricostruzione di due slice contemporaneamente sulla GPU, raddoppiando circa la velocità totale e sfruttando al meglio l’hardware. Questo studio ha dato risultati molto soddisfacenti, infatti, è possibile con solo tre schede TK1 eguagliare e forse a superare, in seguito, la potenza di calcolo di un server tradizionale con il vantaggio aggiunto di avere un sistema portatile, a basso consumo e costo. Questa ricerca si va a porre nell’ambito del computing come uno tra i primi studi effettivi su architetture SoC low-power e sul loro impiego in ambito scientifico, con risultati molto promettenti.

Analisi del moto di particelle in sospensione mediante simulazioni di fluidodinamica computazionale

La mobilitazione di polveri radioattive nel caso di un incidente di perdita di vuoto (LOVA) all’interno di ITER (International Thermonuclear Experimental Reactor), è uno dei problemi di sicurezza che si sono posti durante la costruzione di tale reattore. Le polveri vengono generate dalla continua erosione da parte del plasma del materiale di contenimento. Ciò porta ad un accumulo delle stesse all’interno della camera di vuoto. Nel caso di un incidente LOVA il rilascio di tali polveri in atmosfera rappresenta un rischio per la salute di lavoratori e della popolazione circostante. Per raccogliere dati su tale tipo di incidente è stata costruita presso il laboratorio dell’università di Tor Vergata una piccola facility, STARDUST, in cui sono stati eseguiti vari esperimenti con delle condizioni iniziali simili a quelle presenti all’interno di ITER. Uno di questi esperimenti in particolare simula la rottura della camera di vuoto mediante l’ingresso di aria in STARDUST, inizialmente posto a 100 Pa, con un rateo di pressurizzazione di 300 Pa s−1. All’interno del serbatoio sono presenti delle polveri che, in differente percentuale, vengono portate in sospensione dal flusso di fluido entrante. In particolare le polveri sono composte da tungsteno (W), acciaio inossidabile (SS – 316 ) e carbonio ( C ). Scopo del presente lavoro è quello di riprodurre il campo di velocità che si genera all’interno di STARDUST nel caso dell’esperimento appena descritto e valutare il moto delle particelle portate in sospensione e la loro successiva deposizione. Ciò viene fatto mediante l’utilizzo di una geometria bidimensionale creata con Salome. Su tale geometria sono costruite differenti mesh strutturate in base al tipo di simulazione che si vuole implementare. Quest’ultima viene poi esportata nel solutore utilizzato, Code_Saturne. Le simulazioni eseguite possono essere suddivise in tre categorie principali. Nella prima (Mesh A) si è cercato di riprodurre i risultati numerici presentati dagli autori della parte sperimentale, che hanno utilizzato il software commerciale Fluent. Nella seconda si è riprodotto il campo di velocità interno a STARUDST sulla base dei dati sperimentali in possesso. Infine nell’ultima parte delle simulazioni si è riprodotto il moto delle particelle sospese all’interno del fluido in STARDUST, valutandone la deposizione. Il moto del fluido pressurizzante è stato considerato come compressibile. Il regime di moto è stato considerato turbolento viste le elevate velocità che provocavano elevati valori del numero di Reynolds per l’aria. I modelli con cui si è trattata la turbolenza sono stati di tre tipi. Il campo di velocità ottenuto è stato leggermente differente nei tre casi e si è proceduto ad un confronto per valutare le cause che hanno portato a tali differenze. Il moto delle particelle è stato trattato mediante l’utilizzo del modello di tracciamento lagrangiano delle particelle implementato in Code_Saturne. Differenti simulazioni sono state eseguite per tenere in considerazione i vari modelli di turbolenza adottati. Si è dunque proceduto ad analizzare similitudini e differenze dei risultati ottenuti.

L'algoritmo bionomico per il Traveling Salesman Problem

In questa tesi viene presentato un nuovo metaeuristico per la risoluzione del Traveling Salesman Problem (TSP) simmetrico. Tale metodo, detto algoritmo bionomico, è una variante dell'algoritmo genetico che usa un metodo innovativo di generazione del parents set. Nella tesi vengono proposti diversi metodi di crossover specifici per il TSP ma che possono essere facilmente estesi per altri problemi di ottimizzazione combinatoria. Tali metodi sono stati sperimentati su un insieme di problemi test, i risultati computazionali mostrano l'efficienza dei metodi proposti. In particolare uno dei metodi domina gli altri sia per la miglior qualità delle soluzioni prodotte che per il minor tempo di calcolo impiegato.

Studio di un algoritmo di controllo di temperatura per ganasce termosigillanti in macchine per packaging

Gli obiettivi dell'elaborato sono lo studio e la programmazione di un algoritmo di controllo di temperatura per le superfici termosaldanti di macchine per il packaging (confezionatrici in film a file multiple) prodotte dal committente, OMAG srl. L'algoritmo è implementato tramite il software SoMachineMotion v.4.2, prodotto da Schneider Electrics spa. Il controllo è di tipo in anello chiuso in retroazione, con temocoppie e resistenze di riscaldamento con modulazione PWM. Ci si è inizialmente occupati di testare su banco prova varie tipologie di regolatori: a relay, a isteresi, a ricerca diretta del duty cycle, TBH, con approccio misto TBH/integratore di Clegg, PID. I diversi metodi di regolazione sono stati valutati sulla base di una serie di metri di giudizio (precisione dell'inseguimento, prestazioni statiche e dinamiche, flessibilità, peso computazionale, facilità implementativa), pesati secondo i requisiti imposti dal committente. Le metodologie selezionate sono state PID e TBH/Clegg integrator; quest'ultima ha dato risultati assai soddisfacenti, pur essendo un metodo monoparametrico. Si sono quindi studiate diverse modalità per la taratura del regolatore PID, in particolare: tuning in anello chiuso con metodo a relay per la fase di pretuning, algoritmo di Nelder-Mead, per la ricerca diretta continua dei valori che minimizzano l'errore integrale, per un selftuning adattivo. Si è infine proceduto ad implementare le soluzioni individuate in un software robusto, che rispetti gli standard del settore e si sono inoltre sviluppate una serie di funzionalità aggiuntive, quali: modulazione software PWM, preriscaldamento, handling errori/warning, filtraggio segnali in/out. Si è addizionalmente sviluppato un modello matematico predittivo dell'evoluzione del sistema, che potrebbe servire, in un futuro sviluppo, come base per un controllo model-based in cascata al controllo in retroazione studiato.

Entre la epistemología y la lógica. Decisión y algoritmo de ordenación

[ES] Este trabajo en homenaje al Profesor Emilio Soldevilla trata de plantear algunos elementos de la matemática combinatoria, escogidos sin otro criterio que el de ser fácilmente visualizados para poner en evidencia el aspecto altamente significativo que poseen para la construcción de una epistemología de la economía y gestión de empresas. Y todo ello en torno a uno de los conceptos más destacados de este ámbito del conocimiento cual es el de decisión.

Algoritmo urza para el análisis de sensibilidad en problemas de programación lineal

Este artículo menciona que el algoritmo pretende llenar un hueco existente en los análisis de sensibilidad de la Programación Lineal. Estos análisis abarcan tradicionalmente a todos los coeficientes del sistema excepto a los coeficientes técnicos de las variables de la BASE, debido a la dificultad de calcular la inversa de ésta cuando se ha introducido un parámetro en uno de sus elementos.