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.

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.

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.

L'area dei Lungarni di Pisa nel tardo Medioevo (XIV-XV secolo). un tentativo di ricostruzione in 3D.

Lo scopo di questa ricerca è la ricostruzione dei Lungarni di Pisa nel Tardo Medioevo (XIV-XV secolo); lo studio intende sottolineare le trasformazioni urbanistiche che hanno cambiato il volto di Pisa nel corso del tempo e ricordare che l’area fluviale ebbe un ruolo di primo piano come baricentro commerciale ed economico della città, vocazione che si è in gran parte persa con l’età moderna e contemporanea. La metodologia seguita, affinata e perfezionata durante la partecipazione al progetto Nu.M.E. (Nuovo Museo Elettronico della Città di Bologna), si basa sull’analisi e il confronto di fonti eterogenee ma complementari, che includono precedenti studi di storia dell’urbanistica, un corpus di documentazione di epoca medievale (provvedimenti amministrativi come gli Statuti del Comune di Pisa, ma anche descrizioni di cronisti e viaggiatori), fonti iconografiche, tra cui vedute e mappe cinquecentesche o successive, e fonti materiali, come le persistenze medievali ancora osservabili all’interno degli edifici ed i reperti rinvenuti durante alcune campagne di scavo archeologiche. Il modello 3D non è concepito come statico e “chiuso”, ma è liberamente esplorabile all’interno di un engine tridimensionale; tale prodotto può essere destinato a livelli di utenza diversi, che includono sia studiosi e specialisti interessati a conoscere un maggior numero di informazioni e ad approfondire la ricerca, sia semplici cittadini appassionati di storia o utenti più giovani, come studenti di scuole medie superiori e inferiori.

Una prospettiva storico-filosofica sull'evoluzione del curricolo di fisica nella scuola: problemi e innovazioni pedagogiche

Negli ultimi vent’anni sono state proposte al livello internazionale alcune analisi dei problemi per le scienze nella scuola e diverse strategie per l’innovazione didattica. Molte ricerche hanno fatto riferimento a una nuova nozione di literacy scientifica, quale sapere fondamentale dell’educazione, indipendente dalle scelte professionali successive alla scuola. L’ipotesi di partenza di questa ricerca sostiene che alcune di queste analisi e l’idea di una nuova literacy scientifica di tipo non-vocazionale mostrino notevoli limiti quando rapportate al contesto italiano. Le specificità di quest’ultimo sono state affrontate, innanzitutto, da un punto di vista comparativo, discutendo alcuni documenti internazionali sull’insegnamento delle scienze. Questo confronto ha messo in luce la difficoltà di ottenere un insieme di evidenze chiare e definitive sui problemi dell’educazione scientifica discussi da questi documenti, in particolare per quanto riguarda i dati sulla crisi delle vocazioni scientifiche e sull’attitudine degli studenti verso le scienze. Le raccomandazioni educative e alcuni progetti curricolari internazionali trovano degli ostacoli decisivi nella scuola superiore italiana anche a causa di specificità istituzionali, come particolari principi di selezione e l’articolazione dei vari indirizzi formativi. Il presente lavoro si è basato soprattutto su una ricostruzione storico-pedagogica del curricolo di fisica, attraverso l’analisi delle linee guida nazionali, dei programmi di studio e di alcuni rappresentativi manuali degli ultimi decenni. Questo esame del curricolo “programmato” ha messo in luce, primo, il carattere accademico della fisica liceale e la sua debole rielaborazione culturale e didattica, secondo, l’impatto di temi e problemi internazionali sui materiali didattici. Tale impatto ha prodotto dei cambiamenti sul piano delle finalità educative e degli strumenti di apprendimento incorporati nei manuali. Nonostante l’evoluzione di queste caratteristiche del curricolo, tuttavia, l’analisi delle conoscenze storico-filosofiche utilizzate dai manuali ha messo in luce la scarsa contestualizzazione culturale della fisica quale uno degli ostacoli principali per l’insegnamento di una scienza più rilevante e formativa.

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.

Nonlinear constrained and saturated control of power electronics and electromechanical systems

Power electronic converters are extensively adopted for the solution of timely issues, such as power quality improvement in industrial plants, energy management in hybrid electrical systems, and control of electrical generators for renewables. Beside nonlinearity, this systems are typically characterized by hard constraints on the control inputs, and sometimes the state variables. In this respect, control laws able to handle input saturation are crucial to formally characterize the systems stability and performance properties. From a practical viewpoint, a proper saturation management allows to extend the systems transient and steady-state operating ranges, improving their reliability and availability. The main topic of this thesis concern saturated control methodologies, based on modern approaches, applied to power electronics and electromechanical systems. The pursued objective is to provide formal results under any saturation scenario, overcoming the drawbacks of the classic solution commonly applied to cope with saturation of power converters, and enhancing performance. For this purpose two main approaches are exploited and extended to deal with power electronic applications: modern anti-windup strategies, providing formal results and systematic design rules for the anti-windup compensator, devoted to handle control saturation, and “one step” saturated feedback design techniques, relying on a suitable characterization of the saturation nonlinearity and less conservative extensions of standard absolute stability theory results. The first part of the thesis is devoted to present and develop a novel general anti-windup scheme, which is then specifically applied to a class of power converters adopted for power quality enhancement in industrial plants. In the second part a polytopic differential inclusion representation of saturation nonlinearity is presented and extended to deal with a class of multiple input power converters, used to manage hybrid electrical energy sources. The third part regards adaptive observers design for robust estimation of the parameters required for high performance control of power systems.

