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.

University Timetabling using Genetic Algorithm

The field of automated timetabling and scheduling meeting all the requirementsthat we call constraints is always difficult task and already proved as NPComplete. The idea behind my research is to implement Genetic Algorithm ongeneral scheduling problem under predefined constraints and check the validityof results, and then I will explain the possible usage of other approaches likeexpert systems, direct heuristics, network flows, simulated annealing and someother approaches. It is observed that Genetic Algorithm is good solutiontechnique for solving such problems. The program written in C++ and analysisis done with using various tools explained in details later.

Environmental Objectives, Cost Efficiency, and Multivariate Stochastic Control

This paper is concerned with the cost efficiency in achieving the Swedish national air quality objectives under uncertainty. To realize an ecologically sustainable society, the parliament has approved a set of interim and long-term pollution reduction targets. However, there are considerable quantification uncertainties on the effectiveness of the proposed pollution reduction measures. In this paper, we develop a multivariate stochastic control framework to deal with the cost efficiency problem with multiple pollutants. Based on the cost and technological data collected by several national authorities, we explore the implications of alternative probabilistic constraints. It is found that a composite probabilistic constraint induces considerably lower abatement cost than separable probabilistic restrictions. The trend is reinforced by the presence of positive correlations between reductions in the multiple pollutants.

Förlorad i övergången från aritmetik till algebra : Hur gymnasieelever översätter aritmetik till algebra

The aim of this thesis is to look for signs of students’ understanding of algebra by studying how they make the transition from arithmetic to algebra. Students in an Upper Secondary class on the Natural Science program and Science and Technology program were given a questionnaire with a number of algebraic problems of different levels of difficulty. Especially important for the study was that students leave comments and explanations of how they solved the problems. According to earlier research, transitions are the most critical steps in problem solving. The Algebraic Cycle is a theoretical tool that can be used to make different phases in problem solving visible. To formulate and communicate how the solution was made may lead to students becoming more aware of their thought processes. This may contribute to students gaining more understanding of the different phases involved in mathematical problem solving, and to students becoming more successful in mathematics in general.The study showed that the students could solve mathematical problems correctly, but that they in just over 50% of the cases, did not give any explanations to their solutions.

Paper dimensional stability in sheet-fed offset printing : Papperets dimensionsstabilitet i en arkoffsetpress

In offset printing, dampening solution is used to create a good balance in the process. If too much water is transferred to the paper, the sheet can change its size between the printing units, due to water absorption, and cause a problem with the colour register. This phenomenon is usually referred to as fanout. In this degree project, an investigation was made to see if the paper dimensions changed through its way in the sheet-fed printing process. The instrument Luchs Register Measuring Systems (Lynx) was used, and a method for measuring if the paper changed its dimensions with this instrument, was developed. Paper qualities with three different grammages were used, 90, 130 and 250 gsm. This investigation showed that all paper qualities changed their size with widening in the gripper edge in the range of 10 - 70 µm and in the trailing edge the increase was 10 - 130 µm. The elongations of the papers were in the range of 10- 300 µm. The papers with lowest grammage changed more than the heavier. To see if the print had been affected of the widening and elongation, print quality parameters like relative contrast, dot gain and mottle were correlated with the Lynx data from the sheets. The group of papers that gave correlations were in 130 gsm. The sheets had visual doubling and the combined standard deviation from the Lynx marks K3, K5 and K21 correlated with dot gain. When the variations increased so did the dot gain and this indicates that the doubling was due to the widening. There was also a correlation between the standard deviation from K3 and Mottle. The sheets widened with an average of 30 µm in the gripper edge and since there probably were doubling due to widening it also affected the Mottle values. What the widening depends on is hard to tell. Since widening was so small, it could be due to water absorption, papers being ironed out or maybe the sheets have been flattened out. It probably needs a more detailed investigation to find out what causes the widening. Further investigations about how print quality is affected by the register accuracy of a printing machine should include a print form with measuring areas close to the Lynx marks. The measuring areas should contain fine hairlines, negative text printed with at least two colours and some pictures to evaluate together with standard measuring should give a good knowledge about the subject.

Omvårdnad vid förstoppning hos dementa personer : undersköterskors och vårdbiträdens reflektioner

