Heuristic algorithms for the travelling deliveryman problem

Algoritmi euristici per la risoluzione del Travelling DEliveryman Problem

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.

Procedimenti di ottimizzazione di sistemi smorzati

La presente tesi riguarda lo studio di procedimenti di ottimizzazione di sistemi smorzati. In particolare, i sistemi studiati sono strutture shear-type soggette ad azioni di tipo sismico impresse alla base. Per effettuare l’ottimizzazione dei sistemi in oggetto si agisce sulle rigidezze di piano e sui coefficienti di smorzamento effettuando una ridistribuzione delle quantità suddette nei piani della struttura. È interessante effettuare l’ottimizzazione di sistemi smorzati nell’ottica della progettazione antisismica, in modo da ridurre la deformata della struttura e, conseguentemente, anche le sollecitazioni che agiscono su di essa. Il lavoro consta di sei capitoli nei quali vengono affrontate tre procedure numerico-analitiche per effettuare l’ottimizzazione di sistemi shear-type. Nel primo capitolo si studia l’ottimizzazione di sistemi shear-type agendo su funzioni di trasferimento opportunamente vincolate. In particolare, le variabili di progetto sono le rigidezze di piano, mentre i coefficienti di smorzamento e le masse di piano risultano quantità note e costanti durante tutto il procedimento di calcolo iterativo; per effettuare il controllo dinamico della struttura si cerca di ottenere una deformata pressoché rettilinea. Tale condizione viene raggiunta ponendo le ampiezze delle funzioni di trasferimento degli spostamenti di interpiano pari all’ampiezza della funzione di trasferimento del primo piano. Al termine della procedura si ottiene una ridistribuzione della rigidezza complessiva nei vari piani della struttura. In particolare, si evince un aumento della rigidezza nei piani più bassi che risultano essere quelli più sollecitati da una azione impressa alla base e, conseguentemente, si assiste ad una progressiva riduzione della variabile di progetto nei piani più alti. L’applicazione numerica di tale procedura viene effettuata nel secondo capitolo mediante l’ausilio di un programma di calcolo in linguaggio Matlab. In particolare, si effettua lo studio di sistemi a tre e a cinque gradi di libertà. La seconda procedura numerico-analitica viene presentata nel terzo capitolo. Essa riguarda l’ottimizzazione di sistemi smorzati agendo simultaneamente sulla rigidezza e sullo smorzamento e consta di due fasi. La prima fase ricerca il progetto ottimale della struttura per uno specifico valore della rigidezza complessiva e dello smorzamento totale, mentre la seconda fase esamina una serie di progetti ottimali in funzione di diversi valori della rigidezza e dello smorzamento totale. Nella prima fase, per ottenere il controllo dinamico della struttura, viene minimizzata la somma degli scarti quadratici medi degli spostamenti di interpiano. Le variabili di progetto, aggiornate dopo ogni iterazione, sono le rigidezze di piano ed i coefficienti di smorzamento. Si pone, inoltre, un vincolo sulla quantità totale di rigidezza e di smorzamento, e i valori delle rigidezze e dei coefficienti di smorzamento di ogni piano non devono superare un limite superiore posto all’inizio della procedura. Anche in questo caso viene effettuata una ridistribuzione delle rigidezze e dei coefficienti di smorzamento nei vari piani della struttura fino ad ottenere la minimizzazione della funzione obiettivo. La prima fase riduce la deformata della struttura minimizzando la somma degli scarti quadrarici medi degli spostamenti di interpiano, ma comporta un aumento dello scarto quadratico medio dell’accelerazione assoluta dell’ultimo piano. Per mantenere quest’ultima quantità entro limiti accettabili, si passa alla seconda fase in cui si effettua una riduzione dell’accelerazione attraverso l’aumento della quantità totale di smorzamento. La procedura di ottimizzazione di sistemi smorzati agendo simultaneamente sulla rigidezza e sullo smorzamento viene applicata numericamente, mediante l’utilizzo di un programma di calcolo in linguaggio Matlab, nel capitolo quattro. La procedura viene applicata a sistemi a due e a cinque gradi di libertà. L’ultima parte della tesi ha come oggetto la generalizzazione della procedura che viene applicata per un sistema dotato di isolatori alla base. Tale parte della tesi è riportata nel quinto capitolo. Per isolamento sismico di un edificio (sistema di controllo passivo) si intende l’inserimento tra la struttura e le sue fondazioni di opportuni dispositivi molto flessibili orizzontalmente, anche se rigidi in direzione verticale. Tali dispositivi consentono di ridurre la trasmissione del moto del suolo alla struttura in elevazione disaccoppiando il moto della sovrastruttura da quello del terreno. L’inserimento degli isolatori consente di ottenere un aumento del periodo proprio di vibrare della struttura per allontanarlo dalla zona dello spettro di risposta con maggiori accelerazioni. La principale peculiarità dell’isolamento alla base è la possibilità di eliminare completamente, o quantomeno ridurre sensibilmente, i danni a tutte le parti strutturali e non strutturali degli edifici. Quest’ultimo aspetto è importantissimo per gli edifici che devono rimanere operativi dopo un violento terremoto, quali ospedali e i centri operativi per la gestione delle emergenze. Nelle strutture isolate si osserva una sostanziale riduzione degli spostamenti di interpiano e delle accelerazioni relative. La procedura di ottimizzazione viene modificata considerando l’introduzione di isolatori alla base di tipo LRB. Essi sono costituiti da strati in elastomero (aventi la funzione di dissipare, disaccoppiare il moto e mantenere spostamenti accettabili) alternati a lamine in acciaio (aventi la funzione di mantenere una buona resistenza allo schiacciamento) che ne rendono trascurabile la deformabilità in direzione verticale. Gli strati in elastomero manifestano una bassa rigidezza nei confronti degli spostamenti orizzontali. La procedura di ottimizzazione viene applicata ad un telaio shear-type ad N gradi di libertà con smorzatori viscosi aggiunti. Con l’introduzione dell’isolatore alla base si passa da un sistema ad N gradi di libertà ad un sistema a N+1 gradi di libertà, in quanto l’isolatore viene modellato alla stregua di un piano della struttura considerando una rigidezza e uno smorzamento equivalente dell’isolatore. Nel caso di sistema sheat-type isolato alla base, poiché l’isolatore agisce sia sugli spostamenti di interpiano, sia sulle accelerazioni trasmesse alla struttura, si considera una nuova funzione obiettivo che minimizza la somma incrementata degli scarti quadratici medi degli spostamenti di interpiano e delle accelerazioni. Le quantità di progetto sono i coefficienti di smorzamento e le rigidezze di piano della sovrastruttura. Al termine della procedura si otterrà una nuova ridistribuzione delle variabili di progetto nei piani della struttura. In tal caso, però, la sovrastruttura risulterà molto meno sollecitata in quanto tutte le deformazioni vengono assorbite dal sistema di isolamento. Infine, viene effettuato un controllo sull’entità dello spostamento alla base dell’isolatore perché potrebbe raggiungere valori troppo elevati. Infatti, la normativa indica come valore limite dello spostamento alla base 25cm; valori più elevati dello spostamento creano dei problemi soprattutto per la realizzazione di adeguati giunti sismici. La procedura di ottimizzazione di sistemi isolati alla base viene applicata numericamente mediante l’utilizzo di un programma di calcolo in linguaggio Matlab nel sesto capitolo. La procedura viene applicata a sistemi a tre e a cinque gradi di libertà. Inoltre si effettua il controllo degli spostamenti alla base sollecitando la struttura con il sisma di El Centro e il sisma di Northridge. I risultati hanno mostrato che la procedura di calcolo è efficace e inoltre gli spostamenti alla base sono contenuti entro il limite posto dalla normativa. Giova rilevare che il sistema di isolamento riduce sensibilmente le grandezze che interessano la sovrastruttura, la quale si comporta come un corpo rigido al di sopra dell’isolatore. In futuro si potrà studiare il comportamento di strutture isolate considerando diverse tipologie di isolatori alla base e non solo dispositivi elastomerici. Si potrà, inoltre, modellare l’isolatore alla base con un modello isteretico bilineare ed effettuare un confronto con i risultati già ottenuti per il modello lineare.

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.

