Vid e-handel av dagligvaror finns stora utmaningar i att skapa förutsättningar för effektiva hemleveranser. Sista milen-distributionen står för den minst transporteffektiva delen av den totala försörjningskedjan då den är svårast att genomföra kostnads- och energieffektiv ruttplanering på. Det matematiska optimeringsproblemet som speglar framtagandet av tillåtna körrutter inom bestämda tidsfönster med flera fordon kallas för Vehicle Routing Problem With Time Windows vilket är ett känt problem som ofta nämns i litteraturen. Projektets syfte var att undersöka energieffekivitet genom att skapa en implementering av metaheuristiken tabusökning för att kunna optimera körrutter för hemleverans. Optimeringen har skett med avseende på såväl antal fordon som den totala körsträckan. Resultatet har analyserats för att kunna dra slutsatser om vilka faktorer som påverkar effektiviteten av sista milen-distributionen. Algoritmen hittar en heuristisk lösning utifrån genererade kundordrar. Detta resulterar i en hög fyllnadsgrad vilket är positivt ur både kostnads- och effektivitetssynpunkt. Resultatet pekar på att ett stort kundunderlag, breda tidsfönster samt ett lager placerat i centrum av staden resulterar i de mest effektiva rutterna. / E-commerce of groceries has major challenges in creating the conditions for efficient home delivery. The last mile-distribution accounts for the least transport-efficient part of the total supply chain as it is most difficult to apply cost and energy efficient route planning at. The mathematical optimization problem that reflects the creation of permissible driving routes within defined time windows with multiple vehicles is called Vehicle Routing Problem With Time Windows which is commonly studied in the literature. The project has been aimed at creating a program using the metaheuristic tabu search to be able to optimize driving routes for home delivery. The optimization has been made with regard to the number of vehicles as well as the total mileage. The results have then been analyzed to be able to answer questions about which factors affect the efficiency of the driving routes. The program can, using input data, calculate the shortest distance with the smallest number of vehicles. This results in a high degree of filling, which is positive from both a cost and efficiency point of view. The result indicates that a large customer base, wide time windows and a warehouse located in the center of the city result in the most efficient routes.

Route optimization aims to optimize routes for vehicles withregards to resource usage. Especially when the vehicle needsto visit multiple customers on the route, a route optimizationtool is beneficiary. The purpose of this study is to comparehuman experience with a route optimization program. This isdone by comparing how a truck driver makes his routes to theroute a GIS-tool has calculated and then see which of theroutes was shorter, measured in kilometers. The data for thisstudy was gathered from a big shipping company. In order toachieve the purpose of this study 10 routes were analysed bya GIS program called ArcGIS. The algorithm used by ArcGISin route optimization is tabu search, this type of program wasused because it is based on heuristic methods that is muchfaster than exact methods. Expert systems are based onknowledge from experts that have been accumulated duringmany years of experience. Providing recommendations basedon probability reasoning instead of absolute answer. Thesekind of systems is often used in GIS programs to improveresults and calculation time. The aim of this study wasanalyze if a optimization program finds a better route than theexpert. This study shows an improvement of 60% of theanalyzed routes. To verify the results of this study anhypothesis test was made which gave a level of significanceby more than 85 %. The routes were optimized to a certainextent even before the study was done due to the driveralready being familiar with the routes in question. Because ofthis the results of this study were lower compared to othersimilar studies. Another reason may be that the coordinatesgiven to us did not always correspond perfectly with actuallocation of the stops. / Ruttoptimering avser att optimera rutter för fordon medminsta möjliga resursåtgång. När fordonet ska besöka ettflertal givna platser är ett ruttoptimeringsverktyg förmånligtatt använda. Denna studie syftar till att jämföra den mänskligaerfarenheten mot ett ruttoptimeringsprogram. Detta har gjortsgenom att jämföra hur en lastbilschaufför har kört en rutt mothur ett GIS-verktyg räknat fram den optimerade färdvägen avsamma rutt. Sedan jämfördes om det fanns skillnader ochvilken av rutterna som var kortast, räknat i kilometer. Datahar hämtats från ett stort fraktföretag. För att nå syftet har 10rutter undersökts i programmet ArcGIS Online som använderalgoritmen tabusökning. En kommersiell beräkningsmetodhar använts då det bygger på heuristiska metoder som ärbetydligt snabbare än exakta metoder. Expertsystem byggerpå erfarenhet som experter har samlat på sig genom åren, deger rekommendationer baserade på sannolikhetsresonemangistället för definitiva svar, dessa system sätts ofta in i GIS för att förbättra resultat och beräkningstider i systemen. Studienresulterade i en förbättring på 60 % av rutterna. Målet meddenna undersökning var att visa om ett optimeringsprogramhittar en bättre rutt än experten. För att verifiera resultaten istudien gjordes en hypotesprövning vilket gav ensignifikansnivå på över 85%. Chauffören har kört dessa rutteri flera år vilket gör att rutterna är optimerade i en viss månredan innan studien gjordes. Det har inverkat på resultatetsom gett ett lågt medelvärde av den procentuella skillnaden,jämfört med tidigare undersökningar. En annan faktor kanvara att koordinaterna i datan från företaget inte helt stämdemed den verkliga placeringen av stoppen på rutterna.