Nonlinear Observers for Sensorless Control of Permanent Magnet Synchronous Motors

In this thesis, the industrial application of control a Permanent Magnet Synchronous Motor in a sensorless configuration has been faced, and in particular the task of estimating the unknown “parameters” necessary for the application of standard motor control algorithms. In literature several techniques have been proposed to cope with this task, among them the technique based on model-based nonlinear observer has been followed. The hypothesis of neglecting the mechanical dynamics from the motor model has been applied due to practical and physical considerations, therefore only the electromagnetic dynamics has been used for the observers design. First observer proposed is based on stator currents and Stator Flux dynamics described in a generic rotating reference frame. Stator flux dynamics are known apart their initial conditions which are estimated, with speed that is also unknown, through the use of the Adaptive Theory. The second observer proposed is based on stator currents and Rotor Flux dynamics described in a self-aligning reference frame. Rotor flux dynamics are described in the stationary reference frame exploiting polar coordinates instead of classical Cartesian coordinates, by means the estimation of amplitude and speed of the rotor flux. The stability proof is derived in a Singular Perturbation Framework, which allows for the use the current estimation errors as a measure of rotor flux estimation errors. The stability properties has been derived using a specific theory for systems with time scale separation, which guarantees a semi-global practical stability. For the two observer ideal simulations and real simulations have been performed to prove the effectiveness of the observers proposed, real simulations on which the effects of the Inverter nonlinearities have been introduced, showing the already known problems of the model-based observers for low speed applications.

Gait analysis using a single wearable inertial measurement unit

Procedures for quantitative walking analysis include the assessment of body segment movements within defined gait cycles. Recently, methods to track human body motion using inertial measurement units have been suggested. It is not known if these techniques can be readily transferred to clinical measurement situations. This work investigates the aspects necessary for one inertial measurement unit mounted on the lower back to track orientation, and determine spatio-temporal features of gait outside the confines of a conventional gait laboratory. Apparent limitations of different inertial sensors can be overcome by fusing data using methods such as a Kalman filter. The benefits of optimizing such a filter for the type of motion are unknown. 3D accelerations and 3D angular velocities were collected for 18 healthy subjects while treadmill walking. Optimization of Kalman filter parameters improved pitch and roll angle estimates when compared to angles derived using stereophotogrammetry. A Weighted Fourier Linear Combiner method for estimating 3D orientation angles by constructing an analytical representation of angular velocities and allowing drift free integration is also presented. When tested this method provided accurate estimates of 3D orientation when compared to stereophotogrammetry. Methods to determine spatio-temporal features from lower trunk accelerations generally require knowledge of sensor alignment. A method was developed to estimate the instants of initial and final ground contact from accelerations measured by a waist mounted inertial device without rigorous alignment. A continuous wavelet transform method was used to filter and differentiate the signal and derive estimates of initial and final contact times. The technique was tested with data recorded for both healthy and pathologic (hemiplegia and Parkinson’s disease) subjects and validated using an instrumented mat. The results show that a single inertial measurement unit can assist whole body gait assessment however further investigation is required to understand altered gait timing in some pathological subjects.

Il rapporto architettura – suolo nell’opera di Aldo Rossi

La ricerca muove dal presupposto che l’opera di Aldo Rossi sia stata analizzata finora secondo un criterio tipologico. Tale approccio è una tra le possibili chiavi di lettura del lavoro dell’architetto. Nel tentativo di individuare un’interpretazione dell’opera di Rossi legata a sistemi immutabili nel tempo si è ritenuto necessario approfondire la relazione che si stabilisce tra la sua opera e il suolo. Attraverso la definizione di due categorie di lettura dei progetti dell’autore, che si basano su continuità o discontinuità fisica del progetto rispetto al suolo, si comprende come il rapporto tra area e progetto produca nel tempo soluzioni ricorrenti. In base a questa interpretazione muro e pilastro costituiscono due elementi fondamentali del linguaggio di Rossi. Essi a loro volta si allacciano ad un sistema di riferimento più ampio di cui tettonica e arte muraria sono i capisaldi. La ricerca si articola in tre parti, all’interno delle quali sono sviluppati specifici capitoli. La prima parte, sistema di riferimento, è necessaria a delineare un vocabolario utile per isolare il tema trattato. Essa è fondamentale per comprendere la posizione occupata da Rossi rispetto alle esperienze verificatesi nel corso della storia, relativamente al rapporto spazio - architettura - suolo. La seconda parte, arte muraria, serve a mettere in luce l’influenza che la componente massiva e plastica del terreno ha determinato nella definizione di specifiche soluzioni progettuali. La terza parte, tettonica, delinea invece un approccio opposto al precedente, individuando quei progetti in cui il rapporto col suolo è stato sminuito o addirittura negato, aumentando il senso di sospensione dei volumi nello spazio. In definitiva, l’influenza che il rapporto col suolo ha determinato sulle scelte progettuali di Rossi rappresenta l’interrogativo principale di questa ricerca.

