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.

The Optimal trigger speed of vehicle activated signs

The thesis aims to elaborate on the optimum trigger speed for Vehicle Activated Signs (VAS) and to study the effectiveness of VAS trigger speed on drivers’ behaviour. Vehicle activated signs (VAS) are speed warning signs that are activated by individual vehicle when the driver exceeds a speed threshold. The threshold, which triggers the VAS, is commonly based on a driver speed, and accordingly, is called a trigger speed. At present, the trigger speed activating the VAS is usually set to a constant value and does not consider the fact that an optimal trigger speed might exist. The optimal trigger speed significantly impacts driver behaviour. In order to be able to fulfil the aims of this thesis, systematic vehicle speed data were collected from field experiments that utilized Doppler radar. Further calibration methods for the radar used in the experiment have been developed and evaluated to provide accurate data for the experiment. The calibration method was bidirectional; consisting of data cleaning and data reconstruction. The data cleaning calibration had a superior performance than the calibration based on the reconstructed data. To study the effectiveness of trigger speed on driver behaviour, the collected data were analysed by both descriptive and inferential statistics. Both descriptive and inferential statistics showed that the change in trigger speed had an effect on vehicle mean speed and on vehicle standard deviation of the mean speed. When the trigger speed was set near the speed limit, the standard deviation was high. Therefore, the choice of trigger speed cannot be based solely on the speed limit at the proposed VAS location. The optimal trigger speeds for VAS were not considered in previous studies. As well, the relationship between the trigger value and its consequences under different conditions were not clearly stated. The finding from this thesis is that the optimal trigger speed should be primarily based on lowering the standard deviation rather than lowering the mean speed of vehicles. Furthermore, the optimal trigger speed should be set near the 85th percentile speed, with the goal of lowering the standard deviation.

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.

A data driven approach for automating vehicle activated signs

Vehicle activated signs (VAS) display a warning message when drivers exceed a particular threshold. VAS are often installed on local roads to display a warning message depending on the speed of the approaching vehicles. VAS are usually powered by electricity; however, battery and solar powered VAS are also commonplace. This thesis investigated devel-opment of an automatic trigger speed of vehicle activated signs in order to influence driver behaviour, the effect of which has been measured in terms of reduced mean speed and low standard deviation. A comprehen-sive understanding of the effectiveness of the trigger speed of the VAS on driver behaviour was established by systematically collecting data. Specif-ically, data on time of day, speed, length and direction of the vehicle have been collected for the purpose, using Doppler radar installed at the road. A data driven calibration method for the radar used in the experiment has also been developed and evaluated. Results indicate that trigger speed of the VAS had variable effect on driv-ers’ speed at different sites and at different times of the day. It is evident that the optimal trigger speed should be set near the 85th percentile speed, to be able to lower the standard deviation. In the case of battery and solar powered VAS, trigger speeds between the 50th and 85th per-centile offered the best compromise between safety and power consump-tion. Results also indicate that different classes of vehicles report differ-ences in mean speed and standard deviation; on a highway, the mean speed of cars differs slightly from the mean speed of trucks, whereas a significant difference was observed between the classes of vehicles on lo-cal roads. A differential trigger speed was therefore investigated for the sake of completion. A data driven approach using Random forest was found to be appropriate in predicting trigger speeds respective to types of vehicles and traffic conditions. The fact that the predicted trigger speed was found to be consistently around the 85th percentile speed justifies the choice of the automatic model.

Review of the effectiveness of vehicle activated signs

