Dagens parallella ökning av konsumtion och hållbarhetstänk ställer höga krav på företag. Digitaliseringen och den tekniska progressionen utmanar företag än mer att arbeta mot ständig förbättring för att bibehålla sin konkurrenskraft och är en aspekt som studien lyfter. En av de väsentligaste aktiviteterna att reformera för en transportdistributör inom tillväxtfasen är dess planering och i denna studie läggs vikten således på rutteffektivisering utifrån både kostnads-och miljöaspekter. För att utforma en gynnsam ruttplanering är en av de viktigaste aspekterna informationsflödet. Det finns en tydlig koppling att företag som har ett ineffektivt informationsflöde har svårigheter med att ta fram en ruttplanering som är effektiv. Studien har sitt fokus på mindre företag som befinner sig i tillväxtfasen och hur dessa fördelaktigt kan effektivisera sin ruttplanering och informationsflöde för att bibehålla sin konkurrenskraftighet. Utifrån det teoretiska ramverket, intervjuer och tilldelad data identifieras brister inom informationsflödet och ruttplaneringen. Teorier om omvänd logistik, ruttplanering, värdeflödesanalys och informationssystem med fokus på kommunikation kommer appliceras och användas. Det ska dessutom påvisas varför en bra och välutvecklad ruttplanering är mer gynnsam för ett företag. Via en kartläggning har dessa brister undersökts och reformeringsförslag på informationsflödet har framställts. Dessutom har, via en jämförelse av ruttplanering mellan ett stort mer erfaret företag och ett litet företag med mindre erfarenhet, fördelar och tankesätt kring utförandet av en ruttplanering framtagits. Det visar sig att ett noggrant och grundligt genomtänkt ruttplanering och information och kommunikations-system anpassat efter organisationens behov och prioriteringar skapar konkurrenskraftighet, till skillnad från att använda penna och papper metoden. Vetenskapligt framtagna manuella ruttplaneringsmetoder så som fasta slingor och svepmetoden appliceras fördelaktigt på ett företag i tillväxtfasen. Det genererar samtidigt i en hög kundtillfredsställelse och lönsamhet samtidigt som det ökar miljömedvetenheten hos små företag i tillväxtfasen. Utöver detta skapas en trygghet för den anställde och kontroll över företagets resurser och kapaciteter fås. Problem som är förekommande inom informationsflödet är bland annat ej standardiserad information i körscheman men med hjälp av rutiner, standarder och ett nuläge att utgå ifrån kan ett förbättringsarbete påbörjas och styras i rätt riktning. Studien påvisar att detta är av stor vikt även inom ruttplanering. / Today's parallel increase in consumption and sustainability thinking places high demands on companies. Digitization and technological progression challenge companies even more to work towards continuous improvement in order to maintain their competitiveness and is an aspect that the study highlights. One of the most important activities to reform for a transport distributor within the growth phase is its planning, and in this study the emphasis is thus on route efficiency based on both cost and environmental aspects. In order to design a profitable route planning, one of the most important aspects is the information flow. There is a clear link that companies that have an inefficient information flow have difficulties in developing a route planning that is efficient. The study focuses on smaller companies that are in the growth phase and how these can advantageously streamline their route planning and information flow to maintain their competitiveness. Based on the theoretical framework, interviews and assigned data, shortcomings in the information flow and route planning are identified. Theories of reverse logistics, route planning, value stream map analysis and information systems with a focus on communication will be applied and used. It also demonstrates why a good and well-developed route planning is more favorable for a company. Through a survey, these shortcomings have been investigated and reform proposals for the information flow have been made. In addition, through a comparison of route planning between a large, more experienced company, and a small company with less experience, advantages, and ways of thinking about the execution of a route planning have been developed. It turns out that a carefully and thoroughly thought-out route planning and information and communication system adapted to the organization's needs and priorities creates competitiveness, as opposed to using the pen and paper method. Scientifically developed manual route planning methods such as fixed loops and the sweep method are advantageously applied to a company in the growth phase. At the same time, it generates a high level of customer satisfaction and profitability while increasing the environmental awareness of small companies in the growth phase. In addition to this, security is created for the employee and control over the company's resources and capacities is gained. Problems that occur in the information flow include non-standardized information in driving schedules, but with the help of routines, standards, and a current situation to compare with, improvement work can be started and steered in the right direction. The study shows that it is also of great importance when it comes to route planning.

