Optimization of cable cycles : a trade-off between reliability and cost

This paper elaborates the routing of cable cycle through available routes in a building in order to link a set of devices, in a most reasonable way. Despite of the similarities to other NP-hard routing problems, the only goal is not only to minimize the cost (length of the cycle) but also to increase the reliability of the path (in case of a cable cut) which is assessed by a risk factor. Since there is often a trade-off between the risk and length factors, a criterion for ranking candidates and deciding the most reasonable solution is defined. A set of techniques is proposed to perform an efficient and exact search among candidates. A novel graph is introduced to reduce the search-space, and navigate the search toward feasible and desirable solutions. Moreover, admissible heuristic length estimation helps to early detection of partial cycles which lead to unreasonable solutions. The results show that the method provides solutions which are both technically and financially reasonable. Furthermore, it is proved that the proposed techniques are very efficient in reducing the computational time of the search to a reasonable amount.

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.

Optimal Path Searching through Specified Routes using different Algorithms

To connect different electrical, network and data devices with the minimum cost and shortest path, is a complex job. In huge buildings, where the devices are placed at different locations on different floors and only some specific routes are available to pass the cables and buses, the shortest path search becomes more complex. The aim of this thesis project is, to develop an application which indentifies the best path to connect all objects or devices by following the specific routes.To address the above issue we adopted three algorithms Greedy Algorithm, Simulated Annealing and Exhaustive search and analyzed their results. The given problem is similar to Travelling Salesman Problem. Exhaustive search is a best algorithm to solve this problem as it checks each and every possibility and give the accurate result but it is an impractical solution because of huge time consumption. If no. of objects increased from 12 it takes hours to search the shortest path. Simulated annealing is emerged with some promising results with lower time cost. As of probabilistic nature, Simulated annealing could be non optimal but it gives a near optimal solution in a reasonable duration. Greedy algorithm is not a good choice for this problem. So, simulated annealing is proved best algorithm for this problem. The project has been implemented in C-language which takes input and store output in an Excel Workbook

Production and Delivery (Optimization of production system and reliability)

This thesis is done to solve two issues for Sayid Paper Mill Ltd Pakistan. Section one deals with a practical problem arise in SPM that is cutting a given set of raw paper rolls of known length and width, and a set of product paper rolls of known length (equal to the length of raw paper rolls) and width, practical cutting constraints on a single cutting machine, according to demand orders for all customers. To solve this problem requires to determine an optimal cutting schedule to maximize the overall cutting process profitability while satisfying all demands and cutting constraints. The aim of this part of thesis is to develop a mathematical model which solves this problem.Second section deals with a problem of delivering final product from warehouse to different destinations by finding shortest paths. It is an operational routing problem to decide the daily routes for sending trucks to different destination to deliver their final product. This industrial problem is difficult and includes aspect such as delivery to a single destination and multiple destinations with limited resources. The aim of this part of thesis is to develop a process which helps finding shortest path.

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.