Ant Colony Optimization (ACO) algorithms have been successful in solving a wide variety of NPhard optimization problems. The Traveling Salesman Problem (TSP) has served as a benchmarking problem for many novel ACO algorithms. The slightly harder Dynamic Traveling Salesman Problem (DTSP) is more realistic in the sense that real-time changes happen in the graph belonging to a TSP instance. This thesis studied the original ACO algorithm: the Ant System, and how the amount of pheromone deposited by the ants within the algorithm affected the performance when solving both TSP and DTSP problems. Additionally, 2-opt local search was added to the algorithm, to see how it impacted the performance. We found that when the ants deposited a greater amount of pheromone, the performance for TSP increased, while the performance for DTSP decreased. We concluded that the Ant System in its original form is unsuitable for solving the DTSP. 2-opt local search improved the performance in all instances. / Ant Colony Optimization-algoritmer (ACO) har visat sig vara bra på att lösa många olika NP-svåra optimeringsproblem. För att mäta prestandan för nya ACO-algoritmer har i många fall Handelsresandeproblemet (eng. TSP) använts. Den dynamiska varianten av TSP (eng. DTSP), är ett något svårare problem då förändringar i grafen kan ske i realtid. Denna uppsats utredde hur olika mängder feromon som avges av myrorna inuti algoritmen Ant System, påverkade prestandan för både TSPoch DTSP-instanser. Utöver detta studerades hur den lokala sökningsheuristiken 2-opt påverkade prestandan. Resultaten visade att om myrorna tilläts släppa mer feromoner, ökade prestantan för TSP, men minskade för DTSP. Därav drog vi slutsatsen att algoritmen Ant System i sin ursprungliga form ej är lämplig för att lösa DTSP. Den lokala söknigsheuristiken 2-opt förbättrade prestandan i alla tester.

<p>Genetic algorithms is a method of optimization that can be used tosolve many different kinds of problems. This thesis focuses ondeveloping a framework for genetic algorithms that is capable ofsolving at least the two problems explored in the work. Otherproblems are supported by allowing user-made extensions.The purpose of this thesis is to explore the possibilities of geneticalgorithms for optimization problems and artificial intelligenceapplications.To test the framework two applications are developed that look attwo distinct problems, both of which aim at demonstrating differentparts. The first problem is the so called Travelling SalesmanProblem. The second problem is a kind of artificial life simulator,where two groups of creatures, designated predator and prey, aretrying to survive.The application for the Travelling Salesman Problem measures theperformance of the framework by solving such problems usingdifferent settings. The creature simulator on the other hand is apractical application of a different aspect of the framework, wherethe results are compared against predefined data. The purpose is tosee whether the framework can be used to create useful data forthe creatures.The work showed how important a detailed design is. When thework began on the demonstration applications, things were noticedthat needed changing inside the framework. This led to redesigningparts of the framework to support the missing details. A conclusionfrom this is that being more thorough in the planning, andconsidering the possible use cases could have helped avoid thissituation.The results from the simulations showed that the framework iscapable of solving the specified problems, but the performance isnot the best. The framework can be used to solve arbitrary problemsby user-created extensions quite easily.</p>

Genetic algorithms is a method of optimization that can be used tosolve many different kinds of problems. This thesis focuses ondeveloping a framework for genetic algorithms that is capable ofsolving at least the two problems explored in the work. Otherproblems are supported by allowing user-made extensions.The purpose of this thesis is to explore the possibilities of geneticalgorithms for optimization problems and artificial intelligenceapplications.To test the framework two applications are developed that look attwo distinct problems, both of which aim at demonstrating differentparts. The first problem is the so called Travelling SalesmanProblem. The second problem is a kind of artificial life simulator,where two groups of creatures, designated predator and prey, aretrying to survive.The application for the Travelling Salesman Problem measures theperformance of the framework by solving such problems usingdifferent settings. The creature simulator on the other hand is apractical application of a different aspect of the framework, wherethe results are compared against predefined data. The purpose is tosee whether the framework can be used to create useful data forthe creatures.The work showed how important a detailed design is. When thework began on the demonstration applications, things were noticedthat needed changing inside the framework. This led to redesigningparts of the framework to support the missing details. A conclusionfrom this is that being more thorough in the planning, andconsidering the possible use cases could have helped avoid thissituation.The results from the simulations showed that the framework iscapable of solving the specified problems, but the performance isnot the best. The framework can be used to solve arbitrary problemsby user-created extensions quite easily.

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é.

