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.

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.

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

Genus i historieundervisningen : Problem och möjligheter ur ett gymnasielärarperspektiv

Syftet med den här uppsatsen har varit, dels att undersöka ett antal historielärares förståelse av och attityd till användandet av begreppet genus i historieundervisningen på gymnasiet, dels att analysera vad jämställdhetsmålen i gymnasieskolans styrdokument egentligen säger om be-greppet genus och om detta bör tolkas som ett direktiv att implementera genus i historieun-dervisningen. Undersökningen genomfördes i två steg. Gymnasieskolans styrdokument; skollagen, lä-roplanen för de frivilliga skolformerna samt ämnesbeskrivning och kursplaner för historia A, B och C, närlästes och analyserades utifrån en genusteoretisk grund. Därefter intervjuades sex utvalda gymnasielärare i historia kring begreppet genus i teori och praktik. Resultatet analyse-rades och kategoriserades därefter så att lärarnas genusmedvetenhet och attityd till användan-de av genus i historieundervisningen gick att identifiera.Styrdokumentsgranskningen visade att styrdokumenten idag inte säger någonting expli-cit om användandet av ett genusperspektiv i historieundervisningen men att skollagens och läroplanens jämställdhetsdirektiv vilar på en genusteoretisk grund och därmed indirekt kräver ett genusperspektiv i den konkreta undervisningen. Dokumentens formuleringar kräver en god kunskap kring begreppen jämställdhet och genus för att kunna förstås. Utan den kunskapen riskerar avsaknaden av ett explicit uttalat genusbegrepp att legitimera en historieundervisning utan genusperspektiv.Intervjuresultatet visade att genusmedvetenheten bland de utvalda lärarna var låg och att förekomsten av ett genusperspektiv i den egna undervisningen avgjordes av lärarens eget in-tresse för frågan. Attityden till användandet av ett genusperspektiv i historieundervisningen på gymnasiet kunde hos de flesta tolkas som positiv i teorin men i praktiken omgärdad av en rad förhindrande omständigheter såsom omedvetenhet, tids- och utrymmesbrist, metodbrist och historiedidaktiskt förhållningssätt.

Amning : Duration, problem och skäl till att sluta : En retrospektiv studie av mammors erfarenheter

Syftet med uppsatsen var att relatera amningstidens längd till amningsproblem och kvinnors upplevelse av sin amning samt att kartlägga orsaker till delvis amning och upphörande av amning. Studiens design var en deskriptiv, retrospektiv korrelationsstudie med kvantitativ ansats. Materialet till studien hämtades från redan utförda intervjuer. Populationen bestod av 250 kvinnor i åldrarna 19-46 år varav 103 var förstföderskor och 147 omföderskor.Resultatet av studien har visat att tiden för enbart amning och den totala amningstidens längd varierade. De kvinnor som var positiva till amningen hade en längre amningsperiod än de kvinnor som var negativa till amningen. Anledningarna till att kvinnorna upphörde med den exklusiva amningen var främst medveten tillvänjning till annan kost än bröstmjölk. Det näst vanligaste skälet var enligt rekommendation från BVC att börja ge smakportioner, och det näst, näst vanligaste skälet var relaterat till barnet, nämligen hungrigt barn. Skälen till att avsluta amningen var jämnt fördelade mellan mor- och barn-relaterade orsaker. Bland barn-relaterade orsaker var barnets ointresse för bröstet det klart dominerande skälet till avslutad amning och bland mammorna en medveten avvänjning. Under BB-tiden var det varannan mamma som led av problem med amningen. Det vanligaste problemet var fel sugteknik hos barnet och det näst vanligaste problemet var såriga bröstvårtor. Under barnets första vecka efter hemgång var det såriga bröstvårtor som var det största problemet. Under BVC-tiden var det mjölkstockning som var det vanligast förekommande problemet tätt följt av såriga bröstvårtor. Majoriteten av mödrarna hade upplevt sin amning som positiv, en mysig och värdefull tid. Men många hade även negativa upplevelser såsom känsla av bundenhet och stress.

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.

Spanning Tree Approach On The Snow Cleaning Problem

