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.

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.

Progettazione e sviluppo di software di supporto alla logistica dei trasporti.

Uno dei problemi più diffusi, nell'ambito della logistica, è rappresentato dai costi di trasporto. La gestione dei flussi merci, l'approvvigionamento dei clienti, e la relativa pianifcazione della movimentazione dei veicoli, hanno incidenze notevoli sui costi di gestione aziendali, i quali vengono stimati mediamente nel 45% dei costi logistici. A ragione di questo, sono sempre di più le aziende che ricorrono all'impiego di uffici dedicati alla pianifcazione delle consegne e la gestione dei trasporti in generale. Sebbene le voci di bilancio relative al trasporto raggiungano cifre rilevanti, fno al 4% del fatturato annuo, il tema della pianifcazione viene spesso sottovalutato. Infatti la soluzione a problemi di pianifcazione e monitoraggio dei costi, è spesso demandata a procedure manuali senza supporto informatico. Nasce da qui l'esigenza di proporre uno strumento informatico che supporti gli addetti preposti alla pianifcazione, sviluppando un sistema che copra esigenze di pianifcazione dei viaggi, controllo e consuntivazione dei costi di trasporto, e monitoraggio dei mezzi in tempo reale. La proposta di Gesp srl, Geographic Information Systems, azienda italiana che opera da anni nel campo delle applicazioni software geo-spaziali, prende il nome di Nuovo Sistema Trasporti, o più semplicemente, NST. In quest'ambito prende corpo questa tesi, la quale si pone l'obiettivo di illustrare le fasi di nascita, analisi, progettazione e sviluppo di un software generico per il supporto alla logistica. Saranno così analizzati: le problematiche affrontate nella fase di defnizione, e kick-off (avvio), del progetto, il problema del routing, o Vehicle Routing Problem e le tecniche di Ricerca Operativa che vengono applicate per la sua risoluzione; le moderne metodologie di gestione e sviluppo di un software; l'architettura e le tecnologie impiegate per la distribuzione dell'applicativo.

Studio della distribuzione del segnale misurato dal rivelatore a tempo di volo (tof) di alice e di nuovi algoritmi per la sua ottimizzazione

Questa tesi si propone di investigare l'origine di effetti non gaussiani nella distribuzione del segnale del rivelatore Time of Flight (TOF) dell'esperimento A Large Ion Collider Experiment (ALICE). Con la presa dati iniziata nel 2009 si è infatti osservata un'asimmetria nel segnale la cui origine è ancora oggetto di studio. L'analisi svolta mostra come essa sia dovuta a motivi strumentali piuttosto che fenomenologici e permette quindi di correggere in parte questa anomalia migliorando la risoluzione del rivelatore. ALICE è uno dei quattro esperimenti allestiti lungo l'anello del LHC e ha come obiettivo principale verificare l'esistenza di prove sperimentali che confermino l'esistenza di un nuovo stadio della materia, il cosiddetto Quark Gluon Plasma (QGP). Secondo la Cromodinamica Quantistica (QCD), la teoria che descrive l'interazione forte, caratteristica fondamentale di quark e gluoni è il loro confinamento all'interno di adroni. Studi recenti nell'ambito della QCD non-perturbativa hanno tuttavia dimostrato che in condizioni estreme di densità di materia adronica e temperatura sarebbe possibile un'inversione di tendenza nell'andamento della costante di accoppiamento forte. Le condizioni necessarie alla formazione del QGP sono ben riproducibili nelle collisioni ad energie ultrarelativistiche tra ioni pesanti, come quelle che sono state prodotte a LHC negli ultimi due anni, fra ioni di piombo con energie del centro di massa pari a 2.76 TeV per coppia di nucleoni. L'esperimento ALICE si propone di studiarne i prodotti e poiché la molteplicità di particelle che si generano nell'urto e considerevole, e necessario un sistema di rivelazione che permetta l'identificazione di particelle cariche su un grande angolo solido e in un ampio intervallo di impulsi. Il TOF, utilizzando un particolare rivelatore a gas detto Multigap Resistive Plate Chamber (MRPC), svolge brillantemente questo compito permettendo di raggiungere una risoluzione temporale inferiore ai 100 ps.

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.

Sviluppo e ottimizzazione di algoritmi per predire la risposta alla terapia di resincronizzazione cardiaca

