Heuristic solution methods for multi-attribute vehicle routing problems

Le Problème de Tournées de Véhicules (PTV) est une clé importante pour gérér efficacement des systèmes logistiques, ce qui peut entraîner une amélioration du niveau de satisfaction de la clientèle. Ceci est fait en servant plus de clients dans un temps plus court. En terme général, il implique la planification des tournées d'une flotte de véhicules de capacité donnée basée à un ou plusieurs dépôts. Le but est de livrer ou collecter une certain quantité de marchandises à un ensemble des clients géographiquement dispersés, tout en respectant les contraintes de capacité des véhicules. Le PTV, comme classe de problèmes d'optimisation discrète et de grande complexité, a été étudié par de nombreux au cours des dernières décennies. Étant donné son importance pratique, des chercheurs dans les domaines de l'informatique, de la recherche opérationnelle et du génie industrielle ont mis au point des algorithmes très efficaces, de nature exacte ou heuristique, pour faire face aux différents types du PTV. Toutefois, les approches proposées pour le PTV ont souvent été accusées d'être trop concentrées sur des versions simplistes des problèmes de tournées de véhicules rencontrés dans des applications réelles. Par conséquent, les chercheurs sont récemment tournés vers des variantes du PTV qui auparavant étaient considérées trop difficiles à résoudre. Ces variantes incluent les attributs et les contraintes complexes observés dans les cas réels et fournissent des solutions qui sont exécutables dans la pratique. Ces extensions du PTV s'appellent Problème de Tournées de Véhicules Multi-Attributs (PTVMA). Le but principal de cette thèse est d'étudier les différents aspects pratiques de trois types de problèmes de tournées de véhicules multi-attributs qui seront modélisés dans celle-ci. En plus, puisque pour le PTV, comme pour la plupart des problèmes NP-complets, il est difficile de résoudre des instances de grande taille de façon optimale et dans un temps d'exécution raisonnable, nous nous tournons vers des méthodes approcheés à base d’heuristiques.

Integrated Environment for Launch Vehicle Telemetry Data Management

The telemetry data processing operation intended for a given mission are pre-defined by an onboard telemetry configuration, mission trajectory and overall telemetry methodology have stabilized lately for ISRO vehicles. The given problem on telemetry data processing is reduced through hierarchical problem reduction whereby the sequencing of operations evolves as the control task and operations on data as the function task. The function task Input, Output and execution criteria are captured into tables which are examined by the control task and then schedules when the function task when the criteria is being met.

Site Controller: A System for Computer-Aided Civil Engineering and Construction

A revolution\0\0\0 in earthmoving, a $100 billion industry, can be achieved with three components: the GPS location system, sensors and computers in bulldozers, and SITE CONTROLLER, a central computer system that maintains design data and directs operations. The first two components are widely available; I built SITE CONTROLLER to complete the triangle and describe it here. SITE CONTROLLER assists civil engineers in the design, estimation, and construction of earthworks, including hazardous waste site remediation. The core of SITE CONTROLLER is a site modelling system that represents existing and prospective terrain shapes, roads, hydrology, etc. Around this core are analysis, simulation, and vehicle control tools. Integrating these modules into one program enables civil engineers and contractors to use a single interface and database throughout the life of a project.

Motion planning of autonomous vehicles in a non-autonomous vehicle environment without speed lanes

Planning is one of the key problems for autonomous vehicles operating in road scenarios. Present planning algorithms operate with the assumption that traffic is organised in predefined speed lanes, which makes it impossible to allow autonomous vehicles in countries with unorganised traffic. Unorganised traffic is though capable of higher traffic bandwidths when constituting vehicles vary in their speed capabilities and sizes. Diverse vehicles in an unorganised exhibit unique driving behaviours which are analysed in this paper by a simulation study. The aim of the work reported here is to create a planning algorithm for mixed traffic consisting of both autonomous and non-autonomous vehicles without any inter-vehicle communication. The awareness (e.g. vision) of every vehicle is restricted to nearby vehicles only and a straight infinite road is assumed for decision making regarding navigation in the presence of multiple vehicles. Exhibited behaviours include obstacle avoidance, overtaking, giving way for vehicles to overtake from behind, vehicle following, adjusting the lateral lane position and so on. A conflict of plans is a major issue which will almost certainly arise in the absence of inter-vehicle communication. Hence each vehicle needs to continuously track other vehicles and rectify plans whenever a collision seems likely. Further it is observed here that driver aggression plays a vital role in overall traffic dynamics, hence this has also been factored in accordingly. This work is hence a step forward towards achieving autonomous vehicles in unorganised traffic, while similar effort would be required for planning problems such as intersections, mergers, diversions and other modules like localisation.

