This diploma thesis focuses on meta-heuristic algorithms and their ability to solve difficult optimization problems in polynomial time. The thesis describes different kinds of meta-heuristic algorithms such as genetic algorithm, particle swarm optimization or ant colony optimization. The implemented application was written in Java and contains ant colony optimization for capacitated vehicle routing problem and particle swarm optimization which finds the best possible parameters for ant colonies.

The following thesis deals with optimization of freight transport planning. The goal is to minimize expenses connected to transportation, which emerge from travelled distance. The expenses can be heavily reduced, if the routes are correctly planned, especially when there is a large number of customers to be served. This thesis focuses on solving the problem by using the evolutional algorithms, that are optimization methods based on principles of evolution. Thesis concentrates on Heterogeneous Fixed Fleet Vehicle Routing Problem. Thesis introduces multiple evolutional algorithms and their results are compared. The best algorithm, evolutional strategy with local neighbourhood search, achieves similar, for certain tasks even better results, than other existing evolutional algorithms, created to solve given problem.

Die Tourenbildung beschäftigt sich mit der Konstruktion kostengünstiger Transportrouten zur Belieferung von Verbrauchern. Sie ist eine der weitreichensten Erfolgsgeschichten des Operations Research. Das starke Interesse an diesen Problemen durch Industrie und Forschung liegt zum einen am wirtschaftlichen Potenzial der Tourenbildung und -optimierung, zum anderen macht ihr Reichtum an Struktur sie zu einem faszinierenden Forschungsgebiet. In der vorliegenden Arbeit soll ein Überblick über einige, u. a. auch neuere mathematische Modell- und Lösungsansätze gegeben werden. Auf Grund der hohen Anzahl der Veröffentlichungen auf diesem Gebiet wird nicht zwingend ein Anspruch auf die vollständige Darlegung aller möglichen Problemstellungen im Zusammenhang mit dem TSP sowie dem VRP und deren Lösungsansätze erhoben. An den gegebenen Stellen wird statt dessen auf weiterführende Literatur verwiesen.

El sector de servicio de mantenimiento demuestra un crecimiento continuo desde la incorporación de máquinas para el desarrollo de operaciones. En el Perú, este sector tiene un crecimiento lento, a pesar de ello, algunas empresas de mantenimiento han encontrado oportunidades en nichos poco explorados, como los mantenimientos a cajeros automáticos. Sin embargo, el tipo de servicio que brindan no cumplen ciertos aspectos esenciales para satisfacer la demanda, debido al exceso de tiempo en la atención del servicios y llegada a destiempo para la atención. Es por ello, que el objetivo principal del proyecto es reducir el lead time para el cumplimiento del cronograma anual, ya que se presencia una pérdida del 33.44% de la facturación del servicio de mantenimiento en el año 2019. Por esta razón, se diseña un modelo de gestión de servicio de mantenimiento que comprende la asignación de ruta por el vehicle routing problem mediante la distancia euclidiana y la estandarización de procesos mediante el estudio de tiempos que será validado mediante la simulación del software Arena. Asimismo, se analiza un flujo de caja económico del cual se obtiene un índice de rendimiento (RBC) de S/. 2.31. Finalmente, ha sido posible la reducción del lead time y el cumplimiento del cronograma de mantenimiento. / The maintenance service sector shows continuous growth since the incorporation of machines for the development of operations. In Peru, this sector has a slow growth, despite this, some maintenance companies have found opportunities in little-explored niches, such as maintenance of ATMs. However, the type of service they provide does not meet certain essential aspects to satisfy the demand, due to the excess time in the service and arrival at the wrong time for the service. That is why the main objective of the project is to reduce the lead time for compliance with the annual schedule, since there is a 33.44% loss of the maintenance service billing in 2019. For this reason, a Maintenance service management model that includes the route assignment for the vehicle's routing problem using the standard Euclidean distance and the laization of processes through the study of times that will be validated through the simulation of the Arena software. Likewise, an economic cash flow is analyzed from which a performance index (RBC) of S /. 2.31. Finally, it has been possible to reduce lead time and meet the maintenance schedule. / Trabajo de investigación