Reliable electricity distribution systems are crucial; hence, the maintenance of such systems is highly important, and in Sweden strictly regulated. Poorly planned maintenance scheduling leads unnecessary driving which contributes to increased emissions and costs.  Maintenance planning is similar to the capacitated vehicle routing problem, CVRP, a combinatorial optimization problem. Each route has an origin location, in this case is the office of the maintenance worker. The origin is the starting and ending point of each route. In addition, conditions such as due date for inspection has an impact on how components in the network are prioritized. The maintenance planning problem is likely NP-hard.  Given the above, the aim for this study is to develop a heuristic algorithm that efficiently generates daily inspection schedules on a yearly basis. There are multiple tools and algorithms already developed to solve these kinds of problems, for example the Google’s OR-Tools library, which provide optimal or near optimal solutions to VRP problems. The time complexity of those tools makes them impractical to use when planning maintenance of electrical networks since they can contain many thousands of components i.e., nodes. The main aim of this study is to develop an algorithm that provides a solution good enough compared to the solutions computed by the tools mentioned above but with a lower time complexity.  In order to develop and test the algorithm an electrical distribution network data is required. Due to the sensitive nature of this data, a simulated network is generated in place of using real data. The simulated network is based on land use data from the city of Uppsala, Sweden, and is based on the spatial distribution of an existing electrical distribution network in Örebro, Sweden. The scheduling and routing algorithm developed works by dividing candidate nodes into subsets. The division is done by using Density-based spatial clustering of applications with noise (DBSCAN). The clustering is made by querying all objects that requires an inspection to be performed that year. As a post-processing step all noise points are appended to the closest neighboring cluster. Then a distance map is computed for the objects within each cluster. An inspection day route is computed by applying a greedy forward selection in each cluster, always selecting a random unvisited starting node until all nodes within the cluster has been visited. This is then repeated 100 times for each cluster, finally keeping the best iteration. The number of iterations is based on evaluating the gain per additional iteration which appear to be logarithmic. The greedy forward selection means that the algorithm has a linear time complexity after the clustering and distance map computation is done.  The algorithm is evaluated by comparing the total driving time for the computed route to the output routes of a modified Concorde TSP solution and the solution of Google’s VRP solver.  The results show that the algorithm performs better in areas with shorter average neighborhood distance and driving time of the output route decrease with higher number of iterations. Although the VRP based baselines methods return solutions with inspection routes that are roughly 25% shorter than the proposed method, for realistic problem sizes the proposed method uses less compute resources i.e., time and memory. Furthermore, while the proposed method has a linear time and space complexity whereas the baselines have exponential time complexity. Finally, the VRP based back-optimization solutions are not practical in real settings when inspection tasks are added / changed daily due to service tasks and unfinished routes or when the number of nodes is substantially larger than the roughly 1 000 nodes used in the evaluation.Due to the sensitive nature of electrical distribution data the performance of the algorithm could not be compared to actual maintenance schedules. But with all likelihood the computed schedules should be significantly more efficient than manually planned schedules. / Att ha pålitliga elnät är essentiellt för ett välfungerande samhälle därav är underhållet av sådana system av stor vikt och i Sverige strikt reglerat. Dåligt planerade besiktningar leder till onödig körning inom nätet vilket bidrar till ökade utsläpp och kostnader. Underhållsplanering liknar problemet, CVRP, ett kombinatoriskt optimeringsproblem. Varje rutt har en ursprungsplats, i detta fall är besiktningsmannens kontor. Kontoret är start- och slutpunkten för varje rutt. Dessutom har villkor som sista besiktningsdatum en inverkan på hur komponenter i nätet prioriteras. Underhållsplaneringsproblemet är sannolikt NP-svårt. Mot bakgrund av ovanstående är syftet med denna studie att utveckla en algoritm som effektivt genererar dagliga besiktningsscheman på årsbasis. Det finns redan flera verktyg och algoritmer som har utvecklats för att lösa den här typen av problem, till exempel Googles OR-Tools, som beräknar optimala eller nästan optimala lösningar på VRP-problem. Tidskomplexiteten hos dessa verktyg gör dem opraktiska att använda vid planering av underhåll av elnät eftersom dessa kan innehålla många tusen komponenter, dvs noder. Huvudsyftet med denna studie är att utveckla en algoritm som ger en lösning som är tillräckligt bra jämfört med de lösningar som beräknas av de verktyg som finns idag men med en lägre tidskomplexitet.För att utveckla och testa algoritmen krävs elnätsdata. På grund av denna datas känsliga natur genereras ett simulerat nätverk istället för att använda riktiga data. Det simulerade nätet är baserat på markanvändningsdata från Uppsala, Sverige, och på den rumsliga distributionen av ett befintligt eldistributionsnät i Örebro, Sverige. Schemaläggnings- och ruttalgoritmen som utvecklats fungerar genom att dela upp kandidatnoder i delmängder. Uppdelningen görs genom att använda densitetsbaserad spatial klustring (DBSCAN). Klustringen görs genom att välja ut alla objekt som behöver besiktigas det året. Som ett efterbehandlingssteg läggs alla bruspunkter till det närmaste intilliggande klustret. Sedan beräknas en distansmatris för objekten inom varje kluster. En besiktningsrutt beräknas genom att inom varje kluster alltid starta på en slumpmässig vald ej besökt startnod. Därefter väljs den närmsta nod tills alla noder inom klustret har besökts. Detta upprepas sedan 100 gånger för varje kluster, och slutligen behålls den bästa iterationen. Antalet iterationer baseras på att utvärdera förbättringen per ytterligare iteration - som verkar vara logaritmisk. Det här innebär att algoritmen har en linjär tidskomplexitet efter att klustringen och beräkningen av distansmatrisen har genomförts. Algoritmen utvärderas genom att jämföra den totala körtiden för den beräknade rutten med rutterna för en modifierad Concorde TSP-lösning och lösningen från Googles VRP-solver. Resultaten visar att algoritmen presterar bättre i områden med kortare genomsnittligt avstånd mellan noderna och körtiden för besiktningsrutterna minskar med ett högre antal iterationer. Även om de existerande VRP-algoritmerna returnerar lösningar med besiktningsrutter som är cirka 25 % kortare än den föreslagna metoden, så är dessa inte realistiska att använda när antalet noder närmar sig de av ett riktigt elnät.Dessutom, medan den föreslagna metoden har en linjär tids-och rymdkomplexitet medan de existerande VRP-algoritmerna har en exponentiell tidskomplexitet. Slutligen är de VRP-baserade algoritmerna inte praktiska i verkligheten när besiktningar läggs till eller ändras eller när antalet noder är avsevärt större än de cirka 1 000 noder som används i utvärderingen. På grund av den känsliga karaktären hos elnätsdata kunde algoritmens prestanda inte jämföras med faktiska besiktningsscheman. Men med all sannolikhet borde de beräknade besiktningsschemana vara betydligt effektivare än manuellt planerade scheman.