Model predictive control in thermal management of multiprocessor systems-on-chip

MultiProcessor Systems-on-Chip (MPSoC) are the core of nowadays and next generation computing platforms. Their relevance in the global market continuously increase, occupying an important role both in everydaylife products (e.g. smartphones, tablets, laptops, cars) and in strategical market sectors as aviation, defense, robotics, medicine. Despite of the incredible performance improvements in the recent years processors manufacturers have had to deal with issues, commonly called “Walls”, that have hindered the processors development. After the famous “Power Wall”, that limited the maximum frequency of a single core and marked the birth of the modern multiprocessors system-on-chip, the “Thermal Wall” and the “Utilization Wall” are the actual key limiter for performance improvements. The former concerns the damaging effects of the high temperature on the chip caused by the large power densities dissipation, whereas the second refers to the impossibility of fully exploiting the computing power of the processor due to the limitations on power and temperature budgets. In this thesis we faced these challenges by developing efficient and reliable solutions able to maximize performance while limiting the maximum temperature below a fixed critical threshold and saving energy. This has been possible by exploiting the Model Predictive Controller (MPC) paradigm that solves an optimization problem subject to constraints in order to find the optimal control decisions for the future interval. A fully-distributedMPC-based thermal controller with a far lower complexity respect to a centralized one has been developed. The control feasibility and interesting properties for the simplification of the control design has been proved by studying a partial differential equation thermal model. Finally, the controller has been efficiently included in more complex control schemes able to minimize energy consumption and deal with mixed-criticalities tasks

Residual visual processing following real or virtual lesions to primary visual pathways

Lesions to the primary geniculo-striate visual pathway cause blindness in the contralesional visual field. Nevertheless, previous studies have suggested that patients with visual field defects may still be able to implicitly process the affective valence of unseen emotional stimuli (affective blindsight) through alternative visual pathways bypassing the striate cortex. These alternative pathways may also allow exploitation of multisensory (audio-visual) integration mechanisms, such that auditory stimulation can enhance visual detection of stimuli which would otherwise be undetected when presented alone (crossmodal blindsight). The present dissertation investigated implicit emotional processing and multisensory integration when conscious visual processing is prevented by real or virtual lesions to the geniculo-striate pathway, in order to further clarify both the nature of these residual processes and the functional aspects of the underlying neural pathways. The present experimental evidence demonstrates that alternative subcortical visual pathways allow implicit processing of the emotional content of facial expressions in the absence of cortical processing. However, this residual ability is limited to fearful expressions. This finding suggests the existence of a subcortical system specialised in detecting danger signals based on coarse visual cues, therefore allowing the early recruitment of flight-or-fight behavioural responses even before conscious and detailed recognition of potential threats can take place. Moreover, the present dissertation extends the knowledge about crossmodal blindsight phenomena by showing that, unlike with visual detection, sound cannot crossmodally enhance visual orientation discrimination in the absence of functional striate cortex. This finding demonstrates, on the one hand, that the striate cortex plays a causative role in crossmodally enhancing visual orientation sensitivity and, on the other hand, that subcortical visual pathways bypassing the striate cortex, despite affording audio-visual integration processes leading to the improvement of simple visual abilities such as detection, cannot mediate multisensory enhancement of more complex visual functions, such as orientation discrimination.

Coordination and Control of Autonomous Mobile Robots Swarms by using Particle Swarm Optimization Algorithm and Consensus Theory

This thesis presents some different techniques designed to drive a swarm of robots in an a-priori unknown environment in order to move the group from a starting area to a final one avoiding obstacles. The presented techniques are based on two different theories used alone or in combination: Swarm Intelligence (SI) and Graph Theory. Both theories are based on the study of interactions between different entities (also called agents or units) in Multi- Agent Systems (MAS). The first one belongs to the Artificial Intelligence context and the second one to the Distributed Systems context. These theories, each one from its own point of view, exploit the emergent behaviour that comes from the interactive work of the entities, in order to achieve a common goal. The features of flexibility and adaptability of the swarm have been exploited with the aim to overcome and to minimize difficulties and problems that can affect one or more units of the group, having minimal impact to the whole group and to the common main target. Another aim of this work is to show the importance of the information shared between the units of the group, such as the communication topology, because it helps to maintain the environmental information, detected by each single agent, updated among the swarm. Swarm Intelligence has been applied to the presented technique, through the Particle Swarm Optimization algorithm (PSO), taking advantage of its features as a navigation system. The Graph Theory has been applied by exploiting Consensus and the application of the agreement protocol with the aim to maintain the units in a desired and controlled formation. This approach has been followed in order to conserve the power of PSO and to control part of its random behaviour with a distributed control algorithm like Consensus.

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.