This paper reviews the effectiveness of vehicle activated signs. Vehicle activated signs are being reportedly used in recent years to display dynamic information to road users on an individual basis in order to give a warning or inform about a specific event. Vehicle activated signs are triggered individually by vehicles when a certain criteria is met. An example of such criteria is to trigger a speed limit sign when the driver exceeds a pre-set threshold speed. The preset threshold is usually set to a constant value which is often equal, or relative, to the speed limit on a particular road segment. This review examines in detail the basis for the configuration of the existing sign types in previous studies and explores the relation between the configuration of the sign and their impact on driver behavior and sign efficiency. Most of previous studies showed that these signs have significant impact on driver behavior, traffic safety and traffic efficiency. In most cases the signs deployed have yielded reductions in mean speeds, in speed variation and in longer headways. However most experiments reported within the area were performed with the signs set to a certain static configuration within applicable conditions. Since some of the aforementioned factors are dynamic in nature, it is felt that the configurations of these signs were thus not carefully considered by previous researchers and there is no clear statement in the previous studies describing the relationship between the trigger value and its consequences under different conditions. Bearing in mind that different designs of vehicle activated signs can give a different impact under certain conditions of road, traffic and weather conditions the current work suggests that variable speed thresholds should be considered instead.

Data based Calibration System for Radar used by Vehicle Activated Signs

The accurate measurement of a vehicle’s velocity is an essential feature in adaptive vehicle activated sign systems. Since the velocities of the vehicles are acquired from a continuous wave Doppler radar, the data collection becomes challenging. Data accuracy is sensitive to the calibration of the radar on the road. However, clear methodologies for in-field calibration have not been carefully established. The signs are often installed by subjective judgment which results in measurement errors. This paper develops a calibration method based on mining the data collected and matching individual vehicles travelling between two radars. The data was cleaned and prepared in two ways: cleaning and reconstructing. The results showed that the proposed correction factor derived from the cleaned data corresponded well with the experimental factor done on site. In addition, this proposed factor showed superior performance to the one derived from the reconstructed data.

Triggering Solar-Powered Vehicle Activated Signs using Self Organising Maps with K-means

Solar-powered vehicle activated signs (VAS) are speed warning signs powered by batteries that are recharged by solar panels. These signs are more desirable than other active warning signs due to the low cost of installation and the minimal maintenance requirements. However, one problem that can affect a solar-powered VAS is the limited power capacity available to keep the sign operational. In order to be able to operate the sign more efficiently, it is proposed that the sign be appropriately triggered by taking into account the prevalent conditions. Triggering the sign depends on many factors such as the prevailing speed limit, road geometry, traffic behaviour, the weather and the number of hours of daylight. The main goal of this paper is therefore to develop an intelligent algorithm that would help optimize the trigger point to achieve the best compromise between speed reduction and power consumption. Data have been systematically collected whereby vehicle speed data were gathered whilst varying the value of the trigger speed threshold. A two stage algorithm is then utilized to extract the trigger speed value. Initially the algorithm employs a Self-Organising Map (SOM), to effectively visualize and explore the properties of the data that is then clustered in the second stage using K-means clustering method. Preliminary results achieved in the study indicate that using a SOM in conjunction with K-means method is found to perform well as opposed to direct clustering of the data by K-means alone. Using a SOM in the current case helped the algorithm determine the number of clusters in the data set, which is a frequent problem in data clustering.

Moose-vehicle collisions (MVC) in the State of Maine from 1992-2004

http://digitalcommons.colby.edu/atlasofmaine2005/1004/thumbnail.jpg

ESTIMATED NUMBER AND LOCATION OF FUTURE MOOSE-VEHICLE COLLISIONS (MVC) IN MAINE

http://digitalcommons.colby.edu/atlasofmaine2005/1018/thumbnail.jpg

Estimated Number and Location of Future Moose-Vehicle Collisions (MVC) in Maine

Moose (Alces alces) are a keystone herbivore in Maine. Because of the large number of rural roads in Maine, there is a high rate of moose-vehicle collisions (MVCs), which is increasing. On-road encounters with animals resulted in 231 fatalities in the United States in 1999. Because of the fatality of MVCs, it is important to know where they are most likely to occur. I used GIS analysis to estimate where future MVCs would occur, factoring in the variables of land cover suitability for moose, distance from water bodies, locations of past MVCs, and speed limits on the roads. I ran four different analyses, each one weighting the variables equally. I also ran a regression to determine if increasing road speed was associated with the increase in the number of MVCs per length of road. There was not a strong positive relationship between the number of MVCs per length of road and the speed limit, but it was interesting to note that there were more MVCs per length of road on 35mph and 40mph roads than on 45, 50, 55 or 65mph roads. Future research on MVCs would benefit from the inclusion of include moose population density and road traffic data.