Ottimizzazione topologica di componenti per impiego aerospaziale

Il lavoro di questa tesi presenta il risultato di una attività di sperimentazione su alcuni algoritmi di ottimizzazione topologica recentemente sviluppati in ambito scientifico e descritti in pubblicazioni su riviste internazionali. L’ottimizzazione topologica può essere definita come una tecnica che mira a variare la forma geometrica di un oggetto bidimensionale o tridimensionale in modo da rispettare requisiti su posizionamento di vincoli e applicazione di forze e da minimizzare l’impiego di materiale necessario ad ottenere una struttura che soddisfi alcuni requisiti. Il settore aerospaziale è sicuramente uno di quelli che può beneficiare di questa metodologia visto che è sempre necessario progettare componenti leggeri e quanto più ottimizzati riducendo gli sprechi di materiale; in ambito aeronautico questo porta ad incrementare l’autonomia ed il carico utile riducendo i costi ambientali ed economici delle attività di trasporto. Discorso analogo vige per il campo spaziale in cui i pesi sono cruciali per la scelta del lanciatore da utilizzare per mandare in orbita strumentazioni e impattano in maniera importante sui costi delle missioni. In questa tesi, dopo una breve descrizione delle tecniche di ottimizzazione topologica prese in considerazione nei test svolti, sono presentati i risultati dell'applicazione di questi metodi ad una serie di specifici casi applicativi del settore aerospaziale, mettendo in risalto i risultati in termini di forme geometriche ottenute per alcuni casi di studio. Per ognuno di questi è descritta la schematizzazione seguita a livello di vincoli e di carichi e la dimensione della superficie o volume di controllo di partenza. Gli esiti del processo di ottimizzazione sono poi commentati, sia a livello di conformazione geometrica ottenuta che di possibilità di implementare dal punto di vista costruttivo la forma trovata.