Nowadays, assembly robots are increasingly used in the manufacturing industry to replace or collaborate with human labors. This is the goal of the dual arm assembly robot developed by ABB. With the rapid upgrading in consumer electronics products, the lifetime of an assembly line could be only a few months. However, even for experienced programmers, to manually construct a good enough assembly sequence is time consuming, and the quality of the generated assembly sequence is not guaranteed. Moreover, a good robot assembly sequence is important to the throughput of an assembly line. For dual arm robots, it is also important to obtain a balance between the two arms, as well as handling scheduling conflicts and avoiding collisions in a crowded environment. In this master thesis, a program is produced to automatically generate the optimal assembly sequence for a class of real-world assembly cases. The solution also takes the layout of the assembly cell into account, thus constructing the best combination of cell layout, workload balancing, task sequence and task scheduling. The program is implemented using Google OR-Tools – an open-source support library for combinatorial optimization. A customized search strategy is proposed and a comparison between this strategy and the built-in search strategy of Google OR-Tools is done. The result shows that the used approach is effective for the problem study case. It takes about 4 minutes to find the optimal solution and 32 minutes to prove its optimality. In addition, the result also shows that the customized search strategy works consistently with good performance for different problem cases. Moreover, the customized strategy is more efficient than built-in search strategy in many cases. / Numera används monteringsrobotar alltmer inom tillverkningsindustrin för att ersätta eller samarbeta med människor. Detta är måluppgiften för den tvåarmiga monteringsroboten, YuMi, som utvecklats av ABB. Med den korta produktlivslängden för hemelektronikprodukter kan livslängden för en monteringslinje vara ett fåtal månader. Även för erfarna robotprogrammerare är det svårt och tidsödande att manuellt konstruera en tillräckligt bra monteringsordning, och dessutom kan resultatets kvalitet inte garanteras. En bra monteringsordning är nödvändig för genomströmningen i en monteringslinje. För tvåarmiga robotar, är det också viktigt att få en balans mellan de två armarna, samt hantering av schemakrockar och undvika kollisioner i en trång miljö. I detta examensarbete har ett program skrivits, som automatiskt genererar optimala lösningar för en klass av verkliga monteringsfall. Lösningen tar hänsyn till utformningen av monteringscellen och arrangerar cellen på bästa sätt, balanserar arbetsbelastningen, ordnar och tidsbestämmer uppgifter. Programmet använder sig av Google OR-Tools – ett öppet kodbibliotek för kombinatorisk optimering. Dessutom föreslås en skräddarsydd sökstrategi, som jämförs med Google OR-Tools inbyggda sökstrategi. Resultatet visar att den använda metoden är effektiv för problemtypen. Det tar ungefär 4 minuter att hitta den optimala lösningen och 32 minuter för att bevisa optimalitet. Dessutom visar resultatet att den anpassade sökstrategin konsekvent har en bra prestanda för olika problemfall. Dessutom är den anpassade strategin effektivare än den inbyggda sökstrategin i många fall.