Snow cleaning is one of the important tasks in the winter time in Sweden. Every year government spends huge amount money for snow cleaning purpose. In this thesis we generate a shortest road network of the city and put the depots in different place of the city for snow cleaning. We generate shortest road network using minimum spanning tree algorithm and find the depots position using greedy heuristic. When snow is falling, vehicles start work from the depots and clean the snow all the road network of the city. We generate two types of model. Models are economic model and efficient model. Economic model provide good economical solution of the problem and it use less number of vehicles. Efficient model generate good efficient solution and it take less amount of time to clean the entire road network.

Upplevda problem med projektstyrningsmetoden Scrum i systemutvecklingsprojekt : En studie av Scrums-relaterade problem hos IT- företag i Borlängeregion

Många projekt misslyckas och en av anledningarna är dålig styrning av projektet i allmänhet och inom IT branschen i synnerhet. Baserad på kritik av de traditionella metoderna under de senaste åren, så har det uppkommit flera lättrörliga metoder som kallas Agila metoder. Scrum är den mest kända Agila metoden som används idag. Metoden lovar goda resultat, men i en artikel ur tidningen Computer Sweden (feb 2009) står det ”siffror visar att nio av tio Scrumprojekt misslyckas”. Artikeln triggade vårt intresse av att ta reda på vilka problem specifika för Scrum som många har kritiserat och valde därför att rikta in vår studie mot detta. Uppsatsen syftar till att undersöka om lokala IT-företag i Borlänge, Headlight, Sogeti ochstatliga nätkapacitetleverantören Trafikverket ICT lider av det allmänna problem som de andra Scrumanvändarna upplever i samband med användningen av metoden. Denna uppsats har fokus på fyra problemområden: bristfällig dokumentation, sämre effektivitet i arbetsprocessen, sämre effektivitet i arbetsprocessen i stora projekt samt bristande stöd för utvärdering. För vår studie har litteraturstudier och intervjuer genomförts. Intervjuserier gjordes på elva personer hos våra fallföretag. Målgruppen för våra intervjuer är Product Owner (PO) ScrumMaster (SM) och utvecklare. Vi kan efter genomförd studie dra slutsatsen att de allmänna upplevda problem som de andra Scrumanvändaren upplever har vi även kunnat identifiera hos våra fallföretag. Resultaten har bekräftats med insamlade data och vår teoretiska ram. I diskussionen presenterar vi rekommendationer för att undvik relaterade problem med Scrum.

Essentialism i religionsundervisningen : Ett religionsdidaktiskt problem

Essentialist concepts of religion are common in the teaching of religion in schools and to a certain extent also in the academic discipline of religious studies. In this article, a number of problems with essentialist perceptions of religion are discussed. In the first part of the article a thesis is maintained, according to which essentialist conceptions of religion or specific religions are too limited to be of value in the teaching of religion. This is done through examples of essentialist expressions about religion. The examples are grouped according to a typology of different kinds of essentialism. Two main categories, each with two sub-categories are identified. Thus, the category of essentialism regarding the substance of religion is divided into transcendental or theological essentialism (which presupposes the existence of a sacred power of some kind, the experience of which is the basis for religion), and core essentialism (where it is presupposed that certain ideas or concepts constitute religion as a general category or specific religions). Likewise, the category of essentialism regarding the function of religion has two sub-categories: positive and negative essentialism. These kinds of essentialism presuppose that religion or specific religions are inherently good or harmful respectively to human beings. Examples from each of these categories are given and discussed. In the second part of the article, Benson Saler’s open concept of religion is presented as an alternative to essentialist or bounded perceptions. It is based on Ludwig Wittgenstein’s idea of family resemblances and on prototype theory. In connection with this, it is argued that a certain kind of conscious ethnocentrism is needed as a point of departure in the study and teaching of religion. The metaphor of education as a journey from the familiar out into the unfamiliar and back again is suggested as a possible pattern for such teaching. Finally,some examples of non-essentialist ways to introduce religions are offered.

Från kvinnans problem till problemfri kvinna : En undersökning av audiovisuell reklam för sanitetsprodukter till menstruerande kvinnor mellan åren 1970 och 2000

This thesis tries trough qualitative analyzes to illuminate advertising and its didactic aspects, how menstruation and menstruating women are portrayed over time. The method underlying the survey is didactic, diachronic comparative and hermeneutic. There will also be a feminist point of view on the material. The issue is about how the advertisement presents sanitary products and menstruation and how a menstruating woman is portrayed.The conclusion is that the image of a menstruating woman changes slightly while consolidating the ethos that menstruation should not be visible. The menstruating woman is in constant motion, always fresh and fragrant.

