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.

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.

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

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

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

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

Heuristic algorithms for the Capacitated Location-Routing Problem and the Multi-Depot Vehicle Routing Problem

The Capacitated Location-Routing Problem (CLRP) is a NP-hard problem since it generalizes two well known NP-hard problems: the Capacitated Facility Location Problem (CFLP) and the Capacitated Vehicle Routing Problem (CVRP). The Multi-Depot Vehicle Routing Problem (MDVRP) is known to be a NP-hard since it is a generalization of the well known Vehicle Routing Problem (VRP), arising with one depot. This thesis addresses heuristics algorithms based on the well-know granular search idea introduced by Toth and Vigo (2003) to solve the CLRP and the MDVRP. Extensive computational experiments on benchmark instances for both problems have been performed to determine the effectiveness of the proposed algorithms. This work is organized as follows: Chapter 1 describes a detailed overview and a methodological review of the literature for the the Capacitated Location-Routing Problem (CLRP) and the Multi-Depot Vehicle Routing Problem (MDVRP). Chapter 2 describes a two-phase hybrid heuristic algorithm to solve the CLRP. Chapter 3 shows a computational comparison of heuristic algorithms for the CLRP. Chapter 4 presents a hybrid granular tabu search approach for solving the MDVRP.

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.

Land use management in mountainous areas: combining ground-based and EO (Earth Observation) data to investigate the shallow landsliding susceptibility in the Duron valley (Trento, Italy).

Throughout the alpine domain, shallow landslides represent a serious geologic hazard, often causing severe damages to infrastructures, private properties, natural resources and in the most catastrophic events, threatening human lives. Landslides are a major factor of landscape evolution in mountainous and hilly regions and represent a critical issue for mountainous land management, since they cause loss of pastoral lands. In several alpine contexts, shallow landsliding distribution is strictly connected to the presence and condition of vegetation on the slopes. With the aid of high-resolution satellite images, it's possible to divide automatically the mountainous territory in land cover classes, which contribute with different magnitude to the stability of the slopes. The aim of this research is to combine EO (Earth Observation) land cover maps with ground-based measurements of the land cover properties. In order to achieve this goal, a new procedure has been developed to automatically detect grass mantle degradation patterns from satellite images. Moreover, innovative surveying techniques and instruments are tested to measure in situ the shear strength of grass mantle and the geomechanical and geotechnical properties of these alpine soils. Shallow landsliding distribution is assessed with the aid of physically based models, which use the EO-based map to distribute the resistance parameters across the landscape.

Progettazione di poltrona ad inseguimento solare collocata su ponte navale

Progetto e dimensionamento di una poltrona ad inseguimento solare. Scelta del meccanismo da adottare per la movimentazione automatica dello schienale e della seduta.

Progetto e realizzazione di un dispositivo di controllo e gestione remoto per un sistema di tracking satellitare (ALMATracker)

La seguente tesi presenta lo sviluppo di un sistema di controllo e gestione remota per il tracking di un satellite. Il progetto, denominato ALMATracker, è sviluppato dal corso di Ingegneria Aerospaziale della scuola di Ingegneria e Architettura Aerospaziale dell’Università di Bologna con sede a Forlì. Consiste nella creazione di una motorizzazione per antenne su due assi, movimentata da un hardware commerciale programmabile. Il posizionamento può essere eseguito sia manualmente, su richiesta di un utente da PC remoto, sia automaticamente secondo un’orbita preimpostata. I setpoint di velocità o posizione sono elaborati dal sistema fino ad ottenere un segnale che procede alla movimentazione in velocità dell’antenna. Il comando automatico, invece, orienta l’antenna in modo tale da mantenerla fissa su una traiettoria orbitale di uno specifico spacecraft. La movimentazione automatica segue funzioni polinomiali fornite dall’utente, ricavate da software di propagazione e predizione esterno al sistema ALMATracker. In questo caso il sistema deve procedere alla rotazione mantenendo la velocità richiesta dalla funzione polinomiale. Il controllo effettuato in catena chiusa è attuato tramite una serie di trasduttori di posizione presenti nel sistema.

Efficient ultrasonic signal processing techniques for aided medical diagnostics

Ultrasound imaging is widely used in medical diagnostics as it is the fastest, least invasive, and least expensive imaging modality. However, ultrasound images are intrinsically difficult to be interpreted. In this scenario, Computer Aided Detection (CAD) systems can be used to support physicians during diagnosis providing them a second opinion. This thesis discusses efficient ultrasound processing techniques for computer aided medical diagnostics, focusing on two major topics: (i) Ultrasound Tissue Characterization (UTC), aimed at characterizing and differentiating between healthy and diseased tissue; (ii) Ultrasound Image Segmentation (UIS), aimed at detecting the boundaries of anatomical structures to automatically measure organ dimensions and compute clinically relevant functional indices. Research on UTC produced a CAD tool for Prostate Cancer detection to improve the biopsy protocol. In particular, this thesis contributes with: (i) the development of a robust classification system; (ii) the exploitation of parallel computing on GPU for real-time performance; (iii) the introduction of both an innovative Semi-Supervised Learning algorithm and a novel supervised/semi-supervised learning scheme for CAD system training that improve system performance reducing data collection effort and avoiding collected data wasting. The tool provides physicians a risk map highlighting suspect tissue areas, allowing them to perform a lesion-directed biopsy. Clinical validation demonstrated the system validity as a diagnostic support tool and its effectiveness at reducing the number of biopsy cores requested for an accurate diagnosis. For UIS the research developed a heart disease diagnostic tool based on Real-Time 3D Echocardiography. Thesis contributions to this application are: (i) the development of an automated GPU based level-set segmentation framework for 3D images; (ii) the application of this framework to the myocardium segmentation. Experimental results showed the high efficiency and flexibility of the proposed framework. Its effectiveness as a tool for quantitative analysis of 3D cardiac morphology and function was demonstrated through clinical validation.

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

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.