Solving the Vehicle Routing Problem with Genetic ALgorithm and Simulated Annealing

This Thesis Work will concentrate on a very interesting problem, the Vehicle Routing Problem (VRP). In this problem, customers or cities have to be visited and packages have to be transported to each of them, starting from a basis point on the map. The goal is to solve the transportation problem, to be able to deliver the packages-on time for the customers,-enough package for each Customer,-using the available resources- and – of course - to be so effective as it is possible.Although this problem seems to be very easy to solve with a small number of cities or customers, it is not. In this problem the algorithm have to face with several constraints, for example opening hours, package delivery times, truck capacities, etc. This makes this problem a so called Multi Constraint Optimization Problem (MCOP). What’s more, this problem is intractable with current amount of computational power which is available for most of us. As the number of customers grow, the calculations to be done grows exponential fast, because all constraints have to be solved for each customers and it should not be forgotten that the goal is to find a solution, what is best enough, before the time for the calculation is up. This problem is introduced in the first chapter: form its basics, the Traveling Salesman Problem, using some theoretical and mathematical background it is shown, why is it so hard to optimize this problem, and although it is so hard, and there is no best algorithm known for huge number of customers, why is it a worth to deal with it. Just think about a huge transportation company with ten thousands of trucks, millions of customers: how much money could be saved if we would know the optimal path for all our packages.Although there is no best algorithm is known for this kind of optimization problems, we are trying to give an acceptable solution for it in the second and third chapter, where two algorithms are described: the Genetic Algorithm and the Simulated Annealing. Both of them are based on obtaining the processes of nature and material science. These algorithms will hardly ever be able to find the best solution for the problem, but they are able to give a very good solution in special cases within acceptable calculation time.In these chapters (2nd and 3rd) the Genetic Algorithm and Simulated Annealing is described in details, from their basis in the “real world” through their terminology and finally the basic implementation of them. The work will put a stress on the limits of these algorithms, their advantages and disadvantages, and also the comparison of them to each other.Finally, after all of these theories are shown, a simulation will be executed on an artificial environment of the VRP, with both Simulated Annealing and Genetic Algorithm. They will both solve the same problem in the same environment and are going to be compared to each other. The environment and the implementation are also described here, so as the test results obtained.Finally the possible improvements of these algorithms are discussed, and the work will try to answer the “big” question, “Which algorithm is better?”, if this question even exists.

Speed prediction for triggering vehicle activated signs

Accurate speed prediction is a crucial step in the development of a dynamic vehcile activated sign (VAS). A previous study showed that the optimal trigger speed of such signs will need to be pre-determined according to the nature of the site and to the traffic conditions. The objective of this paper is to find an accurate predictive model based on historical traffic speed data to derive the optimal trigger speed for such signs. Adaptive neuro fuzzy (ANFIS), classification and regression tree (CART) and random forest (RF) were developed to predict one step ahead speed during all times of the day. The developed models were evaluated and compared to the results obtained from artificial neural network (ANN), multiple linear regression (MLR) and naïve prediction using traffic speed data collected at four sites located in Sweden. The data were aggregated into two periods, a short term period (5-min) and a long term period (1-hour). The results of this study showed that using RF is a promising method for predicting mean speed in the two proposed periods.. It is concluded that in terms of performance and computational complexity, a simplistic input features to the predicitive model gave a marked increase in the response time of the model whilse still delivering a low prediction error.

Multivalued adaptive neuro-fuzzy controller for robot vehicle - art. no. 1406

Robotic vehicle navigation in unstructured and uncertain environments is still a challenge. This paper presents the implementation of a multivalued neurofuzzy controller for autonomous ground vehicle (AGVs) in indoor environments. The control system consists of a hierarchy of mobile robot using multivalued adaptive neuro-fuzzy inference system behaviors.

Development, characterization and clinical use of a biodegradable composite scaffold for bone engineering in oro-maxillo-facial surgery