Hur löser gymnasieelever ett rikt problem? : En undersökning om vilka uttrycksformer gymnasieeleveranvänder när de löser ett rikt matematiskt problem

I denna uppsats lägger jag fokus på att undersöka de olika matematiska uttrycksformer someleverna tillämpar när de löser ett rikt problem. Svaret söks med hjälp av empirisk data. Syftetmed arbetet är att undersöka hur några elever som går första året på gymnasiet löser ett riktproblem. Två grupper elever som går i två olika program deltar i undersökningen. Analysengjordes med hjälp av ”KLAG-matrisen”, dvs. en matris som innehåller uttrycksformerna Konkret,Logisk/språklig, Algebraisk/aritmetisk samt Grafisk/geometrisk. Resultatet av litteratur- ochempiristudien visar att oavsett hur eleverna uttrycker sig i sina lösningsförslag innehåller det alltidnågon form av algebraisk/aritmetisk uttrycksform. Detta kan bero på att det för dessa elever ärlättare att kommunicera med algebraisk/aritmetisk uttrycksform än med någon annan. Resultatetvisar också vikten av att använda problemlösning som ett medel i en lärandeprocess även för attutveckla andra förmågor. Eleverna har olika uppfattningar och gör olika tolkningar av problemet.De har olika förutsättningar och använder varierande lösningsmetoder. Detta skulle kunna varaen förklaring till varför deras användning av uttrycksformer är olika.

Energieffektivisering av allmännyttan Jakobsgårdarna : Sociala, politiska, tekniska möjligheter och problem

Denna rapport Energieffektivisering av allmännyttan Jakobsgårdarna behandlar bostadsbolaget Tunabyggens (Borlänge kommun) projekt Jakobsgårdarna, under perioden 2009 till och med juni 2012. Det finns skillnader i tekniskt-ekonomiskt möjliga energieffektiviseringsåtgärder och vad som faktiskt åtgärdas. Denna skillnad har benämnts "energieffektiviseringsgapet". I denna rapport beskrivs och studeras vilka sociala, kulturella, politiska och tekniska faktorer som har en tendens att vidga, respektive reducera, "energieffektiviseringsgapet". Det är en implementeringsstudie, där utgångspunkten är en interaktion mellan fastställande av mål och åtgärder för att uppnå dem. Studien lyfter upp två fokusområden. Fokusområdet styrmedel koncentreras till studier av hur de energipolitiska mål som formulerats nationellt och lokalt kan kopplas till projektet Jakobsgårdarna samt val av specifika styrmedel. Fokusområdet kommunikation inkluderar studier av hur förändringsplanerna formuleras och kommuniceras till boendegrupperingar och intresseorganisationer. Valda metoder är intervjuer, observationer av projektmöten, studier av offentliga handlingar, hemsidor och dokument från EU, regering, riksdag, och Borlänge kommun. En sonderande teknisk pilotinventering av Jakobsgårdarna har utförts, liksom en bearbetning och analys av energistatistik. Det som är viktigt för projektet fortskridande och därmed uppnå formulerade energieffektiviseringsmål är ekonomiska resurser för kostsamma renoveringar, kunskap om befintligt energisystem och möjliga energieffektiviseringsåtgärder, samt möjlighet att implementera ny energieffektiv teknik. Studien visar även att energieffektiviseringsarbetet är mer beroende av governancestyrning (ex SABO-initiativet) än hierarkisk styrning (ex energi- och klimatstrategin). Bostadsbolaget har ett ansvar att ombesörja bostäder för välbeställda liksom mindre välbeställda kommuninvånare. Man kan här ana en konflikt mellan energieffektiviseringsmålen, och kommunens aktuella bostadsbrist liksom lagen om kommunernas bostadsförsörjningsansvar. Ambitionen att involvera de boende i energieffektiviseringsarbetet förväntas leda till att de boende blir medveten om sin energianvändning, och att det i sin tur leder till minskad energianvändning. De projektansvariga förstår att de måste kommunicera olika frågor med de boende, men de boende är måttligt intresserade av energifrågor som tenderar att bli av väldigt teknisk karaktär.