Avfallshämtningen är ett komplext problem som ställer mängder av logistiska krav och bör tillgodose kundens behov om att få sina sopor upphämtade och tömda i rätt tid. Samtidigt bör onödigt trafikarbete minskas för att uppnå en mer hållbar avfallshämtning. Nodra AB sköter avfallshämtningen av det kommunala avfallet i Norrköpings kommun. I dagsläget finns olika abonnemang för Nodra ABs kunder att välja på där avfallet hämtas enligt schemalagda rutter med fasta intervall. Nodra AB vet dock att behovet hos kunderna kan skilja sig från det standardiserade behovet, vilket riskerar att leda till att halvtomma eller överfulla kärl töms. För att se om denna risk går att minimera driver Nodra AB nu ett projekt, Behovsbaserad insamling, där syftet är att utreda om Norrköpings kommun ska gå mot en mer behovsbaserad avfallshämtning. Detta examensarbete avsåg att analysera effekterna på trafikarbetet av att gå från traditionell avfallshämtning med fasta intervall till en behovsbaserad avfallshämtning. Tidsåtgången och koldioxidutsläppen för trafikarbetet ämnades också att analyseras. Målet med examensarbetet var att det skulle fungera som ett komplement till Nodra ABs projektarbete och deras beslutsunderlag inför ett eventuellt införande av behovsbaserad avfallshämtning från fritidshus. Examensarbetet har innefattat både kvalitativa och kvantitativa metoder. En litteraturstudie har genomförts i syfte att få mer kunskap gällande transportplanering och logistiken kring avfallshämtning samt de miljömässiga effekterna transporter ger upphov till idag. Information kring hur Nodra AB arbetar i nuläget har samlats in i form av en intervju med berörd projektledare samt utredningsingenjör och även en observation för att skapa en bättre förståelse. Analysen i examensarbetet grundades på två olika scenarier för en behovsbaserad avfallshämtning. Båda utgick ifrån att ordinarie rutter och intervall bibehölls, men att i det första scenariot endast tömma de kärl som ställts fram vid hämtstället och i det andra scenariot endast tömma de kärl där kunden beställt hämtning via en app. Analysen utgick från att behovet bland fritidshus minskade med 25% under veckorna 24–33 och 50% under veckorna 19–23 samt 34– 38. Inför analysen har data från Nodra AB tillhandahållits, i syfte att kunna beräkna en förändring i körlistorna. För att få fram förändringen i körtid och körsträcka har programvaran ArcMap använts. Resultatet har sedan sammanställts med övriga data i en beräkningsmodell i Microsoft Excel. Resultatet visade på att en behovsbaserad avfallshämtning med minskat behov ger en minskad körsträcka, som leder till tidsbesparingar samt ett minskat koldioxidutsläpp. Resultatet visar dock inte vilka effekter ett ökat behov ger och de finns även övriga aspekter som inte tagits med i detta arbete, som kan påverka trafikarbetet. / <p>Examensarbetet är utfört vid Institutionen för teknik och naturvetenskap (ITN) vid Tekniska fakulteten, Linköpings universitet</p>

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.

