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.

Comparison of EEG signals from epilepsy patients with Bump modeling

Background: l’epilessia è una malattia cerebrale che colpisce oggigiorno circa l’1% della popolazione mondiale e causa, a chi ne soffre, convulsioni ricorrenti e improvvise che danneggiano la vita quotidiana del paziente. Le convulsioni sono degli eventi che bloccano istantaneamente la normale attività cerebrale; inoltre differiscono tra i pazienti e, perciò, non esiste un trattamento comune generalizzato. Solitamente, medici neurologi somministrano farmaci, e, in rari casi, l’epilessia è trattata con operazioni neurochirurgiche. Tuttavia, le operazioni hanno effetti positivi nel ridurre le crisi, ma raramente riescono a eliminarle del tutto. Negli ultimi anni, nel campo della ricerca scientifica è stato provato che il segnale EEG contiene informazioni utili per diagnosticare l'arrivo di un attacco epilettico. Inoltre, diversi algoritmi automatici sono stati sviluppati per rilevare automaticamente le crisi epilettiche. Scopo: lo scopo finale di questa ricerca è l'applicabilità e l'affidabilità di un dispositivo automatico portatile in grado di rilevare le convulsioni e utilizzabile come sistema di monitoraggio. L’analisi condotta in questo progetto, è eseguita con tecniche di misure classiche e avanzate, in modo tale da provare tecnicamente l’affidabilità di un tale sistema. La comparazione è stata eseguita sui segnali elettroencefalografici utilizzando due diversi sistemi di acquisizione EEG: il metodo standard utilizzato nelle cliniche e il nuovo dispositivo portatile. Metodi: è necessaria una solida validazione dei segnali EEG registrati con il nuovo dispositivo. I segnali saranno trattati con tecniche classiche e avanzate. Dopo le operazioni di pulizia e allineamento, verrà utilizzato un nuovo metodo di rappresentazione e confronto di segnali : Bump model. In questa tesi il metodo citato verrà ampiamente descritto, testato, validato e adattato alle esigenze del progetto. Questo modello è definito come un approccio economico per la mappatura spazio-frequenziale di wavelet; in particolare, saranno presenti solo gli eventi con un’alta quantità di energia. Risultati: il modello Bump è stato implementato come toolbox su MATLAB dallo sviluppatore F. Vialatte, e migliorato dall’Autore per l’utilizzo di registrazioni EEG da sistemi diversi. Il metodo è validato con segnali artificiali al fine di garantire l’affidabilità, inoltre, è utilizzato su segnali EEG processati e allineati, che contengono eventi epilettici. Questo serve per rilevare la somiglianza dei due sistemi di acquisizione. Conclusioni: i risultati visivi garantiscono la somiglianza tra i due sistemi, questa differenza la si può notare specialmente comparando i grafici di attività background EEG e quelli di artefatti o eventi epilettici. Bump model è uno strumento affidabile per questa applicazione, e potrebbe essere utilizzato anche per lavori futuri (ad esempio utilizzare il metodo di Sincronicità Eventi Stocas- tici SES) o differenti applicazioni, così come le informazioni estratte dai Bump model potrebbero servire come input per misure di sincronicità, dalle quali estrarre utili risultati.

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 Control of Magnetically Actuated Spacecraft

The topic of this thesis is the feedback stabilization of the attitude of magnetically actuated spacecraft. The use of magnetic coils is an attractive solution for the generation of control torques on small satellites flying inclined low Earth orbits, since magnetic control systems are characterized by reduced weight and cost, higher reliability, and require less power with respect to other kinds of actuators. At the same time, the possibility of smooth modulation of control torques reduces coupling of the attitude control system with flexible modes, thus preserving pointing precision with respect to the case when pulse-modulated thrusters are used. The principle based on the interaction between the Earth's magnetic field and the magnetic field generated by the set of coils introduces an inherent nonlinearity, because control torques can be delivered only in a plane that is orthogonal to the direction of the geomagnetic field vector. In other words, the system is underactuated, because the rotational degrees of freedom of the spacecraft, modeled as a rigid body, exceed the number of independent control actions. The solution of the control issue for underactuated spacecraft is also interesting in the case of actuator failure, e.g. after the loss of a reaction-wheel in a three-axes stabilized spacecraft with no redundancy. The application of well known control strategies is no longer possible in this case for both regulation and tracking, so that new methods have been suggested for tackling this particular problem. The main contribution of this thesis is to propose continuous time-varying controllers that globally stabilize the attitude of a spacecraft, when magneto-torquers alone are used and when a momentum-wheel supports magnetic control in order to overcome the inherent underactuation. A kinematic maneuver planning scheme, stability analyses, and detailed simulation results are also provided, with new theoretical developments and particular attention toward application considerations.

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.

