Syftet med denna studie var att undersöka olika algoritmer som kan användas för attlösa ruttplaneringsproblemet och handelsresandeproblemet. Ruttplaneringsproblemetoch handelsresandeproblemet är problemet som uppstår när den kortaste sträckan skahittas mellan olika körpunkter och problemet är löst efter att den kortaste sträckan blivitfunnen. Observationer och intervjuer hos återvinningsföretaget Gotland Recyclinggjordes för att undersöka hur heuristiker som är metoder, tumregler som kan användasför att få fram resultat som är bra men inte alltid helt optimala kan användas för att kortaner körruterna. Arbetet gjordes med hjälp av företaget Gotland Recycling som idag harcirka 500 kunder per år och äger två sopbilar samt två lastbilar. Företaget har under enlängre tid förstått att deras ruttplaneringssystem har kunnat förbättras därav har företagetintresserat sig för att testa nya metoder för att förbättra sina egna rutter samt olikametoder för att validera de metoder som redan används för ruttplanering och körning.Google Maps och Microsoft Excel användas i denna studie för att applicera de olikaruttplaneringsmetoderna och kunna analysera de olika rutterna. Med hjälp av GoogleMaps har kostnader i form av körsträcka i meter och kilometer tagits fram genom attapplicera algoritmerna på olika körnings områden. Med hjälp av Google Maps ochMicrosoft Excel har fordonens körningsmönster blivit kartlagda och registrerade itabeller där de olika algoritmerna blivit applicerade för att bygga upp nya rutter ochmäta de nya rutternas körsträcka. Litteratur och artiklar har även samlats ihop för dennastudie och användes för att analysera olika ruttplanering och handelsresandeproblemsmetoders olika svagheter och styrkor. Resultatet från testerna och litteraturen visade attdet finns en potential att olika lösnings metoder som undersökts i denna studie kanminska på körsträckan. Olika lösningsmetoder har olika förutsättningar, styrkor ochsvagheter beroende på situationen som de appliceras inom. I två tester av tre medanvändning av någon av den utvalda ruttplanerings metoder minskade körsträckan imeter för rutten jämfört med företagets egen ruttplanering. Både testerna och litteraturenpåvisade att ibland förekommer mycket oberäkneliga hinder inom vissa områden somgör det meningslöst att applicera ruttplanering och handelsresandemetoder inom dessaområden och att mer avancerade system krävs för att hantera situationen. / The aim with this paper was to study how different kinds of heuristics for the routeplanning and traveling salesman’s problem could affect the route, potentially decreasethe driving costs and make it easier for companies and vehicles to plan their routes. Toinvestigate how different heuristics can affect the route planning, observations andinterviews has been made in a company named Gotland Recycling. Gotland Recyclingis a recycling company which operate on the island Gotland. Today the company has500 customers per year and owns four truck vehicles. The company has understood thatfor a long time their route planning system can be improved and has taken an interest intesting new methods to improve their own route planning and validate the methodswhich they are already using for route planning and driving. To analyze the differentroutes Google Maps and Excel was used. With the help of Google Maps and Excel costsin the form of driving length in meter and kilometer has been produced by applying thechosen algorithms on different driving areas. With the help of Google Maps and Excel,the driving pattern has been charted and registered in different tables. Differentalgorithms have then been applied to construct new routes and measure their mileage.Theory in the form of literature and articles has been collected for this study to analyzeand compare different strengths and weaknesses of different route planning andtraveling salesman problem solving methods. The result from this study shows there is apotential for different solution methods to make the mileage smaller. Different solvingmethods had different qualifications, strengths and weaknesses which depended on thesituations which they were applied. In two of the three tests which were made thechosen solving methods produced routes which were shorter than the route produced bythe company. Both testing and the literature also showed that for some situations thereare so many random obstacles in driving areas which make it meaningless to apply anytype of route-planning method and more advanced systems are required.
| Identifer | oai:union.ndltd.org:UPSALLA1/oai:DiVA.org:hig-35452 |
| Date | January 2021 |
| Creators | Gustafsson, Victor |
| Publisher | Högskolan i Gävle, Industriell ekonomi |
| Source Sets | DiVA Archive at Upsalla University |
| Language | Swedish |
| Detected Language | Swedish |
| Type | Student thesis, info:eu-repo/semantics/bachelorThesis, text |
| Format | application/pdf |
| Rights | info:eu-repo/semantics/openAccess |
Page generated in 0.0028 seconds