Internal transportation is one of the key elements in manufacturing operations, and there is a constant need to optimize this process (Antoniuk, 2021). The case company has a very large industrial are covering 3 km2, which poses significant challenges for the internal transportation. The company has too many parcel stations, lacks clear requirements for new parcel stations and documentation for the parcel stations, and faces route planning issues as a result. The purpose of this case study was to identify obstacles and problems to optimize the company’s parcel transport in terms of route planning, placement of parcel stations and the number of parcel stations. The project aimed to develop a general working model for how a parcel transport can be optimized without relying on the Industrial Internet of Things (Sinsinni et al., 2018) and digital technology. The study focused on the company’s internal and external parcel transport routes within and outside the industrial area. Observations and interviews were conducted at the case company, revealing that customers needs include receiving deliveries twice a day and ensuring correct parcel deliveries. The drivers require unchanged or reduced workload, easier training, fewer parcel stations, properly equipped parcel stations, and improved route planning. The transport manager needs a standardised work approach, fewer parcel stations, documentation of parcel stations, and an expanded requirements list. To optimize the case company’s transport, the number and placement of parcel stations, and simultaneously meet these needs, several improvement suggestions were developed. It was found that implementing a scanning system could enhance the accuracy of the parcel deliveries, but this option was not recommended due to it being expensive and gives no guarantee of correct deliveries, among other things. Instead, it is recommended that the company implements a milk run system to achieve JIT (Just-in-time) deliveries for customers and a standardized work approach standardized work approach for drivers. Additionally, a proposal for a digital map was presented to improve documentation and facilitate training, along with a suggestion to merge parcel stations to reduce workload and enhance route planning. Lastly, expanding the requirements list was suggested to ensure properly equipped parcel stations and provide clearer specifications for parcel stations. A general conceptual work model for this optimization process is outlined as follows: 1.       Observe current delivery routes and stations. 2.       Interview stakeholders (such as customers and drivers). 3.       Identify and compile requirements. 4.       Map out stations on a digital map. 5.       Apply a heuristic selection process.  a.       Examine clusters of stations of the digital map.  b.       Evaluate stations based on collected data.  c.       Assess the activity level; if multiple stations have high activity, make an individual assessment.  d.       Merge the stations.  e.       Apply the 250-meter rule to the remaining selection without available data. 6.       Create an optimal route using the selected stations. / Interna transporter är ett av de viktigaste elementen i en tillverkningsverksamhet och det finns ett konstant behov att optimera denna process (Antoniuk, 2021). Fallföretaget har ett mycket stort industriområde som omfattar 3 km2 vilket ställer stora krav på de interna transporterna. Företaget har för många paketstationer, saknar en tydlig kravbild av nya paketstationer och dokumentation över paketstationerna, och har på grund av detta ett ruttplaneringsproblem. Syftet med denna fallstudie var att identifiera hinder och problem för att kunna optimera företagets pakettransport med avseende på ruttplanering, paketstationers placering och antal paketstationer. Målet med projektet var att ta fram en generell arbetsmodell för hur en pakettransport kan optimeras utan Industrial Internet of Things och digital teknologi (Sinsinni et al., 2018). Studien avgränsades till företagets interna och externa pakettransportrutt, innanför och utanför industriområdet. Det utfördes observationer och intervjuer på fallföretaget som visade att kundernas behov är att få leverans två gånger per dag och att paketen levereras rätt. Chaufförerna har behov av oförändrad eller minskad arbetsbelastning, lättare upplärning, färre paketstationer, korrekt utrustade paketstationer och bättre ruttplanering. Transportchefen har behov av ett standardiserat arbetssätt, färre paketstationer, dokumentation över paketstationer och en utökad kravlista. För att optimera fallföretagets transporter, antalet paketstationer och placeringen och samtidigt uppfylla dessa behov tog vi fram flera förbättringsförslag. Vi kom fram till att ett skanningssystem kan öka möjligheten att kundernas paket inte kommer fel men rekommenderar inte detta då det bland annat är kostsamt och inte garanterar att paketen levereras rätt. Vi rekommenderar i stället att företaget implementerar en milk run som skapar JIT (Just-in-time) leverans för kunderna och ett standardiserat arbetssätt för chaufförerna. Det har också tagits fram ett förslag på en digital karta för ökad dokumentation och lättare upplärning, samt ett förslag på sammanslagning av paketstationer och därigenom en minskning. Detta för att minska arbetsbelastningen och skapa en förbättrad ruttplanering. Till sist ger vi även förslaget att de utökar sin kravlista för att uppfylla behovet av korrekt utrustade paketstationer och ge dem en tydligare kravbild. En generell och konceptuell arbetsmodell för denna optimering ser ut som följande: 1.       Observera nuvarande leveransrutter och stationer. 2.       Intervjua intressenter (såsom kunder och chaufförer). 3.       Identifiera och sammanställ krav. 4.       Kartlägg stationer på en digital karta. 5.       Heuristisk urvalsprocess.  a.       Undersöka kluster av stationer på digital karta.  b.       Granska stationerna utefter insamlade data.  c.       Bedöm aktiviteten, om fler stationer har hög aktivitet gör en individuell bedömning.  d.       Slå ihop stationerna.  e.       Resterande urval som inte har någon data utförs med 250 meters-regeln. 6.       Skapa optimal rutt med de valda stationerna.