We have developed a biodegradable composite scaffold for bone tissue engineering applications with a pore size and interconnecting macroporosity similar to those of human trabecular bone. The scaffold is fabricated by a process of particle leaching and phase inversion from poly(lactide-co-glycolide) (PLGA) and two calcium phosphate (CaP) phases both of which are resorbable by osteoclasts; the first a particulate within the polymer structure and the second a thin ubiquitous coating. The 3-5 mu m thick osteoconductive surface CaP abrogates the putative foreign body giant cell response to the underlying polymer, while the internal CaP phase provides dimensional stability in an otherwise highly compliant structure. The scaffold may be used as a biomaterial alone, as a carrier for cells or a three-phase drug delivery device. Due to the highly interconnected macroporosity ranging from 81% to 91%, with macropores of 0.8 similar to 1.8 mm, and an ability to wick up blood, the scaffold acts as both a clot-retention device and an osteoconductive support for host bone growth. As a cell delivery vehicle, the scaffold can be first seeded with human mesenchymal cells which can then contribute to bone formation in orthotopic implantation sites, as we show in immune-compromised animal hosts. We have also employed this scaffold in both lithomorph and particulate forms in human patients to maintain alveolar bone height following tooth extraction, and augment alveolar bone height through standard sinus lift approaches. We provide a clinical case report of both of these applications; and we show that the scaffold served to regenerate sufficient bone tissue in the wound site to provide a sound foundation for dental implant placement. At the time of writing, such implants have been in occlusal function for periods of up to 3 years in sites regenerated through the use of the scaffold.

Low-cost PWM speed controller for an electric mini-baja type vehicle

This paperwork presents a Pulse Width Modulation (PWM) speed controller for an electric mini-baja-type car. A battery-fed 1-kW three-phase induction motor provides the electric vehicle traction. The open-loop speed control is implemented with an equal voltage/frequency ratio, in order to maintain a constant amount of torque on all velocities. The PWM is implemented by a low-cost 8-bit microcontroller provided with optimized ROM charts for distinct speed value implementations, synchronized transition between different charts and reduced odd harmonics generation. This technique was implemented using a single passenger mini-baja vehicle, and the essays have shown that its application resulted on reduced current consumption, besides eliminating mechanical parts. Copyright © 2007 by ABCM.

An investigation into the loss of the Brazilian space programme's launch vehicle VLS-1 V03

There has been a rapid increase in the complexity and integration of many safety-critical systems. In consequence, it is becoming increasingly difficult to identify the causes of incidents and accidents back through the complex interactions that lead to an adverse event. At the same time, there is a growing appreciation of the need to consider a broad range of contextual factors in the aftermath of any mishap. A number of regulators, operators and research teams have responded to these developments by proposing novel techniques to support the analysis of complex, safety-critical incidents. It is important to illustrate these different approaches by applying them to a number of common case studies. The following pages, therefore, show how STAMP and AcciMap might support the Serviço Público Federal investigation into the explosion and fire of the Brazilian launch vehicle VLS-1 VO3. © 2006 Elsevier Ltd. All rights reserved.

Modeling of a MIT for the application of a frequency inverter of the electric vehicle

Nowadays, drives that use a combination of induction motors and frequency inverters are very common, a fact due to the financial practicality and viability in purchasing and operating that system. This system modeling and simulation becomes important when it wants to evaluate the performance, to calculate and correct parameters, and it has a fundamental role in functionality and viability analysis for application of new configurations and technologies. This work is about to elaborate a simple induction motor model based in the torque versus speed characteristic, using the linearization method for application in a specific operation range to be controlled by a frequency inverter. © 2011 Springer-Verlag Berlin Heidelberg.

Experimental Investigation of the Hydrodynamic Coefficients of a Remotely Operated Vehicle Using a Planar Motion Mechanism

