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.

Active cooling of low-concentrating hybrid PV/Thermal collectors

A series of measurements on the performance of solar cell string modules with low-concentrating CPC reflectors with a concentration factor C ˜ 4X have been carried out. To minimise the reduction in efficiency due to high cell temperatures, the modules were cooled. Four different way of cooling were tested:1) The thermal mass of the module was increased, 2) passive air cooling was used by introducing a small air gap between the module and the reflector, 3) the PV cells were cooled by a large cooling fin, 4) the module was actively cooled by circulating cold water on the back. The best performance was given with the actively cooled PV module which gave 2,2 times the output from a reference module while for the output from the module with a cooling fin the value was 1,8.Active cooling is also interesting due to the possibility of co-generation of thermal and electrical energy which is discussed in the paper. Simulations, based on climate data from Stockholm, latitude 59.4°N, show that there are good prospects for producing useful temperatures of the cooling fluid with only a slightly reduced performance of the electrical fraction of the PV thermal hybrid system.

PV-Wind Hybrid Systems for Swedish Locations

PV-Wind-Hybrid systems for stand-alone applications have the potential to be more cost efficient compared to PV-alone systems. The two energy sources can, to some extent, compensate each others minima. The combination of solar and wind should be especially favorable for locations at high latitudes such as Sweden with a very uneven distribution of solar radiation during the year. In this article PV-Wind-Hybrid systems have been studied for 11 locations in Sweden. These systems supply the household electricity for single family houses. The aim was to evaluate the system costs, the cost of energy generated by the PV-Wind-Hybrid systems, the effect of the load size and to what extent the combination of these two energy sources can reduce the costs compared to a PV-alone system. The study has been performed with the simulation tool HOMER developed by the National Renewable Energy Laboratory (NREL) for techno-economical feasibility studies of hybrid systems. The results from HOMER show that the net present costs (NPC) for a hybrid system designed for an annual load of 6000 kWh with a capacity shortage of 10% will vary between $48,000 and $87,000. Sizing the system for a load of 1800 kWh/year will give a NPC of $17,000 for the best and $33,000 for the worst location. PV-Wind-Hybrid systems are for all locations more cost effective compared to PV-alone systems. Using a Hybrid system is reducing the NPC for Borlänge by 36% and for Lund by 64%. The cost per kWh electricity varies between $1.4 for the worst location and $0.9 for the best location if a PV-Wind-Hybrid system is used.

Evaluation of a micro PV-Wind hybrid system in Nordic climate conditions

A one year data analysis for a micro PV-Wind hybrid system (0.52 kW + 1 kW), installed in Borlänge/Sweden is presented in this paper. The system performance was evaluated according the guidelines of the IEC 61724 standard. The parameters obtained allow a comparison with similar systems. The measurement data are also used to evaluate the sizing and operation of the hybrid system. In addition, the system was modelled in HOMER to study sizing options.

Evaluation of a Micro PV-Diesel Hybrid System in Tanzania

In April 2011 a monitoring system was installed to enable studies of the performance and the usage of a micro PV-Diesel Hybrid system at the Ihushi Development Center (IDC) near Mwanza in Tanzania. Estimations of the load have been obtained by a survey of installed appliances and interviews with users of installed equipment. The load profile obtained by measurements has been analyzed and compared to estimations of the energy use. Further, the system size and performance were studied.

Intelligent Algorithms for a Hybrid FuelCell/Photovoltaic Standalone System : Simulation Of Hybrid FuelCell/Photovoltaic Standalone System

The Intelligent Algorithm is designed for theusing a Battery source. The main function is to automate the Hybrid System through anintelligent Algorithm so that it takes the decision according to the environmental conditionsfor utilizing the Photovoltaic/Solar Energy and in the absence of this, Fuel Cell energy isused. To enhance the performance of the Fuel Cell and Photovoltaic Cell we used batterybank which acts like a buffer and supply the current continuous to the load. To develop the main System whlogic based controller was used. Fuzzy Logic based controller used to develop this system,because they are chosen to be feasible for both controlling the decision process and predictingthe availability of the available energy on the basis of current Photovoltaic and Battery conditions. The Intelligent Algorithm is designed to optimize the performance of the system and to selectthe best available energy source(s) in regard of the input parameters. The enhance function of these Intelligent Controller is to predict the use of available energy resources and turn on thatparticular source for efficient energy utilization. A fuzzy controller was chosen to take thedecisions for the efficient energy utilization from the given resources. The fuzzy logic basedcontroller is designed in the Matlab-Simulink environment. Initially, the fuzzy based ruleswere built. Then MATLAB based simulation system was designed and implemented. Thenthis whole proposed model is simulated and tested for the accuracy of design and performanceof the system.

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 user guide to simple monitoring and sustainable operation of PV-diesel hybrid systems : Handbook for system users and operators

This report contains a suggestion for a simple monitoring and evaluation guideline for PV-diesel hybrid systems. It offers system users a way to better understand if their system is operated in a way that will make it last for a long time. It also gives suggestions on how to act if there are signs of unfavourable use or failure. The application of the guide requires little technical equipment, but daily manual measurements. For the most part, it can be managed by pen and paper, by people with no earlier experience of power systems.The guide is structured and expressed in a way that targets PV-diesel hybrid system users with no, or limited, earlier experience of power engineering. It is less detailed in terms of motivations for certain choices and limitations, but rich in details concerning calculations, evaluation procedures and maintenance routines. A more scientific description of the guide can be found in a related journal article.

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.

Towards Presidential Rule in Ukraine : Hybrid Regime Dynamics under Semi-Presidentialism

This article sets out to analyse recent regime developments in Ukraine in relation to semi-presidentialism. The article asks: to what extent and in what ways theoretical arguments against semi-presidentialism (premier-presidential and president-parliamentary systems) are relevant for understanding the changing directions of the Ukrainian regime since the 1990s? The article also reviews the by now overwhelming evidence suggesting that President Yanukovych is turning Ukraine into a more authoritarian hybrid regime and raises the question to what extent the president-parliamentary system might serve this end. The article argues that both kinds of semi-presidentialism have, in different ways, exacerbated rather than mitigated institutional conflict and political stalemate. The return to the president-parliamentary system in 2010 – the constitutional arrangement with the most dismal record of democratisation – was a step in the wrong direction. The premier-presidential regime was by no means ideal, but it had at least two advantages. It weakened the presidential dominance and it explicitly anchored the survival of the government in parliament. The return to the 1996 constitution ties in well with the notion that President Viktor Yanukovych has embarked on an outright authoritarian path.