Unmanned flying vehicles (UAVs) are tools that can be used in a variety of scenarios. The most common areas of application are outdoors, where there are not many obstacles to take into consideration when planning a route. In indoor scenarios, the requirements on the path planning system of the UAV becomes stricter, as these scenarios tend to contain more obstacles compared to flying at higher altitude outdoors. Considering a drone with multiple objectives (waypoints to visit), two problems initially come to mind, namely path planning and combinatorial optimization. To finish the objectives in the most effective way, the optimal path between the waypoints needs to be calculated, as well as the order in which the waypoints need to be visited. Another challenge is the fact that the UAV runs on limited battery capacity, and thus might not be able to finish the objectives before running out of battery. Therefore, the combinatorial optimization needs to include visits to a recharging station. The objective of this thesis is to combine and modify methods for path planning and combinatorial optimization in a way that a route can be calculated within a limited time budget, to allow the computation to be executed “on the fly”. The method used for path planning is ANYA, and the two methods used for the combinatorial optimization are ant colony optimization (ACO) as well as the Lin-Kernighan-Helsgaun (LKH) method. The nearest neighbor method (NN) will be used as a baseline for comparison. We propose an algorithm to include the battery constraint in the optimization. To evaluate the algorithms, we measure the computational time, to know if the method works in real-time, and also the estimated time for the UAV to finish the route, which will determine the energy efficiency of the route. We find that the ACO’s solutions improve over time, but require a long computational time, which makes it not suitable for small time budgets. LKH produces better routes than the NN method, and does so within the chosen time budget, as long as the number of waypoints is limited. The algorithm to optimize the trips to the recharging station works better than the previous use of LKH for this specific problem. / Obemannade flygande fordon är verktyg som är användbara inom en mängd områden. Vanligaste miljön för användning av dessa verktyg är i utomhusmiljöer där inte många fysiska hinder existerar. I inomhusscenarion blir kraven på vägplanering större, då dessa miljöer ofta innehåller fler hinder än vid flygning på högre altituder utomhus. Givet ett scenario med en drönare med flera målpunkter att besöka, finns två stora utmaningar, nämligen vägplanering och ruttplanering. För att besöka alla målpunkter behöver vi en metod för att identifiera närmsta, kollisionsfria vägen mellan målpunkterna, men också en metod för att hitta den optimala ordningen att besöka punkterna i. En annan utmaning som uppstår på grund av drönarens begränsade batteritid är att det inte finns någon garanti på att den hinner besöka alla målpunkter innan batteriet tar slut. Därför måste ruttplaneringen innefatta besök till en laddningsstation. Målet med detta examensarbete är att kombinera och modifiera metoder för väg och ruttplanering på ett sätt så en effektiv rutt mellan alla målpunkter kan identifieras, utan att drönaren får slut på batteri, samt med kravet att metoden ska kunna hitta en lösning inom begränsad tid. Metoden som används för vägplanering är ANYA, och de två metoderna som används för ruttplanering är myrkolonioptimering och Lin-Kernighan-Helsgaun-metoden. Närmsta-granne-metoden kommer användas som en baseline för jämförelsen mellan metoderna. Vi föreslår en algoritm som inkluderar batteribegränsningen i ruttplaneringen. För att utvärdera algoritmerna mäter vi beräkningstiden, för att ta reda på om metoden fungerar i realtid. Vi mäter även den uppskattade tiden det tar för drönaren att slutföra rutten, vilket kommer beskriva hur energieffektiv rutten är. Vi finner att myrkolonioptimering ger en bättre och bättre lösning över tid, men kräver en lång beräkningstid, vilket gör den opassande för korta tidsbegränsningar. LKH producerar bättre rutter än närmsta-granne-metoden, och gör det inom den givna tidsramen, så länge antal målpunkter är begränsade. Algoritmen för att optimera besöken till laddstationen fungerar bättre än tidigare appliceringar av LKH på samma problem.