The purpose of this paper is to increase the routing efficiency of two previously separate commodity transports. By combining them in a common, multi-commodity network flow (MCNF). A Mixed Integer Linear Programming (MILP) model is used to minimize the mileage that is needed to fulfill demand in the different destinations of the transport network. Input needed for the model was mileage between destinations, which was obtained from open data. And the demand of respective commodity was received from documents and an estimation. To solve the stated problem approximations and simplifications was needed because it showed a NP-complete problem. The aim is to produce a result that shows a lower mileage than a reference measure from the present situation with separate transports. The result showed an optimized solution of 1939 km. Which was a difference of 1941 km from the reference measures, that summarized to 3880 km. Despite this the result from the model shows an effective optimization. Which makes the use of MILP for minimizing mileage inside a MCNF problem, a useful approach for solving the stated problem. / Syftet med arbetet var att effektivisera körsträckor för två tidigare separata transporter av olika produkter. Genom att kombinera dem till en gemensam transport i ett multi-commodity network flow (MCNF). Med en Mixed Integer Linear Programming (MILP) modell minimeras de körsträckor som krävs för att fylla efterfrågan i transportnätverkets adresser. In-data som krävdes för att en modell skulle kunna utföras var körsträckor mellan olika adresser, vilket hämtades från öppen data. Samt efterfrågan på produkter som erhölls från dokument och estimering.  Då problemet som skulle lösas visade på hög beräkningskomplexitet behövde ett antal approximationer och förenklingar verkställas. Målet var att visa på ett resultat där körsträckor hade förminskats relativt till ett referensmått från nuläget. Där resultatet visade på en optimerad lösning på 1939 km. Vilket var en differens på 1941 km från de referensmåttet som summerades till 3880 km. Modellens resultat visar trots det en effektiv optimering. Vilket gör att användningen av MILP för att minimera körsträckor inom MCNF problem, är ett effektivt tillvägagångssätt att lösa det motiverade problemet.