La necessità di indagine sul fronte dell’insufficienza cardiaca deriva dall’elevato impatto sociale della patologia, non soltanto per l’effetto invalidante sulla condizione del paziente che ne è affetto, bensì anche per la notevole incidenza sui servizi sanitari nazionali, per l’importante valore di mortalità e morbilità che ne è associato. Il numero di ospedalizzazioni per scompenso cardiaco è consistente; ciò rende ragione dell’elevato assorbimento di risorse dovuto a questa patologia. Il razionale dell’impiego della Terapia di Resincronizzazione Cardiaca (CRT) consiste nella correzione della dissincronia cardiaca come causa di disfunzione meccanica atriale e ventricolare. Il metodo analitico sviluppato origina dalle indagini sugli spostamenti dell’elettrocatetere posizionato in Seno Coronarico, sulla base del fatto che il sito di stimolazione risulta un fattore determinante per la buona risposta alla terapia. Dovendo studiare le posizioni nel tempo del catetere, si è pensato di valutarne le variazioni nel periodo pre e post attivazione della CRT ricostruendone la traiettoria in 3D. Lo studio parametrico di quest’ultima ha permesso di individuare un indice predittore della risposta alla CRT al follow-up a sei mesi. La prosecuzione della ricerca presentata ha l’intento di migliorare gli algoritmi di elaborazione dei dati per rendere più robuste le misure, sfruttando tecniche che possano aumentare riproducibilità, ripetibilità, e ininfluenza rispetto alla variabilità delle condizioni analitiche. Sviluppando nuovi modelli si è eliminata l'interazione dell'operatore nelle fasi d'indagine, rendendo le analisi completamente automatiche. I metodi sono stati testati e applicati.

Ottimizzazione di strutture reticolari mediante algoritmi genetici

La tesi tratta dell'ottimizzazione di alcune tipologie di strutture reticolari. Per sviluppare i problemi analizzati ci si è avvalsi del software Grasshopper, conducendo poi l'ottimizzazione mediante un algoritmo genetico.

Algoritmi di ottimizzazione per il bus touring problem.

Nel campo della Ricerca Operativa e dei problemi di ottimizzazione viene presentato un problema, denominato Bus Touring Problem (BTP), che modella una problematica riguardante il carico e l’instradamento di veicoli nella presenza di di vincoli temporali e topologici sui percorsi. Nel BTP, ci si pone il problema di stabilire una serie di rotte per la visita di punti di interesse dislocati geograficamente da parte di un insieme di comitive turistiche, ciascuna delle quali stabilisce preferenze riguardo le visite. Per gli spostamenti sono disponibili un numero limitato di mezzi di trasporto, in generale eterogenei, e di capacitá limitata. Le visite devono essere effettuate rispettando finestre temporali che indicano i periodi di apertura dei punti di interesse; per questi, inoltre, é specificato un numero massimo di visite ammesse. L’obiettivo é di organizzare il carico dei mezzi di trasporto e le rotte intraprese in modo da massimizzare la soddisfazione complessiva dei gruppi di turisti nel rispetto dei vincoli imposti. Viene presentato un algoritmo euristico basato su Tabu Search appositamente ideato e progettato per la risoluzione del BTP. Vengono presentati gli esperimenti effettuati riguardo la messa appunto dei parametri dell'algoritmo su un insieme di problemi di benchmark. Vengono presentati risultati estesi riguardo le soluzioni dei problemi. Infine, vengono presentate considerazioni ed indicazioni di sviluppo futuro in materia.

Ottimizzazione stocastica di una microrete con tecnologia "vehicle-to-grid"

La presente tesi ha come obiettivo quello di sviluppare un modello per la gestione ottimizzata delle unità di generazione e di accumulo di una microrete elettrica. La tesi analizza, come caso studio di riferimento, una microrete contenente impianti di generazione da fonti rinnovabili, sistemi di accumulo a batteria (BES:Battery Energy System) e stazioni di ricarica per veicoli elettrici. In particolare le stazioni di ricarica sono a flusso bidirezionale, in grado di fornire servizi di tipo "grid-to-vehicle"(G2V) e "vehicle-to-grid" (V2G). Il modello consente di definire, come sistema di dispacciamento centrale, le potenze che le varie risorse distribuite devono erogare o assorbire nella rete nelle 24 ore successive. Il dispacciamento avviene mediante risoluzione di un problema di minimizzazione dei costi operativi e dell'energia prelevata dalla rete esterna. Il problema è stato formulato tramite l'approccio di programmazione stocastica lineare dove i parametri incerti del modello sono modellizzati tramite processi stocastici. L'implementazione del modello è stata effettuata tramite il software AIMMS, un programma di ottimizzazione che prevede al suo interno delle funzionalità specifiche per la programmazione stocastica

Detezione dei parametri temporali tramite sensori inerziali nello sprint: ottimizzazione e confronto di algoritmi proposti in letteratura per la corsa