Sparse Signal Representation of Ultrasonic Signals for Structural Health Monitoring Applications

Assessment of the integrity of structural components is of great importance for aerospace systems, land and marine transportation, civil infrastructures and other biological and mechanical applications. Guided waves (GWs) based inspections are an attractive mean for structural health monitoring. In this thesis, the study and development of techniques for GW ultrasound signal analysis and compression in the context of non-destructive testing of structures will be presented. In guided wave inspections, it is necessary to address the problem of the dispersion compensation. A signal processing approach based on frequency warping was adopted. Such operator maps the frequencies axis through a function derived by the group velocity of the test material and it is used to remove the dependence on the travelled distance from the acquired signals. Such processing strategy was fruitfully applied for impact location and damage localization tasks in composite and aluminum panels. It has been shown that, basing on this processing tool, low power embedded system for GW structural monitoring can be implemented. Finally, a new procedure based on Compressive Sensing has been developed and applied for data reduction. Such procedure has also a beneficial effect in enhancing the accuracy of structural defects localization. This algorithm uses the convolutive model of the propagation of ultrasonic guided waves which takes advantage of a sparse signal representation in the warped frequency domain. The recovery from the compressed samples is based on an alternating minimization procedure which achieves both an accurate reconstruction of the ultrasonic signal and a precise estimation of waves time of flight. Such information is used to feed hyperbolic or elliptic localization procedures, for accurate impact or damage localization.

Sea level measurement using single GNSS antenna SNR signals

This thesis presents a possible method to calculate sea level variation using geodetic-quality Global Navigate Satellite System (GNSS) receivers. Three antennas are used: two small antennas and a choke ring one, analyzing only Global Positioning System signals. The main goal of the thesis is to test a modified configuration for antenna set up. In particular, measurements obtained tilting one antenna to face the horizon are compared to measurements obtained from antennas looking upward. The location of the experiment is a coastal environment nearby the Onsala Space Observatory in Sweden. Sea level variations are obtained using periodogram analysis of the SNR signal and compared to synthetic gauge generated from two independent tide gauges. The choke ring antenna provides poor result, with an RMS around 6 cm and a correlation coefficients of 0.89. The smaller antennas provide correlation coefficients around 0.93. The antenna pointing upward present an RMS of 4.3 cm and the one pointing the horizon an RMS of 6.7 cm. Notable variation in the statistical parameters is found when modifying the length of the interval analyzed. In particular, doubts are risen on the reliability of certain scattered data. No relation is found between the accuracy of the method and weather conditions. Possible methods to enhance the available data are investigated, and correlation coefficient above 0.97 can be obtained with small antennas when sacrificing data points. Hence, the results provide evidence of the suitability of SNR signal analysis for sea level variation in coastal environment even in the case of adverse weather conditions. In particular, tilted configurations provides comparable result with upward looking geodetic antennas. A SNR signal simulator is also tested to investigate its performance and usability. Various configuration are analyzed in combination with the periodogram procedure used to calculate the height of reflectors. Consistency between the data calculated and those received is found, and the overall accuracy of the height calculation program is found to be around 5 mm for input height below 5 m. The procedure is thus found to be suitable to analyze the data provided by the GNSS antennas at Onsala.

Analysis and design of high performance multiphase electric drives for vehicle and aircraft applications