Kurs: Examensarbete i logistik för Civilekonomprogrammet, 4FE19E, VT17 Författare: Martin Norén och Kristoffer Nählstedt Handledare: Hana Hulthén Examinator: Helena Forslund Titel: Hemtjänsten i Växjö kommun - En fallstudie om personal- och ruttplanering Bakgrund: Boendeformen särskilt boende har minskat påtagligt de senaste åren och förväntas minska ytterligare i framtiden. Samtidigt ökar andelen äldre som är i behov av vård och omsorg. Ett sätt att lösa detta är att förlägga omsorgsvården på hemtjänsten. För att klara sitt uppdrag använder hemtjänstenheter idag sig av olika planeringsverktyg som är tänkt att säkerställa att en kostnadseffektiv hemtjänst kan bedrivas samtidigt som den inte ska ge avkall på kvalitén av omsorg. Det ökade trycket på hemtjänsten kräver dock mycket resurser och det är idag svårt att klara av att nå upp till de interna målen som ställts på organisationen under denna föränderliga tid. Därför är det viktigare än någonsin med effektiva planeringsprocesser som kan underlätta och stödja hemtjänsten i sina åtaganden. Syfte: Syftet med studien är att effektivisera hemtjänstenheters planeringsprocesser. Avsikten med effektiviseringen är att uppnå en mer kostnadseffektiv hemtjänst som når måluppfyllelsen inom kontinuitet och brukartid. Metod: Studien är en fallstudie som genomförts i Växjö kommuns omsorgsenhet. Med hjälp av semi-strukturerade intervjuer, insamling av kvalitativ och kvantitativ data har studien kunnat inhämta empiriskt material. En processkartläggning genomfördes och författarna identifierade slöserier och presenterade sedan förbättringsförslag med stöd från åtskilliga teorier. Slutsatser: Författarna lyckades lägga fram förbättringsförslag på alla de tre planeringsprocesser som studien lyckades identifiera. Först lades förbättringsförslag av både kvantitativ och kvalitativ karaktär fram med avsikten att säkerställa kompetensförsörjningen i organisationen. I ruttplaneringsprocessen delade författarna upp hemtjänstenheten Vikaholm i två olika grupper baserat på dess geografiska placeringar och lyckades därigenom förbättra både kontinuiteten och brukartiden samtidigt som kostnaden sjönk för organisationen som helhet. Efter observationer och intervjuer på de olika arbetsgrupperna framkom slutligen fler förbättringsförslag på hur hemtjänstenheter skulle kunna arbeta för att effektivisera sin schemaläggningsprocess ytterligare. Nyckelord: Hemtjänst, äldreomsorg, kontinuitet, brukartid, planering, planeringsprocesser, processkartläggning, ruttplanering, prognostisering. / Course: Examensarbete i logistik för Civilekonomprogrammet, 4FE19E, VT17 Authors: Martin Norén and Kristoffer Nählstedt Tutor: Hana Hulthén Examiner: Helena Forslund Title: Home care for the elders in Växjö municipality - A case study about personnel and route planning Background: In Sweden the amount of people living in an assisted living have reduced significantly during the recent years and is predicted to be reduced even more. At the mean time the amount of elders in need of care is increasing. One way of solving this is by the use of home care. To handle its duty home care units use different kinds of planning tools to ensure quality of the care and that the home care is being cost efficient. The increased demand on the home care service requires a lot of resources and it is today very hard to achieve the internal goals which have been set up by the organisation. Therefore it is now more important than ever with efficient planning processes that can ease and support the home care service in its obligations. Purpose: The purpose of the study is to streamline the planning process in elder care units. The streamlined planning process intends to achieve a more cost efficient elder care, that achieves the objectives concerning continuity and time spent with the elders. Method: The study is a case study, which have been carried out in the municipality of Växjö. With the use of semi-structured interviews, gathering of qualitative and quantitative data the study have been able to obtain empirical material. In order to identify waste the authors used process mapping and then later on proposed improvements with support from a number of theories. Conclusions: The authors managed to propose improvements on all of three identified planning processes. Firstly, the study presented the proposed improvements on the process of ensuring competent personnel with the use of both qualitative and quantitative data. In the route planning process the authors split the home care unit of Vikaholm into two units, based on the locations of the elders. Thereby the authors managed to improve all of the three main goals of the home care unit; continuity, economy and the amount of time the care takers spend with the elders. Observations and interviews on the different units lead to the conclusion of potential improvements on how home care units could work to be more efficient in their scheduling processes.  Keywords: Home care, elder care, time spent with the elder, planning, process planning, process mapping, route planning, forecasting.