A multilevel approach to the travelling salesman problem

We motivate, derive, and implement a multilevel approach to the travelling salesman problem.The resulting algorithm progressively coarsens the problem, initialises a tour, and then employs either the Lin-Kernighan (LK) or the Chained Lin-Kernighan (CLK) algorithm to refine the solution on each of the coarsened problems in reverse order.In experiments on a well-established test suite of 80 problem instances we found multilevel configurations that either improved the tour quality by over 25% as compared to the standard CLK algorithm using the same amount of execution time, or that achieved approximately the same tour quality over seven times more rapidly. Moreover, the multilevel variants seem to optimise far better the more clustered instances with which the LK and CLK algorithms have the most difficulties.

Facets of the polytope of the asymmetric travelling salesman problem with replenishment arcs

The Asymmetric Travelling Salesman Problem with Replenishment Arcs (RATSP) is a new class of problems arising from work related to aircraft routing. Given a digraph with cost on the arcs, a solution of the RATSP, like that of the Asymmetric Travelling Salesman Problem, induces a directed tour in the graph which minimises total cost. However the tour must satisfy additional constraints: the arc set is partitioned into replenishment arcs and ordinary arcs, each node has a non-negative weight associated with it, and the tour cannot accumulate more than some weight limit before a replenishment arc must be used. To enforce this requirement, constraints are needed. We refer to these as replenishment constraints.

In this paper, we review previous polyhedral results for the RATSP and related problems, then prove that two classes of constraints developed in V. Mak and N. Boland [Polyhedral results and exact algorithms for the asymmetric travelling salesman problem with replenishment arcs, Technical Report TR M05/03, School of Information Technology, Deakin University, 2005] are, under appropriate conditions, facet-defining for the RATS polytope.

Polyhedral combinatorics of the cardinality constrained quadratic knapsack problem and the quadratic selective travelling salesman problem

This paper considers the Cardinality Constrained Quadratic Knapsack Problem (QKP) and the Quadratic Selective Travelling Salesman Problem (QSTSP). The QKP is a generalization of the Knapsack Problem and the QSTSP is a generalization of the Travelling Salesman Problem. Thus, both problems are NP hard. The QSTSP and the QKP can be solved using branch-and-cut methods. Good bounds can be obtained if strong constraints are used. Hence it is important to identify strong or even facet-defining constraints. This paper studies the polyhedral combinatorics of the QSTSP and the QKP, i.e. amongst others we identify facet-defining constraints for the QSTSP and the QKP, and provide mathematical proofs that they do indeed define facets.

Polyhedral results and exact algorithms for the asymmetric travelling salesman problem with replenishment arcs

The asymmetric travelling salesman problem with replenishment arcs (RATSP), arising from work related to aircraft routing, is a generalisation of the well-known ATSP. In this paper, we introduce a polynomial size mixed-integer linear programming (MILP) formulation for the RATSP, and improve an existing exponential size ILP formulation of Zhu [The aircraft rotation problem, Ph.D. Thesis, Georgia Institute of Technology, Atlanta, 1994] by proposing two classes of stronger cuts. We present results that under certain conditions, these two classes of stronger cuts are facet-defining for the RATS polytope, and that ATSP facets can be lifted, to give RATSP facets. We implement our polyhedral findings and develop a Lagrangean relaxation (LR)-based branch-and-bound (BNB) algorithm for the RATSP, and compare this method with solving the polynomial size formulation using ILOG Cplex 9.0, using both randomly generated problems and aircraft routing problems. Finally we compare our methods with the existing method of Boland et al. [The asymmetric traveling salesman problem with replenishment arcs, European J. Oper. Res. 123 (2000) 408–427]. It turns out that both of our methods are much faster than that of Boland et al. [The asymmetric traveling salesman problem with replenishment arcs, European J. Oper. Res. 123 (2000) 408–427], and that the LR-based BNB method is more efficient for problems that resemble the aircraft rotation problems.