The first part of this thesis has focused on the construction of a twelve-phase asynchronous machine for More Electric Aircraft (MEA) applications. In fact, the aerospace world has found in electrification the way to improve the efficiency, reliability and maintainability of an aircraft. This idea leads to the aircraft a new management and distribution of electrical services. In this way is possible to remove or to reduce the hydraulic, mechanical and pneumatic systems inside the aircraft. The second part of this dissertation is dedicated on the enhancement of the control range of matrix converters (MCs) operating with non-unity input power factor and, at the same time, on the reduction of the switching power losses. The analysis leads to the determination in closed form of a modulation strategy that features a control range, in terms of output voltage and input power factor, that is greater than that of the traditional strategies under the same operating conditions, and a reduction in the switching power losses.

Multicentre study for a robust protocol in single-voxel spectroscopy: quantification of MRS signals by time-domain fitting algorithms

Magnetic Resonance Spectroscopy (MRS) is an advanced clinical and research application which guarantees a specific biochemical and metabolic characterization of tissues by the detection and quantification of key metabolites for diagnosis and disease staging. The "Associazione Italiana di Fisica Medica (AIFM)" has promoted the activity of the "Interconfronto di spettroscopia in RM" working group. The purpose of the study is to compare and analyze results obtained by perfoming MRS on scanners of different manufacturing in order to compile a robust protocol for spectroscopic examinations in clinical routines. This thesis takes part into this project by using the GE Signa HDxt 1.5 T at the Pavillion no. 11 of the S.Orsola-Malpighi hospital in Bologna. The spectral analyses have been performed with the jMRUI package, which includes a wide range of preprocessing and quantification algorithms for signal analysis in the time domain. After the quality assurance on the scanner with standard and innovative methods, both spectra with and without suppression of the water peak have been acquired on the GE test phantom. The comparison of the ratios of the metabolite amplitudes over Creatine computed by the workstation software, which works on the frequencies, and jMRUI shows good agreement, suggesting that quantifications in both domains may lead to consistent results. The characterization of an in-house phantom provided by the working group has achieved its goal of assessing the solution content and the metabolite concentrations with good accuracy. The goodness of the experimental procedure and data analysis has been demonstrated by the correct estimation of the T2 of water, the observed biexponential relaxation curve of Creatine and the correct TE value at which the modulation by J coupling causes the Lactate doublet to be inverted in the spectrum. The work of this thesis has demonstrated that it is possible to perform measurements and establish protocols for data analysis, based on the physical principles of NMR, which are able to provide robust values for the spectral parameters of clinical use.

Feedback linearization of antagonistically actuated variable stiffness joints with twisted string actuators

The work of this thesis is on the implementation of a variable stiffness joint antagonistically actuated by a couple of twisted-string actuator (TSA). This type of joint is possible to be applied in the field of robotics, like UB Hand IV (the anthropomorphic robotic hand developed by University of Bologna). The purposes of the activities are to build the joint dynamic model and simultaneously control the position and stiffness. Three different control approaches (Feedback linearization, PID, PID+Feedforward) are proposed and validated in simulation. To improve the properties of joint stiffness, a joint with elastic element is taken into account and discussed. To the end, the experimental setup that has been developed for the experimental validation of the proposed control approaches.

Autonomous Vehicle and Internet on Vehicles

In questa tesi mi occupo di spiegare come si comportano i veicoli autonomi per prendere tutte le decisioni e come i dati dei sensori di ogni auto vengono condivisi con la flotta di veicoli

Meccanismi di Gamification per interfacce human-vehicle

L’obiettivo principale di questa tesi è utilizzare le tecniche di gamification più importanti nella progettazione ed implementazione di un’interfaccia Human-Vehicle per creare un software che possa rendere la guida di un’automobile elettrica più efficace ed efficiente da parte del guidatore. Per lo sviluppo del software è stato svolto uno studio specifico sulla gamification, sulle interfacce Human-Vehicle e sulle macchine elettriche attualmente in produzione. Successivamente è stata svolta la fase di progettazione in cui sono stati creati dei mockup relativi all’interfaccia grafica ed è stato svolto un focus group. Infine è stato implementato il vero e proprio software di simulazione EcoGame ed è stato effettuato un test utenti.