Med fokus på distribution behandlar denna rapport planerandet och utförandet av ruttplaneringen hos fallföretaget Gerdas Bröd i Grästorp AB. Utifrån antagandet att resurserna är begränsade hos Gerdas så presenteras ruttförslag utifrån målfunktionerna fyllnadsgrad och minsta möjliga körsträcka. Syftet har aldrig varit att presentera några optimala rutter utan snarare visa hur man på ett rimligt, logiskt och metodiskt sätt kan arbeta med dessa frågor utan att ta särskilt stora resurser i anspråk. Genom datainsamling bestående av intervjuer, observationer och samtal med flera rollinnehavare inom verksamheten har denna fallstudie tagit form. Företagets nuläge och önskan om åtgärder kunde tack vare denna datainsamling identifieras och lägga grunden för vidare analys och rekommendationer. De begränsade resurserna kan i vissa avseenden förklara avsaknaden av planering och styrning inom verksamheten. Det har lett till att chaufförerna i stor omfattning får sköta sig själva i utförandet av inlastning och leverans. Som ett ansikte utåt för verksamheten sköter förarna i praktiken all distribution samtidigt som de hanterar en stor andel av den kontinuerliga kundkontakten. Utförandet av ruttförslag är därför i stor utsträckning till för att stötta dem i deras dagliga arbete. Efter analys och jämförelse mellan teori och empiri mynnar detta ut i en rad olika rekommenderade åtgärder för fallföretaget. Med den kraftigt varierande efterfrågan behöver man vara flexibla internt för att kunna parera mot eventuell över- och underbemanning. Tillgång till fler bilar och förare är därför en av flera åtgärder som rekommenderas. / With focus on distribution, this rapport touches the planning and excecution of routes at the business case Gerdas Bröd in Grästorp AB. From the assumption that the resources are limited at Gerdas this rapport will present route suggestions from the objective functions load factor and minimum mileage. The purpose has never been to present any optimized routes but rather show how to work with these things in a reasonable, logical and methodically way without claiming any remarkable amount of resources. Trough data collection of interviews, observations and dialogs with several employees with different roles within Gerdas, this rapport has developed into this final version. The present of the company and their desire of actions could, thanks to the data collection, be identified and be the foundation of further analysis and recommendation. The limited resources can in some ways explain the lack of planning and management within the distribution of the company. This has led to the drivers being on their own when it comes to the execution of the loading and transporting. As the public face of the company the drivers handles almost everything when it comes to distribution while they manage to handle a big majority of the continuous customer contact. The makings of the route suggestions are primarily to support them in their daily work. After analysing and comparing theory with the company empiricism this will end in a line of recommended actions for the business case. With the greatly varying demand you must be internal flexible to be able to respond to any under- or over staffing. The access to more trucks and drivers is one of several recommended actions.