Constipation is a common problem for people with dementia and it may result in discomfort, suffering and lower quality of life. Nurses in municipal nursing homes have difficult to observe and prevent these problems because they do not participate in the daily caring work. The aim of this study was to illustrate the nurse assistants’ reflections about the care they gave people with dementia and constipation. Main questions vas how they became aware of such problems and what they did when someone had problem with constipation. It also asked about their methods to prevent constipation and if they thought anything could be done better in the future. The method used was a qualitative interview study. The study included eight nurse assistants who worked in municipal nursing homes for people with dementia. The interviews where tape recorded, then written and analysed with a phenomenological method. The result illustrate how the nurse assistants used their sense for observing and their personal feelings to share the experience with the person. This gave trust and renders possibility to get knowledge and also gave opportunity to prevent problems and give help, in a way that not reduced dignity for the person. Bowel control, fluid, food and the possibility to get out for a walk was important. It was also important to have enough time for sharing reflections. Small units gave possibility to personal knowledge.

Alternativa förpackningsmaterial och konstruktioner för »Hackman tools«-serien

Choosing a new plastic material for a container includes several different steps. In this case,the Finnish company Hackman needed a new type of packaging material for theircutlery- and kitchentool series »Hackman tools«. The project was carried out in cooperationwith the design agency Ytterborn & Fuentes, which has Hackman as a client.Several different demands were put on the material in order to fulfill as many of the clientswishes as possible. The most urgent problem with the existing container was the difficultysfor the customer to clearly see the contents in the container. Because of this problemthe customer tried to open the container in the shop. To avoid this from happening,Hackman wanted a more transparent plastic material that still fulfilled all other necessaryproperties such as strength, viscosity, printability, sealability and exhaustion strength.The final result and recommendation of a polypropylen-plastic (Evacast) was based ondetailed studies of packaging plastics and their properties as well as discussions with plasticconvertersand suppliers. The recommended plastic is avaliable in several different modelsthat fulfill all demands on material properties, environmental aspects, cost aspects and transparency.Apart from the material problem the project also included drafting some sketches and ideason new construction solutions for the container. The construction of the exsisting containerwas also a problem because of its complexity. As a result of the change of material it has beenpossible to simplify the construction.

Troubleshooting med avseende på avsättningar på gummiduk, Bobergs tryckeri AB

Bobergs printing house in Falun has during some time had problems regarding deposits on blankets intheirs Müller Martini UV-printing presses. Deposits appear in both image areas and non-image areas.These areas have been analyzed and the deposits on non-image areas contain chalk, clay and talc. Thequestion remains how these material bond to the blanket surface. The chalk and clay comes from thepaper. The talc comes from the ink. Deposits from image areas contain pigment and talc from the printingink. The dampening water has also been analyzed. The result shows some sort of problem with thehardness regulator for the clean water. The pH-level should be increased a few steps.

Branch and Bound Algorithm for Multiprocessor Scheduling

The multiprocessor task graph scheduling problem has been extensively studied asacademic optimization problem which occurs in optimizing the execution time of parallelalgorithm with parallel computer. The problem is already being known as one of the NPhardproblems. There are many good approaches made with many optimizing algorithmto find out the optimum solution for this problem with less computational time. One ofthem is branch and bound algorithm.In this paper, we propose a branch and bound algorithm for the multiprocessor schedulingproblem. We investigate the algorithm by comparing two different lower bounds withtheir computational costs and the size of the pruned tree.Several experiments are made with small set of problems and results are compared indifferent sections.

En applikationsinfrastruktur för massutskick av e-post

In today's society it is becoming more and more important with direct marketing. Some of the direct marketing is done through e-mail, in which companies see an easy way to advertise himself. I did this thesis work at WebDoc Systems. They have a product that creates web documents directly in your browser, also called CMS. The CMS has a module for sending mass e-mail, but this module does not function properly and WebDoc Systems customers are dissatisfied with that part of the product. The problem with the module was that sometimes it didn't send the e-mail, and that it was not possible to obtain some form of follow-up information on the e-mail. The goal of this work was to develop a Web service that could easily send e-mail to many receivers, just as easily be able to view statistics on how mailing has gone. The first step was to do a literature review to get a good picture of available programming platforms, but also to be able create a good application infrastructure. The next step was to implement this design and improve it over time by using an iterative development methodology. The result was an application infrastructure that consists of three main parts and a plugin interface. The parts that were implemented were a Web service application, a Web application and a Windows service application. The three elements cooperate with each other and share a database, and plugins.

Separation and Execution of graphical engine on a cross platform IDE to enhance performance