In questo studio sono stati analizzati ed ottimizzati alcuni algoritmi proposti in letteratura per la detezione dei parametri temporali della corsa, con l'obiettivo di determinare quale, fra quelli proposti, sia il più affidabile per il suo utilizzo nell'analisi dello sprint. Per fare ciò, sono state condotte delle acquisizioni outdoor su cinque atleti differenti, utilizzando tre sensori inerziali IMU EXL-s3 (EXEL S.r.l., Bologna) con frequenza di acquisizione a 200 Hz, posizionati sul dorso dei due piedi e sul tronco (schiena, livello L1). Gli algoritmi confrontati sono stati sviluppati in ambiente MATLAB (MathWorks Inc., USA) e sono stati riferiti al gold standard di telecamera a 250 fps analizzando, per ciascuno, i limits of agreement. L'algoritmo implementato da Bergamini et al. (si veda l'articolo 'Estimation of temporal parameters during sprint running using a trunk-mounted inertial measurement unit') è risultato il migliore, con un bias di circa 0.005 s e limits of agreement entro gli 0.025 s fra i dati da sensore e il riferimento video, dati questi che confermano anche i risultati ottenuti da Bergamini et al.

Identificazione dei parametri meccanici del ponte metallico ferroviario a Pontelagoscuro attraverso un algoritmo di ottimizzazione di tipo evolutivo