Traditional shortest path algorithms can efficiently find the optimal paths in graphs using simple heuristics. However, formulating a simple heuristic is challenging under the road network setting since there are multiple factors to consider, such as road segment length, edge centrality, and speed limit. This study investigates how a neural network can learn to take these factors as inputs and yield a path given a pair of origin and destination. The research question is formulated as: Are neural networks applicable to real-time route planning tasks in a roadnetwork?. The proposed metric to evaluate the effectiveness of the neural network is arrival rate. The quality of generated paths is evaluated by time efficiency. The real-time performance of the model is also compared between pathfinding in dynamic and static graphs, using theabove metrics. A staggered approach is applied in progressing this investigation. The first step is to generate random graphs, which allows us to monitor the size and properties of the training graph without caring too many details in a road network. The next step is to determine, as a proof of concept, if a neural network can learn to traverse simple graphs with multiple strategies, given that road networks are in effect complex graphs. Finally, we scale up by including factors that might affect the pathfinding in real road networks. Overall, the training data is optimal paths in a graph generated by a shortest path algorithm. The model is then applied to new graphs to generate a path given a pair of origin and destination. The arrival rate and time efficiency are calculated and compared with that of the corresponding optimal path. Experimental results show that the effectiveness, i.e., arrival rate ofthe model is 90% and the path quality, i.e., time efficiency has a medianof 0.88 and a large variance. The experiment shows that the model has better performance in dynamic graphs than in static graphs. Overall, the answer to the research question is positive. However, there is still room to improve the effectiveness of the model and the paths generated by the model. This work shows that a neural network trained to make locally optimal choices can hardly give a globally optimal solution. We also show that our method, only making locally optimal choices, can adapt to dynamic graphs with little performance overhead. / Traditionella algoritmer för att hitta den kortaste vägen kan effektivt hitta de optimala vägarna i grafer med enkel heuristik. Att formulera en enkel heuristik är dock utmanande för vägnätverk eftersom det finns flera faktorer att överväga, såsom vägsegmentlängd, kantcentralitet och hastighetsbegränsningar. Denna studie undersöker hur ett neuralt nätverk kan lära sig att ta dessa faktorer som indata och finna en väg utifrån start- och slutpunkt. Forskningsfrågan är formulerad som: Är neuronnätverket tillämpliga på realtidsplaneringsuppgifter i ett vägnät?. Det föreslagna måttet för att utvärdera effektiviteten hos det neuronnätverket är ankomstgrad. Kvaliteten på genererade vägar utvärderas av tidseffektivitet. Prestandan hos modellen jämförs också mellan sökningen i dynamiska och statiska grafer, med hjälp av ovanstående mätvärden. Undersökningen bedrivs i flera steg. Det första steget är att generera slumpmässiga grafer, vilket gör det möjligt för oss att övervaka träningsdiagrammets storlek och egenskaper utan att ta hand om för många detaljer i ett vägnät. Nästa steg är att, som ett bevis på konceptet, undersöka om ett neuronnätverk kan lära sig att korsa enkla grafer med flera strategier, eftersom vägnätverk är i praktiken komplexa grafer. Slutligen skalas studien upp genom att inkludera faktorer som kan påverka sökningen i riktiga vägnät. Träningsdata utgörs av optimala vägar i en graf som genereras av en algoritm för att finna den kortaste vägen. Modellen appliceras sedan i nya grafer för att hitta en väg mellan start och slutpunkt. Ankomstgrad och tidseffektivitet beräknas och jämförs med den motsvarande optimala sökvägen. De experimentella resultaten visar att effektiviteten, dvs ankomstgraden av modellen är 90% och vägkvaliteten dvs tidseffektiviteten har en median på 0,88 och en stor varians. Experimentet visar att modellen har bättre prestanda i dynamiska grafer än i statiska grafer. Sammantaget är svaret på forskningsfrågan positivt. Det finns dock fortfarande utrymme att förbättra modellens effektivitet och de vägar som genereras av modellen. Detta arbete visar att ett neuronnätverk tränat för att göra lokalt optimala val knappast kan ge globalt optimal lösning. Vi visar också att vår metod, som bara gör lokalt optimala val, kan anpassa sig till dynamiska grafer med begränsad prestandaförlust.