Providing advanced health care at home rather than in a hospital creates a greater quality of life for patients and their families. It also lowers the risk of hospital-acquired infections and accelerates recovery. The overall cost of care per patient is decreased. Manual scheduling of patient visits by health care professionals (HCPs) has become a bottleneck for increased patient capacity at SABH, a ward providing advanced pediatric health care at home (“Sjukhusansluten Avancerad Barnsjukvård i Hemmet” in Swedish), since many parameters need to be taken into account during scheduling. This thesis aims to increase the efficiency of SABH’s daily scheduling of personnel and resources by designing an automated scheduler that constructs a daily schedule and incorporates changes in it when needed in order to remove scheduling as a limitation for increased patient capacity. Requirements on a feasible schedule are identified in cooperation with SABH and literature is investigated about similar areas where the scheduling process has been automated. The scheduling is formulated as a computerized problem and investigated from the perspective of theoretical computer science. We show that the scheduling problem is NP-hard and can therefore not be expected to be solved optimally. The algorithm for scheduling the visits minimizes violations of time windows and travel times, and maximizes person continuity and workload balancing. The algorithm constructs an initial solution that fulfills time constraints using a greedy approach and then uses local search, simulated annealing, and tabu search to iteratively improve the solution. We present an exact rescheduling algorithm that incorporates additional visits after the original schedule has been set. The scheduling algorithm was implemented and tested on real data from SABH. Although we found the algorithm to be efficient, automatic transfer of data from the patient journal system is an imperative for the scheduler to be adopted. / Barn som får avancerad sjukvård hemma istället för på sjukhus tillfrisknar ofta snabbare och risken för vårdrelaterade infektioner minskar. Barnen och deras familjer blir mer välmående av att få vistas i sin hemmiljö. På Astrid Lingrens barnsjukhus i Stockholm erbjuds avancerad hemsjukvård av avdelningen Sjukhusansluten Avancerad Barnsjukvård i Hemmet (SABH). För att schemalägga när patienterna ska besökas av sjukvårdspersonalen behöver många olika faktorer beaktas, detta sker idag helt manuellt. Den manuella schemaläggningen utgör en naturlig begränsning av SABHs patientkapacitet. Denna uppsats syftar till att effektivisera schemaläggningsprocessen hos SABH genom att föreslå en automatiserad lösning som hanterar koordinering av personal och resurser och dem förändringar som behöver göras i schemat under dagen, för att få bort schemaläggningsprocessen som ett hinder mot ökad patientkapacitet. Krav på schemaläggningen identifieras i diskussion med SABH och genom att studera litteratur kring liknande områden där schemaläggning lösts automatiserat. Vi formulerar schemaläggningen som ett datologiskt problem och analyserar det med utgångspunkt i teoretisk datalogi. Vi visar att problemet är NP-svårt och därför inte kan förväntas lösas optimalt inom rimlig tid. Vår lösning approximerar istället fram ett rimligt svar, där fokus hos algoritmen är att patienterna ska besökas de tider de behöver, personalens restider ska vara så korta som möjligt samtidigt som arbetsbördan hos personalen ska vara så lika fördelad som möjligt och patienterna ska, i den mån det är möjligt, få vård av samma personal. Med en girig algoritm konstrueras ett initialt schema som uppfyller de grundläggande kraven, detta schema förbättras med lokalsökning, simulated annealing och tabusökning. En exakt lösning framställs för uppdatering av schemat. Algoritmen för att lägga ett dagligt schema (utan uppdateringar) implementerades och testades med riktigt data från SABH. Vår algoritm visade sig vara effektiv, men för att kunna göra hela schemaläggningsprocessen effektiv behöver den integreras med journalsystemet.

<p>Машинско учење и неуронске мреже су алати који налазе све већу<br />примену у решавању практичних проблема. За креирање неуронске<br />мреже потребан је скуп података, који може бити прикупљен на<br />различите начине. У овој тези је показано да се подаци за тренинг<br />неуронске мреже могу успешно прикупити креирањем веб игре.<br />Сакупљени скуп података садржи стратегије решавања проблема<br />трговачког путника и проблема рутирања возила.</p> / <p>Mašinsko učenje i neuronske mreže su alati koji nalaze sve veću<br />primenu u rešavanju praktičnih problema. Za kreiranje neuronske<br />mreže potreban je skup podataka, koji može biti prikupljen na<br />različite načine. U ovoj tezi je pokazano da se podaci za trening<br />neuronske mreže mogu uspešno prikupiti kreiranjem veb igre.<br />Sakupljeni skup podataka sadrži strategije rešavanja problema<br />trgovačkog putnika i problema rutiranja vozila.</p> / <p>Machine learning and neural networks are the tools that are finding more and<br />more fields of application in solving practical problems. For the creation of<br />the neural networks, data can be successfully collected by creating a web<br />game. The data collected in this manner has strategic solutions for the<br />problems of Travel salesperson problem and vehicle routing problem.</p>

