Use Multilevel Graph Partitioning Scheme to solve traveling salesman problem

The traveling salesman problem is although looking very simple problem but it is an important combinatorial problem. In this thesis I have tried to find the shortest distance tour in which each city is visited exactly one time and return to the starting city. I have tried to solve traveling salesman problem using multilevel graph partitioning approach.Although traveling salesman problem itself very difficult as this problem is belong to the NP-Complete problems but I have tried my best to solve this problem using multilevel graph partitioning it also belong to the NP-Complete problems. I have solved this thesis by using the k-mean partitioning algorithm which divides the problem into multiple partitions and solving each partition separately and its solution is used to improve the overall tour by applying Lin Kernighan algorithm on it. Through all this I got optimal solution which proofs that solving traveling salesman problem through graph partition scheme is good for this NP-Problem and through this we can solved this intractable problem within few minutes.Keywords: Graph Partitioning Scheme, Traveling Salesman Problem.

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.

Task assignment optimization in SAP Extended WarehouseManagement

Nowadays in the world of mass consumption there is big demand for distributioncenters of bigger size. Managing such a center is a very complex and difficult taskregarding to the different processes and factors in a usual warehouse when we want tominimize the labor costs. Most of the workers’ working time is spent with travelingbetween source and destination points which cause deadheading. Even if a worker knowsthe structure of a warehouse well and because of that he or she can find the shortest pathbetween two points, it is still not guaranteed that there won’t be long traveling timebetween the locations of two consecutive tasks. We need optimal assignments betweentasks and workers.In the scientific literature Generalized Assignment Problem (GAP) is a wellknownproblem which deals with the assignment of m workers to n tasks consideringseveral constraints. The primary purpose of my thesis project was to choose a heuristics(genetic algorithm, tabu search or ant colony optimization) to be implemented into SAPExtended Warehouse Management (SAP EWM) by with task assignment will be moreeffective between tasks and resources.After system analysis I had to realize that due different constraints and businessdemands only 1:1 assingments are allowed in SAP EWM. Because of that I had to use adifferent and simpler approach – instead of the introduced heuristics – which could gainbetter assignments during the test phase in several cases. In the thesis I described indetails what ware the most important questions and problems which emerged during theplanning of my optimized assignment method.

What factors affect the destination choice of Jordanian tourists?A panel data analysis

This paper investigates what factors affect the destination choice for Jordanian to 8 countries (Oman, Saudi Arabia, Syria, Tunisia, Yemen, Egypt, Lebanon and Bahrain) using panel data analysis. Number of outbound tourists is represented as dependent variable, which is regressed over five explanatory variables using fixed effect model. The finding of this paper is that tourists from Jordan have weak demand for outbound tourism; Jordanian decision of traveling abroad is determined by the cost of traveling to different places and choosing the cheapest alternative.

Ant colony for TSP

The aim of this work is to investigate Ant Colony Algorithm for the traveling salesman problem (TSP). Ants of the artificial colony are able to generate successively shorter feasible tours by using information accumulated in the form of a pheromone trail deposited on the edges of the TSP graph. This paper is based on the ideas of ant colony algorithm and analysis the main parameters of the ant colony algorithm. Experimental results for solving TSP problems with ant colony algorithm show great effectiveness.

Den avgörande föreställningen : En struktur för transmediaberättandet

En transmediaberättelse kan beskrivas som ett berättande som sker över flera separata tekniska medier, där varje enskilt mediums innehåll kan stå självständigt, men i läsningen tillsammans bildar en större sammanhållen berättelse. De enskilda mediumen kan vara icke-berättande, interaktiva, uppmuntra till medskapande och vara helt valfria både vad gäller ordningen de konsumeras i och att ta del av över huvudtaget. En sådan berättelse, eller snarare berättelsekonsumtion ställer krav på en analysmodell. Uppsatsens syfte är att att beskriva användarens förhållande till berättelsebeteenden i det pågående transmediaberättandet, avseende tolkning och påverkan av produktionen. I studien genomfördes en explorativ litteraturstudie inom flera olika ämnesområden och resultatet har sammanställts i en beskrivande modell för berättelseprocessen. Modellen inkluderar en ny begreppsapparat, som inte utgår från vilken typ av produktion det handlar om. Den skildrar användarens förhållande till de berättelsestimuli som finns i olika framställningar och hur dessa genom tolkning sammanfogas till sammanhållande berättelser. Modellen berör även skapandet och medskapandet av sådana framställningar. Modellen prövas på ett exempel med samspel mellan en distinkt icke-berättande och en berättande komponent i form av en actionfigur och dess förpackningstext. Exemplet illustrerar hur actionfiguren utan att på något sätt själv vara en berättelse ändå besitter berättelsestimuli som gör att den passar in i den större transmediaberättelsen. Skaparen har planterat berättelsestimuli, men det är läsarens uppgift att knyta samman och genom sin föreställning omvandla en rad stimuli till en faktisk berättelse.

