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.

Konstruktion och design av två glassförpackningar i kartongkvaliteten Frövi Light

This degree project was made in cooperation with AssiDomän Frövi and Charlotte Andersson and the main objectivehas been to create to ice cream pacbges from 250 gsm Frövi Light board. The paekages are intended to be easilyresealable while decreasing in size together with the ice cream. The project also describes the food packaging labelsand symbols currently present in the European common market.Both capsules utilize a separate lid for resealing. One of the paekages (Capsuie A) is indended to be cut along withthe ice cream and thereby decrease in size. The other one (Capsuie B) uses a series of flaps for contracting and expandingwhich enab1es adjusting of the size without cutting the package up.The design for Capsuie A is created both as a series of flavours with a super-hero theme intended for children andwith a colfee flavour for a maturer audience. For Capsule B, a design was created for a sorbet.

Improved Road Design for Future Maintenance - Analysis of Road Barrier Repair Costs

The cost of a road construction over its service life is a function of the design, quality of construction, maintenance strategies and maintenance operations. Unfortunately, designers often neglect a very important aspect which is the possibility to perform future maintenance activities. The focus is mainly on other aspects such as investment costs, traffic safety, aesthetic appearance, regional development and environmental effects. This licentiate thesis is a part of a Ph.D. project entitled “Road Design for lower maintenance costs” that aims to examine how the life-cycle costs can be optimized by selection of appropriate geometrical designs for the roads and their components. The result is expected to give a basis for a new method used in the road planning and design process using life-cycle cost analysis with particular emphasis on road maintenance. The project started with a review of literature with the intention to study conditions causing increased needs for road maintenance, the efforts made by the road authorities to satisfy those needs and the improvement potential by consideration of maintenance aspects during planning and design. An investigation was carried out to identify the problems which obstruct due consideration of maintenance aspects during the road planning and design process. This investigation focused mainly on the road planning and design process at the Swedish Road Administration. However, the road planning and design process in Denmark, Finland and Norway were also roughly evaluated to gain a broader knowledge about the research subject. The investigation was carried out in two phases: data collection and data analysis. Data was collected by semi-structured interviews with expert actors involved in planning, design and maintenance and by a review of design-related documents. Data analyses were carried out using a method called “Change Analysis”. This investigation revealed a complex combination of problems which result in inadequate consideration of maintenance aspects. Several urgent needs for changes to eliminate these problems were identified. Another study was carried out to develop a model for calculation of the repair costs for damages of different road barrier types and to analyse how factors such as road type, speed limits, barrier types, barrier placement, type of road section, alignment and seasonal effects affect the barrier damages and the associated repair costs. This study was carried out using a method called the “Case Study Research Method”. Data was collected from 1087 barrier repairs in two regional offices of the Swedish Road Administration, the Central Region and the Western Region. A table was established for both regions containing the repair cost per vehicle kilometre for different combinations of barrier types, road types and speed limits. This table can be used by the designers in the calculation of the life-cycle costs for different road barrier types.

Road Design for Future Maintenance : Life-cycle Cost Analyses for Road Barriers

The cost of a road construction over its service life is a function of design, quality of construction as well as maintenance strategies and operations. An optimal life-cycle cost for a road requires evaluations of the above mentioned components. Unfortunately, road designers often neglect a very important aspect, namely, the possibility to perform future maintenance activities. Focus is mainly directed towards other aspects such as investment costs, traffic safety, aesthetic appearance, regional development and environmental effects. This doctoral thesis presents the results of a research project aimed to increase consideration of road maintenance aspects in the planning and design process. The following subgoals were established: Identify the obstacles that prevent adequate consideration of future maintenance during the road planning and design process; and Examine optimisation of life-cycle costs as an approach towards increased efficiency during the road planning and design process. The research project started with a literature review aimed at evaluating the extent to which maintenance aspects are considered during road planning and design as an improvement potential for maintenance efficiency. Efforts made by road authorities to increase efficiency, especially maintenance efficiency, were evaluated. The results indicated that all the evaluated efforts had one thing in common, namely ignorance of the interrelationship between geometrical road design and maintenance as an effective tool to increase maintenance efficiency. Focus has mainly been on improving operating practises and maintenance procedures. This fact might also explain why some efforts to increase maintenance efficiency have been less successful. An investigation was conducted to identify the problems and difficulties, which obstruct due consideration of maintainability during the road planning and design process. A method called “Change Analysis” was used to analyse data collected during interviews with experts in road design and maintenance. The study indicated a complex combination of problems which result in inadequate consideration of maintenance aspects when planning and designing roads. The identified problems were classified into six categories: insufficient consulting, insufficient knowledge, regulations and specifications without consideration of maintenance aspects, insufficient planning and design activities, inadequate organisation and demands from other authorities. Several urgent needs for changes to eliminate these problems were identified. One of the problems identified in the above mentioned study as an obstacle for due consideration of maintenance aspects during road design was the absence of a model for calculating life-cycle costs for roads. Because of this lack of knowledge, the research project focused on implementing a new approach for calculating and analysing life-cycle costs for roads with emphasis on the relationship between road design and road maintainability. Road barriers were chosen as an example. The ambition is to develop this approach to cover other road components at a later stage. A study was conducted to quantify repair rates for barriers and associated repair costs as one of the major maintenance costs for road barriers. A method called “Case Study Research Method” was used to analyse the effect of several factors on barrier repairs costs, such as barrier type, road type, posted speed and seasonal effect. The analyses were based on documented data associated with 1625 repairs conducted in four different geographical regions in Sweden during 2006. A model for calculation of average repair costs per vehicle kilometres was created. Significant differences in the barrier repair costs were found between the studied barrier types. In another study, the injuries associated with road barrier collisions and the corresponding influencing factors were analysed. The analyses in this study were based on documented data from actual barrier collisions between 2005 and 2008 in Sweden. The result was used to calculate the cost for injuries associated with barrier collisions as a part of the socio-economic cost for road barriers. The results showed significant differences in the number of injuries associated with collisions with different barrier types. To calculate and analyse life-cycle costs for road barriers a new approach was developed based on a method called “Activity-based Life-cycle Costing”. By modelling uncertainties, the presented approach gives a possibility to identify and analyse factors crucial for optimising life-cycle costs. The study showed a great potential to increase road maintenance efficiency through road design. It also showed that road components with low investment costs might not be the best choice when including maintenance and socio-economic aspects. The difficulties and problems faced during the collection of data for calculating life-cycle costs for road barriers indicated a great need for improving current data collecting and archiving procedures. The research focused on Swedish road planning and design. However, the conclusions can be applied to other Nordic countries, where weather conditions and road design practices are similar. The general methodological approaches used in this research project may be applied also to other studies.