“Biosim” is a simulation software which works to simulate the harvesting system.This system is able to design a model for any logistic problem with the combination of several objects so that the artificial system can show the performance of an individual model. The system will also describe the efficiency, possibility to be chosen for real life application of that particular model. So, when any one wish to setup a logistic model like- harvesting system, in real life he/she may be noticed about the suitable prostitution for his plants and factories as well as he/she may get information about the least number of objects, total time to complete the task, total investment required for his model, total amount of noise produced for his establishment in advance. It will produce an advance over view for his model. But “Biosim” is quite slow .As it is an object based system, it takes long time to make its decision. Here the main task is to modify the system so that it can work faster than the previous. So, the main objective of this thesis is to reduce the load of “Biosim” by making some modification of the original system as well as to increase its efficiency. So that the whole system will be faster than the previous one and performs more efficiently when it will be applied in real life. Theconcept is to separate the execution part of ”Biosim” form its graphical engine and run this separated portion in a third generation language platform. C++ is chosenhere as this external platform. After completing the proposed system, results with different models have been observed. The results show that, for any type of plants of fields, for any number of trucks, the proposed system is faster than the original system. The proposed system takes at least 15% less time “Biosim”. The efficiency increase with the complexity of than the original the model. More complex the model, more efficient the proposed system is than original “Biosim”.Depending on the complexity of a model, the proposed system can be 56.53 % faster than the original “Biosim”.

Small-Scale Farmers Land Use and Socioeconomic Situation in the Mount Elgon District in Northwestern Kenya : A Minor Field Study - Combined Field Mapping and Interview

This Minor Field Study was carried out during November and December in 2011 in the Mount Elgon District in Western Kenya. The objective was to examine nine small-scale farming household´s land use and socioeconomic situation when they have joined a non-governmental organization (NGO) project, which specifically targets small-scale farming households to improve land use system and socioeconomic situation by the extension of soil and water conservation measures. The survey has worked along three integral examinations methods which are mapping and processing data using GIS, semi structured interviews and literature studies.   This study has adopted a theoretical approach referred to as political ecology, in which landesque capital is a central concept. The result shows that all farmers, except one, have issues with land degradation. However, the extent of the problem and also implemented sustainable soil and water conservation measures were diverse among the farmers. The main causes of this can both be linked to how the farmers themselves utilized their farmland and how impacts from the climate change have modified the terms of the farmers working conditions. These factors have consequently resulted in impacts on the informants’ socioeconomic conditions. Furthermore it was also registered that social and economic elements, in some cases, were the causes of how the farmers manage their farmland. The farmer who had no significant problem with soil erosion had invested in trees and opportunities to irrigate the farmland. In addition, it was also recorded that certain farmers had invested in particular soil and water conservation measures without any significant result. This was probably due to the time span these land measures cover before they start to generate revenue.  The outcome of this study has traced how global, national and local elements exist in a context when it comes to the conditions of the farmers´ land use and their socioeconomic situation. The farmers atMt.Elgon are thereby a component of a wider context when they are both contributory to their socioeconomic situation, mainly due to their land management, and also exposed to core-periphery relationships on which the farmers themselves have no influence.

Portals for microenterprises in rural area : two cases

Research has shown that microenterprises have ability to survive and grow with the support of portals that include eCcommerce. However, almost no research has demonstrated how it’s done and what support microenterprises want. Results of our study shows that the portals have to be improved to support the use of advanced ICT applications, make it usable to use, and give more time for core business for the participating microenterprises. We have seen that portals have to solve problem with the technical solution and the process of payment. The network building activities in the portals do not happen in such extent that we have expected based on previous research. If portals will get businesses to grow in microenterprises, we propose that in addition to providing access to advanced ICT applications need to climbs one step higher in the DTI ladder and create more of eCommerce to increase sales in a greater market. We also propose that portals which support cooperation between microenterprises in rural areas from different branches have the best chances to succeed in the future.

Följsamhet till råd om egenvård hos patienter med diabetes typ 2 : En litteraturöversikt

Bakgrund: Diabetes typ 2 är en endokrin sjukdom och ett globalt hälsoproblem, där antalet insjuknande personer ökar kraftigt. Behandlingen vid diabetes typ 2 utgörs till största del av egenvård vilket ställer stora krav på patienten och på sjukvården. En bristande följsamhet till råd om egenvård kan leda till sämre hälsa för patienten och ökade kostnader för samhället. Syfte: Syftet med denna litteraturöversikt var att beskriva vilka faktorer som påverkar följsamheten till råd om egenvård hos patienter med diabetes typ 2. Metod: En litteraturöversikt baserad på 15 vetenskapliga artiklar där både kvalitativa och kvantitativa artiklar har granskats. Databaserna CINAHL och PubMed har använts. Resultat: Faktorer som påverkade följsamheten till råd om egenvård identifierades och resulterade i fem huvudkategorier: Information; Kunskap; Socialt stöd; Teknologiskt stöd och Livssituation. Dessa faktorer framkom som viktiga för en god följsamhet till råd om egenvård. Slutsats: Det är av stor betydelse att försöka identifiera varje individs olika förutsättningar, för att på så sätt ha möjlighet att anpassa både information, utbildning och egenvårdsplanering utifrån individen.