Detta arbete syftar till att undersöka om det är möjligt att med en heuristisk metod skapa giltiga lösningar till ett problem vid planering av stränggjutningsproduktion på SSAB. Planeringsproblemet uppstår när stål av olika sorter ska gjutas under samma dag. Beroende på i vilken ordning olika kundordrar av stål gjuts uppstår spill av olika storlek. Detta spill ska minimeras och tidigare arbete har genomförts på detta problem och resulterat i en matematisk modell för att skapa lösningar till problemet. Det tar i praktiken lång tid att hitta bra lösningar med modellen och frågeställningen är om det går att göra detta med en heuristisk metod för att kunna generera bra lösningar snabbare. Med inspiration från Variable Neighbourhood Search, Simulated Annealing och tabusökning har heuristiker skapats, implementerats och utvärderats mot den matematiska modellen. En av heuristikerna presterar bättre än den matematiska modellen gör på 10 minuter. Matematiska modellens resultat efter 60 minuter körtid är bättre än den utvecklade heuristiken, men resultaten är nära varandra. Körtiden för heuristiken tar signifikant mindre tid än 10 minuter. / This study aims to investigate if it is possible to use a heuristic method to create feasible solution in a Cast Batching Problem at SSAB. The problem occurs when different kinds of steel should be cast during the same day. Depending on which order the groups of different steel is placed different amounts of waste is produced, the goal is to minimize this waste. Earlier work has been done on this problem and resulted in a mathematical model to create feasible solutions to this problem. In practice the time it takes to create good solutions are long and the question is if it is possible to use a heuristic method to generate good solutions in a shorter amount of time. Drawing upon inspiration from metaheuristics such as Variable Neighbourhood Search, Simualted Annealing and Tabu Search multiple heuristics have been created, implemented and evaluated against the mathematical model. One of the heuristics perform better than the mathematical model does in 10 minutes. The result from the mathematical model after 60 minutes is slightly better than the heuristic, but the results are similar. With regards to running time the heuristic takes considerably less time than 10 minutes.

Snow removal is an important optimization problem in countries with snowfall. Bus stops can only be cleared after the adjacent street is cleared. The problem of optimizing snow removal for bus stops in an urban area is a special case of the Travelling Salesman Problem with Time Windows, where each stop only can be cleared after a certain time has passed. The solver Gurobi is used to solve the mathematical model of this problem to optimality. A local search and a tabu search is implemented. The results of the mathematical model are compared to the results of the implemented tabu search method. The results show that if a solution needs to be produced quickly, the tabu search provides better solutions than Gurobi. / Snöröjning är ett viktigt optimeringsproblem i länder med snöfall. Busshållplatsen kan bara röjas efter att den angränsande vägen är röjd. Problemet att optimera snöröjning av busshållplatser i en stad är ett Handelsresandeproblem med tidsfönster, där varje hållplats bara kan röjas efter att en tid har gått. I arbetet har vi implementerat en tabusökning för att hitta snabbt hitta bra tillåtna lösningar till problemet. För att utvärdera prestandan hos tabusökningen har vi också implementerat en matematisk modell och använt Gurobi som lösare. Resultaten visar att tabusökningen är snabbast på att hitta tillåtna lösningar av god kvalité.

The University Course Timetabling Problem (UCTP) is the problem of assigning locations (lecture halls, computer rooms) and time slots (time and date) to a set of events (lectures, labs) while satisfying a number of constraints such as avoiding double-bookings. Many variants of problem formulations exist, and most realistic variants are thought to be NP-hard. A recent trend in solving hard scheduling problems lies in the application of hybrid metaheuristics, where improvements are often found by hybridizing a population-based approach with some form of local search. In this paper, an implementation of a Genetic Algorithm (GA) that solves the UCTP is hybridized with local search in the form of Tabu Search (TS). The results show significant improvements to the performance and scalability over the non-hybridized GA. Two application strategies for the TS are investigated. The first strategy performs a switch-over from the GA to the TS, while the second interleaves the two algorithms. The effectiveness of each application strategy is seen to depend on the characteristics of the individual algorithms. / Schemaläggningsproblemet UCTP (University Course Timetabling Problem) består av problemet att tilldela platser (föreläsningssalar, laborationssalar) och tidpunkter (datum och klockslag) till en mängd tillställningar (föreläsningar, laborationer) under kravet att upprätthålla en mängd restriktioner, exempelvis att undvika dubbelbokningar. Det finns många varianter av problemformuleringen och de flesta realistiska formuleringer anses ge upphov till NP-svåra optimeringsproblem. En förhållandevis ny trend för lösningsmodeller till svåra schemaläggningsproblem ligger i tillämpningen av hybrida metaheuristiker, där förbättringar ofta ses när populationsbaserade algoritmer kombineras med någon typ av lokalsökning. I denna rapport undersöks en UCTP-lösning baserad på en Genetisk Algoritm (GA) som hybridiseratsmed en lokalsökning i form av en Tabusökning (TS). Resultaten visar på signifikanta förbättringar i prestanda och skalbarhet jämfört med den icke-hybridiserade GA:n. Två appliceringsstrategier för TS undersöks. Den första strategin utgörs av att byta algoritm från GA till TS, medan den andra utgörs av att sammanfläta de två algoritmerna. Appliceringsstrategiernas effektivitet ses bero av de individuella algoritmernas egenskaper.