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.

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.

Simulazioni realistiche di algoritmi di Crowd Steering

La simulazione realistica del movimento di pedoni riveste una notevole importanza nei mondi dell'architettonica e della sicurezza (si pensi ad esempio all'evacuazione di ambienti), nell'industria dell'entertainment e in molti altri ambiti, importanza che è aumentata negli ultimi anni. Obiettivo di questo lavoro è l'analisi di un modello di pedone esistente e l'applicazione ad esso di algoritmi di guida, l'implementazione di un modello più realistico e la realizzazione di simulazioni con particolare attenzione alla scalabilità. Per la simulazione è stato utilizzato il framework Alchemist, sviluppato all'interno del laboratorio di ricerca APICe, realizzando inoltre alcune estensioni che potranno essere inglobate nel pacchetto di distribuzione del sistema stesso. I test effettuati sugli algoritmi presi in esame evidenziano un buon guadagno in termini di tempo in ambienti affollati e il nuovo modello di pedone risulta avere un maggiore realismo rispetto a quello già esistente, oltre a superarne alcuni limiti evidenziati durante i test e ad essere facilmente estensibile.

Accessible information in a two-qubit system through the quantum steering ellipsoids formalism

Capire come ottenere l'informazione accessibile, cioè quanta informazione classica si può estrarre da un processo quantistico, è una delle questioni più intricate e affascinanti nell'ambito della teoria dell'informazione quantistica. Nonostante l'importanza della nozione di informazione accessibile non esistono metodi generali per poterla calcolare, esistono soltanto dei limiti, i più famosi dei quali sono il limite superiore di Holevo e il limite inferiore di Josza-Robb-Wootters. La seguente tesi fa riferimento a un processo che coinvolge due parti, Alice e Bob, che condividono due qubits. Si considera il caso in cui Bob effettua misure binarie sul suo qubit e quindi indirizza lo stato del qubit di Alice in due possibili stati. L'obiettivo di Alice è effettuare la misura ottimale nell'ottica di decretare in quale dei due stati si trova il suo qubit. Lo strumento scelto per studiare questo processo va sotto il nome di 'quantum steering ellipsoids formalism'. Esso afferma che lo stato di un sistema di due qubit può essere descritto dai vettori di Bloch di Alice e Bob e da un ellissoide nella sfera di Bloch di Alice generato da tutte le possibili misure di Bob. Tra tutti gli stati descritti da ellissoidi ce ne sono alcuni che manifestano particolari proprietà, per esempio gli stati di massimo volume. Considerando stati di massimo volume e misure binarie si è riuscito a trovare un limite inferiore all'informazione accessibile per un sistema di due qubit migliore del limite inferiore di Josza-Robb-Wootters. Un altro risultato notevole e inaspettato è che l'intuitiva e giustificata relazione 'distanza tra i punti nell'ellissoide - mutua informazione' non vale quando si confrontano coppie di punti ''vicine'' tra loro e lontane dai più distanti.

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.

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.

Minimizing residential distribution system operating costs through intelligently scheduled plug-in hybrid electric vehicle charging

Rising fuel prices and environmental concerns are threatening the stability of current electrical grid systems. These factors are pushing the automobile industry towards more effcient, hybrid vehicles. Current trends show petroleum is being edged out in favor of electricity as the main vehicular motive force. The proposed methods create an optimized charging control schedule for all participating Plug-in Hybrid Electric Vehicles in a distribution grid. The optimization will minimize daily operating costs, reduce system losses, and improve power quality. This requires participation from Vehicle-to-Grid capable vehicles, load forecasting, and Locational Marginal Pricing market predictions. Vehicles equipped with bidirectional chargers further improve the optimization results by lowering peak demand and improving power quality.

Development of Hardware-In-the-Loop Simulation System for Hybrid Electric Vehicle Study

The development of embedded control systems for a Hybrid Electric Vehicle (HEV) is a challenging task due to the multidisciplinary nature of HEV powertrain and its complex structures. Hardware-In-the-Loop (HIL) simulation provides an open and convenient environment for the modeling, prototyping, testing and analyzing HEV control systems. This thesis focuses on the development of such a HIL system for the hybrid electric vehicle study. The hardware architecture of the HIL system, including dSPACE eDrive HIL simulator, MicroAutoBox II and MotoTron Engine Control Module (ECM), is introduced. Software used in the system includes dSPACE Real-Time Interface (RTI) blockset, Automotive Simulation Models (ASM), Matlab/Simulink/Stateflow, Real-time Workshop, ControlDesk Next Generation, ModelDesk and MotoHawk/MotoTune. A case study of the development of control systems for a single shaft parallel hybrid electric vehicle is presented to summarize the functionality of this HIL system.

STUDY OF HYBRID ELECTRIC VEHICLE BATTERY MODELING AND CONTROL USING AUTONOMIE

This report presents the research results of battery modeling and control for hybrid electric vehicles (HEV). The simulation study is conducted using plug-and-play powertrain and vehicle development software, Autonomie. The base vehicle model used for testing the performance of battery model and battery control strategy is the Prius MY04, a power-split hybrid electric vehicle model in Autonomie. To evaluate the battery performance for HEV applications, the Prius MY04 model and its powertrain energy flow in various vehicle operating modes are analyzed. The power outputs of the major powertrain components under different driving cycles are discussed with a focus on battery performance. The simulation results show that the vehicle fuel economy calculated by the Autonomie Prius MY04 model does not match very well with the official data provided by the department of energy (DOE). It is also found that the original battery model does not consider the impact of environmental temperature on battery cell capacities. To improve battery model, this study includes battery current loss on coulomb coefficient and the impact of environmental temperature on battery cell capacity in the model. In addition, voltage losses on both double layer effect and diffusion effect are included in the new battery model. The simulation results with new battery model show the reduced fuel economy error to the DOE data comparing with the original Autonomie Prius MY04 model.