The purpose of this thesis is to investigate how tractor swapping can be implemented in Vehicle Routing Problems (VRP) with electric heavy goods vehicles, and to evaluate how a model that allows for tractor swapping performs, in terms of schedule cost, against a model that does not. Hence, this thesis introduces a new rich VRP variant which includes tractor swapping, as well as time windows, pickup and delivery, and electric vehicles. The model is named Electric Tractor Swap Vehicle Routing Problem (E-TSVRP) and is formulated as a mixed integer linear program. As for the solver, Gurobi is used. The results show that utilizing tractor swapping can reduce the total cost of serving customers significantly by reducing en-route charging and utilizing drivers more efficiently. Specifically, it is shown that the cost reduction comes mainly from reducing driver work time. By demonstrating how tractor swapping works and how the results can be visualized on smaller cases, this thesis aims to serve as a foundation for future research within the field. To be able to fully implement the model for large logistics problem instances however, alternative solution methods such as heuristics or metaheuristics should be developed so that the problems can be solved in a reasonable amount of time. / Syftet med denna uppsats är att undersöka hur traktorbyten kan implementeras i "Vehicle Routing Problem" (VRP) med tunga, elektriska lastfordon, och att utvärdera hur en modell som tillåter traktorbyten presterar mot en modell som inte tillåter det, med avseende på den totala schemakostnaden. I uppsatsen introduceras därför en ny och generell VRP som har stöd för traktorbyten, men som också modellerar energikonsumtion och laddning av elektriska lastbilar, samt tillåter tidsfönster för när leveranser kan levereras och hämtas upp på godtyckliga platser. Modellen kallas för "Electric Tractor Swap Vehicle Routing Problem" (E-TSVRP) och formuleras som ett linjärt, blandat heltalsprogram. Programmet löses sedan med lösaren Gurobi. Resultaten visar att utnyttjandet av traktorbyten kan märkbart minska den totala kostnaden av att leverera varor till kunder genom att minska tiden som föraren väntar på att traktorn laddar. Mer specifikt tillåts möjligheten att byta till en ny traktor när den tidigare får slut på energi, vilket möjliggör en högre utnyttjandegrad av förarna, och den fakturerade tiden associerad till förarna kan minskas. Detta sker genom en avvägning mellan å ena sidan högre hårdvarukostnader för fler traktorer och å andra sidan lägre förarkostnader. Genom att demonstrera hur traktorbyten fungerar och hur resultaten kan visualiseras på mindre transportproblem, strävar denna uppsats efter att verka som en grund för framtida forskning. För att modellen ska kunna användas för stora logistikproblem bör dock alternativa lösningsmetoder som till exempel lösningsheuristiker eller metaheuristiker utvecklas så att problemen kan lösas inom en rimlig tid.