Nel periodo storico compreso tra la seconda metà dell’Ottocento ed il primo ventennio del Novecento, un’ondata di innovazioni tecnologiche e scientifiche, unitamente all’espansione dell’industria siderurgica e la conseguente diffusione del ferro come materiale da costruzione, portarono alla realizzazione di strutture metalliche grandiose. Ciò fu reso possibile grazie ad una fervida attività di ricerca che permise la risoluzione di problematiche tecniche di assoluto rilievo, come la progettazione di grandi coperture o di ponti destinati al traffico ferroviario in grado di coprire luci sempre maggiori. In questo contesto si sviluppò il sistema della chiodatura come metodo di unione per il collegamento rigido e permanente dei vari elementi che compongono la struttura portante metallica. Ad oggi il sistema della chiodatura è stato quasi completamente sostituito dalla bullonatura di acciaio ad alta resistenza e dalla saldatura, che garantendo gli stessi standard di affidabilità e sicurezza, offrono vantaggi in termini economici e di rapidità esecutiva. Tuttavia lo studio delle unioni chiodate continua a rivestire notevole importanza in tutti quei casi in cui il progettista debba occuparsi di restauro, manutenzione o adeguamento di strutture esistenti che in molti casi continuano ad assolvere le funzioni per le quali erano state progettate. La valutazione delle strutture esistenti, in particolare i ponti, ha assunto un’importanza sempre crescente. L’incremento della mobilità e del traffico sulle infrastrutture di trasporto ha portato ad un incremento contemporaneo di carichi e velocità sui ponti. In particolare nelle ferrovie, i ponti rappresentano una parte strategica della rete ferroviaria e in molti casi, essi hanno già raggiunto i loro limiti di capacità di traffico, tanto è vero che l’età media del sessanta percento dei ponti metallici ferroviari è di un centinaio di anni. Pertanto i carichi di servizio, i cicli di sforzo accumulati a causa dei carichi da traffico e il conseguente invecchiamento delle strutture esistenti, inducono la necessità della valutazione della loro rimanente vita a fatica. In questo contesto, la valutazione delle condizioni del ponte e le conseguenti operazioni di manutenzione o sostituzione diventano indispensabili. Negli ultimi decenni sono state effettuate numerose iniziative di ricerca riguardo il comportamento a fatica dei ponti ferroviari chiodati, poiché le passate esperienze hanno mostrato che tali connessioni sono suscettibili di rotture per fatica. Da uno studio dell’ASCE Committee on Fatigue and Fracture Reliability è emerso che l’ottanta, novanta percento delle crisi nelle strutture metalliche è da relazionarsi ai fenomeni di fatica e frattura. Il danno per fatica riportato dai ponti chiodati è stato osservato principalmente sulle unioni tra elementi principali ed è causato dagli sforzi secondari, che si possono sviluppare in diverse parti delle connessioni. In realtà riguardo la valutazione della fatica sui ponti metallici chiodati, si è scoperto che giocano un ruolo importante molti fattori, anzitutto i ponti ferroviari sono soggetti a grandi variazioni delle tensioni indotte da carichi permanenti e accidentali, così come imperfezioni geometriche e inclinazioni o deviazioni di elementi strutturali comportano sforzi secondari che solitamente non vengono considerati nella valutazione del fenomeno della fatica. Vibrazioni, forze orizzontali trasversali, vincoli interni, difetti localizzati o diffusi come danni per la corrosione, rappresentano cause che concorrono al danneggiamento per fatica della struttura. Per questo motivo si studiano dei modelli agli elementi finiti (FE) che riguardino i particolari delle connessioni e che devono poi essere inseriti all’interno di un modello globale del ponte. L’identificazione degli elementi critici a fatica viene infatti solitamente svolta empiricamente, quindi è necessario che i modelli numerici di cui si dispone per analizzare la struttura nei particolari delle connessioni, così come nella sua totalità, siano il più corrispondenti possibile alla situazione reale. Ciò che ci si propone di sviluppare in questa tesi è un procedimento che consenta di affinare i modelli numerici in modo da ottenere un comportamento dinamico analogo a quello del sistema fisico reale. Si è presa in esame la seguente struttura, un ponte metallico ferroviario a binario unico sulla linea Bologna – Padova, che attraversa il fiume Po tra le località di Pontelagoscuro ed Occhiobello in provincia di Ferrara. Questo ponte fu realizzato intorno agli anni che vanno dal 1945 al 1949 e tra il 2002 e il 2006 ha subito interventi di innalzamento, ampliamento ed adeguamento nel contesto delle operazioni di potenziamento della linea ferroviaria, che hanno portato tra l’altro all’affiancamento di un nuovo ponte, anch’esso a singolo binario, per i convogli diretti nella direzione opposta. Le travate metalliche del ponte ferroviario sono costituite da travi principali a traliccio a gabbia chiusa, con uno schema statico di travi semplicemente appoggiate; tutte le aste delle travi reticolari sono formate da profilati metallici in composizione chiodata. In particolare si è rivolta l’attenzione verso una delle travate centrali, della quale si intende affrontare un’analisi numerica con caratterizzazione dinamica del modello agli Elementi Finiti (FEM), in modo da conoscerne lo specifico comportamento strutturale. Ad oggi infatti l’analisi strutturale si basa prevalentemente sulla previsione del comportamento delle strutture tramite modelli matematici basati su procedimenti risolutivi generali, primo fra tutti il Metodo agli Elementi Finiti. Tuttavia i risultati derivanti dal modello numerico possono discostarsi dal reale comportamento della struttura, proprio a causa delle ipotesi poste alla base della modellazione. Difficilmente infatti si ha la possibilità di riscontrare se le ipotesi assunte nel calcolo della struttura corrispondano effettivamente alla situazione reale, tanto più se come nella struttura in esame si tratta di una costruzione datata e della quale si hanno poche informazioni circa i dettagli relativi alla costruzione, considerando inoltre che, come già anticipato, sforzi secondari e altri fattori vengono trascurati nella valutazione del fenomeno della fatica. Nel seguito si prenderanno in esame le ipotesi su masse strutturali, rigidezze dei vincoli e momento d’inerzia delle aste di parete, grandezze che caratterizzano in particolare il comportamento dinamico della struttura; per questo sarebbe ancora più difficilmente verificabile se tali ipotesi corrispondano effettivamente alla costruzione reale. Da queste problematiche nasce l’esigenza di affinare il modello numerico agli Elementi Finiti, identificando a posteriori quei parametri meccanici ritenuti significativi per il comportamento dinamico della struttura in esame. In specifico si andrà a porre il problema di identificazione come un problema di ottimizzazione, dove i valori dei parametri meccanici vengono valutati in modo che le caratteristiche dinamiche del modello, siano il più simili possibile ai risultati ottenuti da elaborazioni sperimentali sulla struttura reale. La funzione costo è definita come la distanza tra frequenze proprie e deformate modali ottenute dalla struttura reale e dal modello matematico; questa funzione può presentare più minimi locali, ma la soluzione esatta del problema è rappresentata solo dal minimo globale. Quindi il successo del processo di ottimizzazione dipende proprio dalla definizione della funzione costo e dalla capacità dell’algoritmo di trovare il minimo globale. Per questo motivo è stato preso in considerazione per la risoluzione del problema, l’algoritmo di tipo evolutivo DE (Differential Evolution Algorithm), perché gli algoritmi genetici ed evolutivi vengono segnalati per robustezza ed efficienza, tra i metodi di ricerca globale caratterizzati dall’obiettivo di evitare la convergenza in minimi locali della funzione costo. Obiettivo della tesi infatti è l’utilizzo dell’algoritmo DE modificato con approssimazione quadratica (DE-Q), per affinare il modello numerico e quindi ottenere l’identificazione dei parametri meccanici che influenzano il comportamento dinamico di una struttura reale, il ponte ferroviario metallico a Pontelagoscuro.