This thesis presents an approach to solve an optimal path planning problem for a swarm of drones. We optimize and improve information retrieval in area exploration within applications such a ‘Search and Rescue’-missions or reconnaissance missions. For this, dynamic programming has been used as a solving approach for a optimization problem. Different scenarios have been examined for two types of system, a single-agent system and a multi-agent system. First, there have been restrictions on the agents movement in a grid map and for that, optimal paths have been computed for both systems. Thereafter, two different solving approaches within dynamic programming have been tested and compared. The greedy approach which is a standard use where each agent computes the most optimal path from its own perspective and a simultaneous solving approach where the agents compute the most optimal paths according to all agents perspective. The simultaneous solving approach performed better than the greedy approach, which was expected since it is a more swarm optimal approach. However, it has a higher computational complexity which grows exponentially unlike to the greedy approach. Lastly, we discuss the case when the agents are allowed to move in all directions to optimize the information retrieval for the swarm. Here, dynamic programming turns out to have limitations for our use and purpose. For future work, a suggestion is to model the problem with multiple objective functions instead of one as has been done in this thesis. Also, it would be interesting trying another solving method for the problem. To this, I give example of two methods that would be interesting to compare, using model predictive control or a machine learning-based solution such as reinforcement learning. / Denna avhandling presenterar ett tillvägagångssätt för att lösa ett optimalt ruttplanerings problem för en drönarsvärm. Vi optimerar och förbättrar informationsinhämtningen i områdesutforskning inom applikationer som ’Search and Rescue’-uppdrag eller spaningsuppdrag. För detta har dynamisk programmering använts som en lösningsmetod till optimeringsproblem. Olika scenarier har undersökts för två typer av system, ett en-agent system och ett fler-agent system. Först har agenterna varit begränsade hur de har fått röra sig i en rutnätskarta och för det fallet har optimala vägar beräknats för båda systemen. Därefter har två olika lösningssätt inom dynamisk programmering testats och jämförts. Det giriga tillvägagångssättet som är en standardanvändning där varje agent beräknar den mest optimala vägen ur sitt eget perspektiv och en simultan lösningsmetod där agenterna beräknar de mest optimala vägarna enligt alla agenters perspektiv. Den simultana lösningsstrategin presterade bättre än den giriga, vilket var väntat eftersom det är ett mer svärmoptimalt tillvägagångssätt. Den har dock en högre beräkningskomplexitet som växer exponentiellt jämfört med den giriga metoden. Till sist diskuterar vi fallet då agenterna får röra sig i alla riktningar för att optimera informationssökningen för svärmen. Här visar sig dynamisk programmering ha begränsningar för våran användning och syfte. För framtida arbete är ett förslag att modellera problemet med flera mål funktioner istället för en som har gjorts i denna avhandling. Det skulle också vara intressant att prova ett annat lösningssätt för problemet. Till detta ger jag exempel på två metoder som skulle vara intressanta att jämföra, genom att använda modell prediktiv styrning eller en maskininlärningsbaserad lösning såsom förstärkande inlärning.

In route planning the goal is to obtain the best route between a set of locations, which becomes a very complex task as the number of locations increase. This study will consider the problem of transfer bus route planning and examines the feasibility of applying a reinforcement learning method in this specific real-world context. In recent research, reinforcement learning methods have emerged as a promising alternative to classical optimization algorithms when solving similar problems. This due to their positive properties in terms of scalability and generalization. However, the majority of said research has been performed on strictly theoretical problems, not using real-world data. This study implements an existing reinforcement learning model and adapts it to fit the realms of transfer bus route planning. The model is trained to generate optimized routes in terms of time and cost consumption. Then, routes generated by the trained model are evaluated by comparing them to corresponding manually planned routes. The reinforcement learning model produces routes that outperforms manually planned routes with regards to both examined metrics. However, due to delimitations and assumptions made during the implementation, the explicit differences in consumptions are considered promising but cannot be taken as definite results. The main finding is the overarching behavior of the model, implying a proof of concept; reinforcement learning models are usable tools in the context of real-world transfer bus route planning. / Inom ruttplanering är målet att erhålla den bästa färdvägen mellan en uppsättning platser, vilket blir en mycket komplicerad uppgift i takt med att antalet platser ökar. Denna studie kommer att behandla problemet gällande ruttplanering av transferbussar och undersöker genomförbarheten av att tillämpa en förstärkningsinlärningsmetod på detta verkliga problem. I nutida forskning har förstärkningsinlärningsmetoder framträtt som ett lovande alternativ till klassiska optimeringsalgoritmer för lösandet av liknande problem. Detta på grund utav deras positiva egenskaper gällande skalbarhet och generalisering. Emellertid har majoriteten av den nämnda forskningen utförts på strikt teoretiska problem. Denna studie implementerar en befintlig förstärkningsinlärningsmodell och anpassar den till att passa problemet med ruttplanering av transferbussar. Modellen tränas för att generera optimerade rutter, gällande tids- och kostnadskonsumtion. Därefter utvärderas rutterna, som genererats av den tränade modellen, mot motsvarande  manuellt planerade rutter. Förstärkningsinlärningsmodellen producerar rutter som överträffar de manuellt planerade rutterna med avseende på de båda undersökta mätvärdena. På grund av avgränsningar och antagandet som gjorts under implementeringen anses emellertid de explicita konsumtionsskillnaderna vara lovande men kan inte ses som definitiva resultat. Huvudfyndet är modellens övergripande beteende, vilket antyder en konceptvalidering; förstärkningsinlärningsmodeller är användbara som verktyg i sammanhanget gällande verklig ruttplanering av transferbussar.