As the transport industry shifts towards Battery Electric Vehicles (BEVs) the need for accurate route planning rises. BEVs have reduced range compared to traditional fuel based vehicles, and the range can vary greatly depending on ambient conditions and vehicle load. Existing research focuses more on the theoretical algorithms, and often have none or very simple vehicle models, leaning towards consumer cars instead of heavy duty trucks. Vehicle Route Planning (VRP) is a wide research area, and this thesis focuses on the Shortest Path subproblem. Contraction Hierarchies (CHs) is a commonly used family of algorithms for finding shortest paths in road networks, and is prevalent in the research frontier. CHs however comes with certain drawbacks, such as having to perform a costly preprocessing phase whenever metrics change, and not being able to share map data between multiple vehicles in a fleet. This thesis extends CHs to support a mixed fleet, with fast metric updates and support for more detailed cost optimization goals. This is done by implementing Customizable Contraction Hierarchies (CCHs), but with custom data structures and customization phase. This implementation allows map data to be shared between vehicles in a fleet, and keeps each vehicle's edge weights separate. The edge weights can be updated quickly, as the customization phase scales linearly with the size of the map. The implementation also supports edge weights that do not adhere to triangle inequality, which the previous research did not. Experiments are executed on a map of Stockholm and a synthetic map, to test the algorithm's performance, verify correctness, and stress the importance of accurate metrics for optimization goals. The CCH performed as expected, if not better, and its correctness is upheld. The implementation is fit to be integrated into a route planner, but further research should be conducted to see how it meshes with other parts of VRP, such as time windows, turn costs, and charging stations. / När transportindustrin övergår till batterielektriska fordon ökar behovet av rigorös ruttplanering. Batterielektriska fordon har minskad räckvidd jämfört med traditionella bränslebaserade fordon, och räckvidden kan variera stort beroende på omgivningsförhållanden och fordonets belastning. Existerande forskning fokuserar mer på de teoretiska algoritmerna och har ofta inga eller mycket enkla fordonsmodeller, som liknar mer konsumentbilar istället för tunga lastbilar. Ruttplanering är ett brett forskningsområde, och denna avhandling fokuserar på underproblemet att hitta kortaste vägen. Kontraktionshierarkier är en välanvänd familj av algoritmer för att hitta kortaste vägen i ett vägnät, och är prevalent i forskningsfronten. Kontraktionshierarkier har dock vissa nackdelar, som att de behöver utföra en kostsam förbehandlingsfas när parametrar ändras, och att kartdatan inte kan delas mellan flera fordon i en flotta. Den här avhandlingen utökar Kontraktionshierarkier för att stödja en blandad fordonsflotta, med snabba uppdateringar av parametrar och stöd för mer detaljerade optimeringsmål. Detta görs genom att implementera Anpassningsbara Kontraktionsierarkier, men med anpassade datastrukturer och anpassningsfas. Denna implementering tillåter att kartdata delas mellan fordonen i en flotta, och håller varje fordons kantvikter separat. Kantvikterna kan uppdateras snabbt, eftersom anpassningsfasen skalas linjärt med storleken på kartan. Implementationen stöder också kantvikter som inte följer triangelojämlikheten, vilket den tidigare forskningen inte gjorde. Experiment utförs på en karta över Stockholm och en syntetisk karta, för att testa algoritmens prestanda, verifiera korrekthet, och betona vikten av detaljerade parametrar i optimeringsmål. Anpassningsbara Kontraktionshierarkier presterade som förväntat, om inte bättre, och dess korrekthet uppehölls. Implementeringen är lämplig för att integreras i en ruttplanerare, men ytterligare forskning bör genomföras för att se hur den passar ihop med andra delar av ruttplaneringsproblemet, så som tidsfönster, svängkostnader och laddstationer.

This thesis addresses route planning of Battery Electric Heavy-Duty Commercial Vehicles to enhance the reliability of electric vehicle transport. Collaborating with Scania, a Swedish truck manufacturing company, the goal is to develop a pipeline that uses open source data from OpenStreetMap and performs a modified Contraction Hierarchy in order to create a graph that can be used as input to a modified Vehicle Routing Problem formulation using Mixed Integer Programming. The input graph is preprocessed to support a Battery Electric Heavy-Duty Commercial Vehicle model in order to more accurately predict energy consumption. The challenges lie in balancing computational efficiency and electric vehicle characteristics. The implemented pipeline demonstrates success but initial tests show that a naive version of the pipeline, not implementing Contraction Hierarchies, can perform better. Several speedups can be made in order to improve the efficiency of the pipeline, the main being in programming in a more efficient programming language than Python. Further testing is needed for larger input graphs to assess performance accurately.