Ice as a vehicle for diarrheagenic Escherichia coli

In a recent study of the microbiological quality of commercial ice, 50 Escherichia coli isolates belonging to different serotypes were found. The potential hazard from these isolates was examined by testing their adherence patterns ill HeLa cells and searching for the presence of DNA sequences related to E. coli virulence properties. Twelve potentially diarrheagenic isolates were found and classified as enteroaggregative E. coli (EAEC) based oil their ability to produce aggregative adherence to HeLa cells. The remaining isolates were devoid of the virulence properties searched for. The EAEC isolates belonged to 10 different serotypes, among which O128ab:H35 is often found in diarrheic feces. None of these isolates reacted with a specific EAEC DNA probe or carried any of the known EAEC virulence genes. These data indicate that ice may be all important vehicle for transmission of enteropathogens, especially of the EAEC group. (C) 2003 Elsevier B.V. All rights reserved.

A study of reverse logistics flow management in vehicle battery industries in the midwest of the state of São Paulo (Brazil)

Having the objective of minimizing costs and improving their image in the consumer and export market, car battery industries began to seek environmental alternatives geared towards sustainable development. Reverse logistics flow represents an unprecedented tool for the economic and operational development of company activities, as well as a differential in the search for competitive advantages through environmentally correct practices. The aim of this paper is to describe the reverse logistics chain adopted by automotive battery industries in the midwest of the state of São Paulo, proposing a reverse logistics framework for small manufacturers that creates actions aimed at not harming the environment. (C) 2010 Elsevier Ltd. All rights reserved.

Influence of the type of vehicle and limit of obturation on apical and periapical tissue response in dogs' teeth after root canal filling with mineral trioxide aggregate

The purpose of this study was to investigate the influence of the type of vehicle (distilled water or propyleneglycol) on the response of apical tissues of dogs' teeth after root canal filling with mineral trioxide aggregate (MTA) at two different limits. Forty roots of incisors and premolars of two adult dogs were used. After pulpectomy, the root canals were prepared biomechanically, and the roots had the apical cemental barrier penetrated with a #15 K-file and widened to a #25 K-file. The root canals were assigned to four groups according to the vehicle used for MTA (ProRoot-MTA; Tulsa Dental, Tulsa, OK) preparation and the limit of root canal filling: group 1, filling with MTA/distilled water to the limit of the cemental canal; group 2, overfilling with MTA/distilled water, group 3, filling with MTA/propyleneglycol to the limit of the cemental canal; and group 4, overfilling with MTAlpropyleneglycol. The animals were killed by anesthetic overdose 90 days after endodontic treatment and the anatomic pieces were prepared for histomorphological analysis. The sections were stained with hematoxylin and eosin and Brown and Brenn techniques. The results showed that MTA pastes prepared with either distilled water or propyleneglycol as vehicles had similar biological behavior (p > 0.05); root fillings placed at the cemental canal limit showed better results than the overfillings (p = 0.01), and MTA/propyleneglycol paste was more easily placed into the root canals than MTA/distilled water paste.

Influences of the load centre of gravity on heavy vehicle acceleration

The aim of this paper is to analyse the influence of the load centre of gravity on heavy vehicle acceleration. This analysis is done through a method in which a vehicle centre of gravity map is used. A model for the driving force is presented for bus, truck and tractor-semi trailer combinations. The proposed model takes into consideration the resistance forces (drag, rolling resistance, translation and rotation acceleration, climbing resistance) and the 4 X 2 traction system. The positions of the vehicle centre of gravity as a function of the position of the load centre of gravity are determined. The vehicle acceleration is calculated based on the position of the load centre of gravity. This study analyses the acceleration of one of the Mercedes-Benz do Brasil tractor-semitrailer vehicle. A comparison of the acceleration for different maximum adhesion coefficients and ramps are presented, showing new results. An example showing the variations of the load centre of gravity position with the acceleration time and distance is provided. The load centre of gravity position is important for vehicle safety and the efficiency and economy in the transportation of the load.