Predictive control of hybrid vehicle powertrain for intelligent energy management

This thesis studies the minimization of the fuel consumption for a Hybrid Electric Vehicle (HEV) using Model Predictive Control (MPC). The presented MPC – based controller calculates an optimal sequence of control inputs to a hybrid vehicle using the measured plant outputs, the current dynamic states, a system model, system constraints, and an optimization cost function. The MPC controller is developed using Matlab MPC control toolbox. To evaluate the performance of the presented controller, a power-split hybrid vehicle, 2004 Toyota Prius, is selected. The vehicle uses a planetary gear set to combine three power components, an engine, a motor, and a generator, and transfer energy from these components to the vehicle wheels. The planetary gear model is developed based on the Willis’s formula. The dynamic models of the engine, the motor, and the generator, are derived based on their dynamics at the planetary gear. The MPC controller for HEV energy management is validated in the MATLAB/Simulink environment. Both the step response performance (a 0 – 60 mph step input) and the driving cycle tracking performance are evaluated. Two standard driving cycles, Urban Dynamometer Driving Schedule (UDDS) and Highway Fuel Economy Driving Schedule (HWFET), are used in the evaluation tests. For the UDDS and HWFET driving cycles, the simulation results, the fuel consumption and the battery state of charge, using the MPC controller are compared with the simulation results using the original vehicle model in Autonomie. The MPC approach shows the feasibility to improve vehicle performance and minimize fuel consumption.

AN EXPERIMENTAL STUDY OF PARTIAL LOW RISK DEPLOYMENT IN A FIXED VEHICLE ENVIRONMENT

This study will look at the passenger air bag (PAB) performance in a fix vehicle environment using Partial Low Risk Deployment (PLRD) as a strategy. This development will follow test methods against actual baseline vehicle data and Federal Motor Vehicle Safety Standards 208 (FMVSS 208). FMVSS 208 states that PAB compliance in vehicle crash testing can be met using one of three deployment methods. The primary method suppresses PAB deployment, with the use of a seat weight sensor or occupant classification sensor (OCS), for three-year old and six-year old occupants including the presence of a child seat. A second method, PLRD allows deployment on all size occupants suppressing only for the presents of a child seat. A third method is Low Risk Deployment (LRD) which allows PAB deployment in all conditions, all statures including any/all child seats. This study outlines a PLRD development solution for achieving FMVSS 208 performance. The results of this study should provide an option for system implementation including opportunities for system efficiency and other considerations. The objective is to achieve performance levels similar too or incrementally better than the baseline vehicles National Crash Assessment Program (NCAP) Star rating. In addition, to define systemic flexibility where restraint features can be added or removed while improving occupant performance consistency to the baseline. A certified vehicles’ air bag system will typically remain in production until the vehicle platform is redesigned. The strategy to enable the PLRD hypothesis will be to first match the baseline out of position occupant performance (OOP) for the three and six-year old requirements. Second, improve the 35mph belted 5th percentile female NCAP star rating over the baseline vehicle. Third establish an equivalent FMVSS 208 certification for the 25mph unbelted 50th percentile male. FMVSS 208 high-speed requirement defines the federal minimum crash performance required for meeting frontal vehicle crash-test compliance. The intent of NCAP 5-Star rating is to provide the consumer with information about crash protection, beyond what is required by federal law. In this study, two vehicles segments were used for testing to compare and contrast to their baseline vehicles performance. Case Study 1 (CS1) used a cross over vehicle platform and Case Study 2 (CS2) used a small vehicle segment platform as their baselines. In each case study, the restraints systems were from different restraint supplier manufactures and each case contained that suppliers approach to PLRD. CS1 incorporated a downsized twins shaped bag, a carryover inflator, standard vents, and a strategic positioned bag diffuser to help disperse the flow of gas to improve OOP. The twin shaped bag with two segregated sections (lobes) to enabled high-speed baseline performance correlation on the HYGE Sled. CS2 used an A-Symmetric (square shape) PAB with standard size vents, including a passive vent, to obtain OOP similar to the baseline. The A-Symmetric shape bag also helped to enabled high-speed baseline performance improvements in HYGE Sled testing in CS2. The anticipated CS1 baseline vehicle-pulse-index (VPI) target was in the range of 65-67. However, actual dynamic vehicle (barrier) testing was overshadowed with the highest crash pulse from the previous tested vehicles with a VPI of 71. The result from the 35mph NCAP Barrier test was a solid 4-Star (4.7 Star) respectfully. In CS2, the vehicle HYGE Sled development VPI range, from the baseline was 61-62 respectively. Actual NCAP test produced a chest deflection result of 26mm versus the anticipated baseline target of 12mm. The initial assessment of this condition was thought to be due to the vehicles significant VPI increase to 67. A subsequent root cause investigation confirmed a data integrity issue due to the instrumentation. In an effort to establish a true vehicle test data point a second NCAP test was performed but faced similar instrumentation issues. As a result, the chest deflect hit the target of 12.1mm; however a femur load spike, similar to the baseline, now skewed the results. With noted level of performance improvement in chest deflection, the NCAP star was assessed as directional for 5-Star capable performance. With an actual rating of 3-Star due to instrumentation, using data extrapolation raised the ratings to 5-Star. In both cases, no structural changes were made to the surrogate vehicle and the results in each case matched their perspective baseline vehicle platforms. These results proved the PLRD is viable for further development and production implementation.