The determination of hydrodynamic coefficients of full scale underwater vehicles using system identification (SI) is an extremely powerful technique. The procedure is based on experimental runs and on the analysis of on-board sensors and thrusters signals. The technique is cost effective and it has high repeatability; however, for open-frame underwater vehicles, it lacks accuracy due to the sensors' noise and the poor modeling of thruster-hull and thruster-thruster interaction effects. In this work, forced oscillation tests were undertaken with a full scale open-frame underwater vehicle. These conducted tests are unique in the sense that there are not many examples in the literature taking advantage of a PMM installation for testing a prototype and; consequently, allowing the comparison between the experimental results and the ones estimated by parameter identification. The Morison's equation inertia and drag coefficients were estimated with two parameter identification methods, that is, the weighted and the ordinary least-squares procedures. It was verified that the in-line force estimated from Morison's equation agrees well with the measured one except in the region around the motion inversion points. On the other hand, the error analysis showed that the ordinary least-squares provided better accuracy and, therefore, was used to evaluate the ratio between inertia and drag forces for a range of Keulegan-Carpenter and Reynolds numbers. It was concluded that, although both experimental and estimation techniques proved to be powerful tools for evaluation of an open-frame underwater vehicle's hydrodynamic coefficients, the research provided a rich amount of reference data for comparison with reduced models as well as for dynamic motion simulation of ROVs. [DOI: 10.1115/1.4004952]

Performance of polymeric reinforcements in vehicle structures submitted to frontal impact

Preformed structural reinforcements have shown good performance in crash tests, where the great advantage is their weight. These reinforcements are designed with the aim of increasing the rigidity of regions with large deformations, thus stabilising sections of the vehicle that work as load path during impact. The objective of this work is to show the application of structural reinforcements made of polymeric material PA66 in the field of vehicle safety, through finite element simulations. Simulations of frontal impact at 50 km/h and in ODB (offset deformable barrier) at 57 km/h configurations (standards such as ECE R-94 and ECE R-12) were performed in the software LS-DYNA R (R) and MADYMO (R). The simulations showed that the use of polymeric reinforcements leads to a 70% reduction in A-pillar intrusion, a 65% reduction in the displacement of the steering column and a 59% reduction in the deformation in the region of the occupant legs and feet. The level of occupant injuries was analysed by MADYMO (R) software, and a reduction of 23.5% in the chest compression and 80% in the tibia compression were verified. According to the standard, such conditions lead to an improvement in the occupant safety in a vehicle collision event.

Column generation for a multitrip vehicle routing problem with time windows, driver work hours, and heterogeneous fleet

This study addresses a vehicle routing problem with time windows, accessibility restrictions on customers, and a fleet that is heterogeneous with regard to capacity and average speed. A vehicle can performmultiple routes per day, all starting and ending at a single depot, and it is assigned to a single driverwhose totalwork hours are limited.Acolumn generation algorithmis proposed.The column generation pricing subproblem requires a specific elementary shortest path problem with resource constraints algorithm to address the possibility for each vehicle performingmultiple routes per day and to address the need to set the workday’s start time within the planning horizon. A constructive heuristic and a metaheuristic based on tabu search are also developed to find good solutions.

Engineering Complex Computational Ecosystems

Self-organising pervasive ecosystems of devices are set to become a major vehicle for delivering infrastructure and end-user services. The inherent complexity of such systems poses new challenges to those who want to dominate it by applying the principles of engineering. The recent growth in number and distribution of devices with decent computational and communicational abilities, that suddenly accelerated with the massive diffusion of smartphones and tablets, is delivering a world with a much higher density of devices in space. Also, communication technologies seem to be focussing on short-range device-to-device (P2P) interactions, with technologies such as Bluetooth and Near-Field Communication gaining greater adoption. Locality and situatedness become key to providing the best possible experience to users, and the classic model of a centralised, enormously powerful server gathering and processing data becomes less and less efficient with device density. Accomplishing complex global tasks without a centralised controller responsible of aggregating data, however, is a challenging task. In particular, there is a local-to-global issue that makes the application of engineering principles challenging at least: designing device-local programs that, through interaction, guarantee a certain global service level. In this thesis, we first analyse the state of the art in coordination systems, then motivate the work by describing the main issues of pre-existing tools and practices and identifying the improvements that would benefit the design of such complex software ecosystems. The contribution can be divided in three main branches. First, we introduce a novel simulation toolchain for pervasive ecosystems, designed for allowing good expressiveness still retaining high performance. Second, we leverage existing coordination models and patterns in order to create new spatial structures. Third, we introduce a novel language, based on the existing ``Field Calculus'' and integrated with the aforementioned toolchain, designed to be usable for practical aggregate programming.