Road network and GPS tracking with data processing and quality assessment

GPS technology has been embedded into portable, low-cost electronic devices nowadays to track the movements of mobile objects. This implication has greatly impacted the transportation field by creating a novel and rich source of traffic data on the road network. Although the promise offered by GPS devices to overcome problems like underreporting, respondent fatigue, inaccuracies and other human errors in data collection is significant; the technology is still relatively new that it raises many issues for potential users. These issues tend to revolve around the following areas: reliability, data processing and the related application. This thesis aims to study the GPS tracking form the methodological, technical and practical aspects. It first evaluates the reliability of GPS based traffic data based on data from an experiment containing three different traffic modes (car, bike and bus) traveling along the road network. It then outline the general procedure for processing GPS tracking data and discuss related issues that are uncovered by using real-world GPS tracking data of 316 cars. Thirdly, it investigates the influence of road network density in finding optimal location for enhancing travel efficiency and decreasing travel cost. The results show that the geographical positioning is reliable. Velocity is slightly underestimated, whereas altitude measurements are unreliable.Post processing techniques with auxiliary information is found necessary and important when solving the inaccuracy of GPS data. The densities of the road network influence the finding of optimal locations. The influence will stabilize at a certain level and do not deteriorate when the node density is higher.

”När man kollar på bilden tänker man så här” : en receptionsstudie av gymnasieelevers uppfattning om bilder som kunskapskällor i historieundervisningen

Images are used in history education for a variety of reasons, not least to generate interest through a better understanding of historical events and people. The aim of this study was to investigate how historical pictures, either illustrated or documentary/photographic, can be used as a resource for activating and improving pupils' historical empathy, in the way described by Stéphane Lévasque. I conducted a reception study on five different focus groups consisting of pupils from different upper secondary schools in Sweden. The pupils varied with regard to number of credits for admission to upper secondary school. A sixth group of pupils was interviewed as a contrasting control group in order to add perspective to the results. The discussions were based on the pupils' interpretations of 34 selected pictures, all of which were taken from the most common history textbooks. Each pupil was asked to choose the picture he/she felt was the most representative historical image. On the basis of the strategies used by the pupils when interpreting the pictures and discussing them, the material was analysed in accordance with Lévesque's categories: imagination, historical contextualisation and morals. The last category, morals, was further divided into three sub-categories: sense of justice, sympathy and progression. The reflections of the pupils and the degree of contextualisation varied. It appeared that the pupils were less inclined to discuss assumptions about the persons in the pictures; instead they chose to discuss the historical context in question. The pictures in this study did not seem to trigger the pupils to fabricate anachronistic reasoning about history; when they did produce lengthy reasoning, it was contextual, structural and metahistorical. In this context, the pupils who belonged to the group with the highest average of credits showed some signs of reflection on the basis of historical context and some criticism about the historical sources. On no occasion did any of the pupils choose a picture as a concrete expression of injustice. One of the questions this study aimed to explore was whether a lack of historical context affects how pictures trigger emotions and reasoning on the basis of moral aspects. Some of the pupils displayed moral standpoints, primarily the degree of morals concerning injustice. One possible interpretation could be that the feeling of being unfairly treated and subjected to insulting behaviour and social injustice was something the pupils could relate to. The group of pupils who had not yet studied history at upper secondary school, the control group, generally made reflections using this sort of reasoning when they discussed the historical aspects of the pictures.

Mio i folksagan och karnevalen : En tolkning och narratologisk studie av Astrid Lindgrens verk Mio, min Mio

The purpose of the study is, based on a narratological perspective, to analyze and interpret the novel written by Astrid Lindgren: Mio, min Mio. It is based on the legacy of the folktale tradition, which is also the basis for carnival concept according to Bachtin. The study is based on a narrative model of Gérard Genette. Mio, min Mio is told as a first person narrator and can be interpreted as Bo tells it to himself. It is a frame story in which the outer story is the reality, while the inner story is the structure of the folktale where Mio embarks on a predetermined mission to fight against evil. Carnival concept involves a timed up-and-down-turn that is sanctioned and controlled, this fits well with this story seen from this interpretation. In the fantasy world everything has an idealized counterpart and Bo is, via Mio, in this world for a limited time. Children in our society are powerless, but are allowed to be mighty in children's literature. The story gets a subversive effect as it shows that adult standards are not absolute. Even if Bo turns back to his foster parents, he goes through this inner battle processing his thoughts and feelings. The love Bo will experience in imagination gives him the power to manage his real situation.