Fast route planning for a standard car is well explored, lots of research, and many algorithms exist. For trucks or other heavy vehicles, the available research and quick algorithm alternatives dwindle. This thesis focuses on available alternatives for trucks and other vehicles with attributes hindering them from traversing parts of the road network. Attributes like height are one among many, which can hinder a vehicle on its path. These attributes can vary greatly and is the reason why known solutions can’t be applied. Many well-known solutions rely partially on precalculated data regarding the shortest path for its performance. Precalculating for all possible combinations of attributes is not practical due to the number of possible configurations and the amount of computing needed for each one. The implemented solution is derived from multiple existing solutions and was evaluated on a graph representing Sweden’s road network. The solution is sufficiently fast to allow commercial use and allows changes to the road network with nightly updates. The solution is based on trying to predict which roads are more important when searching for the shortest path. With this knowledge, a search for the shortest path can be said to prioritize the before mentioned roads, which results in it finding its goal faster. / Snabb ruttplanering för en vanlig personbil är välutforskat med mycket tillgänglig forskning och många existerande algoritmer. För lastbilar och andra tunga fordon minskar den tillgängliga forskningen och alternativa algoritmer kraftigt. Den här avhandlingen fokuserar på alternativen som existerar för lastbilar, samt andra fordon som har egenskaper vilket blockerar dem från att framföras på delar av vägnätverket. Höjd är ett attribut bland flera som kan hindra ett fordon från att ta sig fram. Dessa egenskaper kan variera kraftigt och är orsaken till varför kända lösningar inte går att applicera. Många välkända lösningar förlitar sig på förberäknad data gällande snabbaste möjliga väg för sin prestanda. Att utföra dessa beräkningar för alla möjliga kombinationer av egenskaper är opraktiskt på grund av antalet möjliga konfigurationer och hur mycket som måste räknas ut för varje. Den implementerade lösningen är en kombination av flera existerande lösningar och utvärderades på en graf som representerar det svenska vägnätet. Lösningen är snabb nog för att tillåta bruk inom det kommersiella och den tillåter förändringar i vägnätet med nattliga uppdateringar. Lösningen bygger på att försöka förutsäga vilka vägar i ett vägnät som är viktigare än andra när det gäller att finna den snabbaste vägen. Med hjälp av det kan man sedan styra en sökning så att den prioriterar dessa vägar och därmed hitta sitt mål fortare.

Jordens befolkning växer och allt fler flyttar in till urbana områden. Detta medför att städer växer, nya byggnader tillkommer och infrastrukturer expanderar. Denna snabba tillväxtfas står i direkt anslutning till ökade översvämningar till följd av de förändringar som görs i naturen. De redan överbelastade dagvattensystemen har i många fall svårt att hantera de befintliga kraven. Till följd av detta uppstår översvämningar vid större regnintensitet och utgör stora omkostnader för samhället. Dagvattenhanteringen brister då det inom kommunens organisationer är otydliga ansvarsfördelningar. För att kunna planera för hållbara städer även i framtiden är det viktigt att hitta en genomförbar lösning gällande både ansvarsfördelningen samt hur dagvattnet ska hanteras på bästa sätt för att uppnå kostnadsfördelar. I denna studie tas det fram en guide för kommunen över hur ansvaret bör fördelas mellan kommun och exploatör i dagvattenfrågan. Guiden bygger på simuleringar och teorier inom optimeringslära för att kunna föreslå rimliga lösningar. Genom dessa simuleringar av dagvattensystemet har mängden vatten som inte ryms i dagvattensystemet kvantifierats. Vidare för att hitta en rimlig alternativ avrinningsväg för det överflödiga dagvattnet har olika algoritmer för kortaste vägen problemet undersökts. Resultaten visar att en klassisk algoritm med en heuristisk funktion som appliceras på kortaste vägen problemet inte kan identifiera den mest lämpliga avrinningsvägen. Detta då den heuristiska funktionen i algoritmen förhindrar att en naturligare avrinningsväg uppströms väljs även om denna skulle ge en mer optimal lösning. / The earth's population is growing and increasingly more people move into urban areas. This means that as cities grow, new buildings are being built and infrastructures are expanding. This rapid growth is directly related to increased floods as a result of man-made changes in nature. The already overloaded storm water systems for rain-, melt-, rinsing and other surplus water cannot often handle the existing demand. Therefore, floods arise at greater rain intensity and pose significant costs to society. Due to an unclear division of responsibility within the municipality's organizations there is a failure to handle the existing storm water problem. In order to be able to plan for sustainable cities in the future, it is important to find a viable solution regarding the responsibility issue and how to best handle the storm water to achieve cost advantage. This study presents a guide for municipalities on how to allocate the responsibility between the municipality and the exploiter. The guide is based on simulations and theories in optimization to propose effective solutions for harmful surplus storm water. Through simulations of the storm water system, the amount of surplus water that does not fit the storm water system capacity has been quantified. In addition, to find a reasonable alternative run-off path for the surplus water, different methods of the shortest path problem have been investigated. The results show that a classical shortest path algorithm with a heuristic function is not the most appropriate alternative. This because the heuristic function in the algorithm prevents the selection of a more natural pathway upstream even though it could be a more optimal solution.

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.

Mobile networks have rapidly evolved over decades, and have arrived at the fifth generation (5G) system in recent years. From 2019, companies started to bring 5G networks into business, providing higher data rates, lower latency, and larger network capacity to the world. One of the main advancements in 5G network systems is the use of millimetre waves for wireless transmission. This not only grants higher throughput with wide bandwidth but also introduces new challenges to the radio access networks in 5G systems. To tackle the challenges, a new type of network, which is called the Integrated Access and Backhaul (IAB) network, has been proposed as a deployment solution for 5G cellular networks. In this work, we investigate the routing mechanism of an IAB network and propose a novel load balancing algorithm that can be applied to the IAB network for improvement in throughput as well as load distribution. We extend the work from previous studies on IAB networks and evaluate the performance of the proposed algorithm in comparison to previous work. Through radio network simulations, we find that the shortest path routing outperforms a greedy algorithm in terms of path selection in the network and that the proposed algorithm achieves load balancing among the network, combined with an improvement in the user throughput. Finally, we conclude our work and suggest directions for future work in the study of IAB networks. / Mobilnäten har utvecklats snabbt de senaste decennierna och är nu framme vid femte generationens system (5G). Under 2019 började telekomföretag lansera 5G-nätverk, med högre datahastigheter, lägre fördröjningar och högre nätverkskapacitet. Ett av de största framstegen inom 5G-nätverkssystem är användningen av millimetervågor för trådlös överföring. Detta ger högre datahastigheter och större bandbredd, men leder också till nya utmaningar för radioaccessnätverket. För att hantera några av dessa har en ny typ av nätverk, kallat Integrated Access and Backhaul (IAB) föreslagits. I det här arbetet undersöker vi routingmekanismer för ett IAB-nätverk och föreslår en ny lastbalanseringsalgoritm som kan användas för att förbättra såväl genomströmning som lastfördelning. Arbetet är en utvidgning av tidigare studier av IAB-nätverk och jämför prestanda för den nya algoritmen med tidigare förslag. Genom simuleringar har vi funnit att shortest path routing överträffar en ”greedy” algoritm när det gäller vägval i nätverket och att den föreslagna algoritmen uppnår såväl lastbalansering som förbättrad genomströmning. Avslutningsvis ges förlag till fortsatt arbete inom studiet av IAB-nätverk.

Planners who are involved in locational decision making often use raster-based geographic information systems (GIS) to quantify the value of land in terms of suitability or cost for a certain use. From a computational point of view, this process can be seen as a transformation of one or more sets of values associated with a grid of cells into another set of such values through a function reflecting one or more criteria. While it is generally anticipated that different transformations lead to different ‘best’ locations, little has been known on how such differences arise (or do not arise). Examples of such spatial decision problems can be easily found in the literature and many of them concern the selection of a set of cells (to which the land use under consideration is allocated) from a raster surface of suitability or cost depending on context. To facilitate GIS’s algorithmic approach, it is often assumed that the quality of the set of cells can be evaluated as a whole by the sum of their cell values. The validity of this assumption must be questioned, however, if those values are measured on a scale that does not permit arithmetic operations. Ordinal scale of measurement in Stevens’s typology is one such example. A question naturally arises: is there a more mathematically sound and consistent approach to evaluating the quality of a path when the quality of each cell of the given grid is measured on an ordinal scale? The thesis attempts to answer the questions highlighted above in the context of path planning through a series of computational experiments using a number of random landscape grids with a variety of spatial and non-spatial structures. In the first set of experiments, we generated least-cost paths on a number of cost grids transformed from the landscape grids using a variety of transformation parameters and analyzed the locations and (weighted) lengths of those paths. Results show that the same pair of terminal cells may well be connected by different least-cost paths on different cost grids though derived from the same landscape grid and that the variation among those paths is affected by how given values are distributed in the landscape grid as well as by how derived values are distributed in the cost grids. Most significantly, the variation tends to be smaller when the landscape grid contains more distinct patches of cells potentially attracting or distracting cost-saving passage or when the cost grid contains a smaller number of low-cost cells. The second set of experiments aims to compare two optimization models, minisum and minimax (or maximin) path models, which aggregate the values of the cells associated with a path using the sum function and the maximum (or minimum) function, respectively. Results suggest that the minisum path model is effective if the path search can be translated into the conventional least-cost path problem, which aims to find a path with the minimum cost-weighted length between two terminuses on a ratio-scaled raster cost surface, but the minimax (or maximin) path model is mathematically sounder if the cost values are measured on an ordinal scale and practically useful if the problem is concerned not with the minimization of cost but with the maximization of some desirable condition such as suitability. / Planerare som arbetar bland annat med att fatta beslut som hänsyftar till vissa lokaler använder ofta rasterbaserade geografiska informationssystem (GIS) för att sätta ett värde på marken med avseende på lämplighet eller kostnad för en viss användning. Ur en beräkningssynpunkt kan denna process ses som en transformation av en eller flera uppsättningar värden associerade med ett rutnät av celler till en annan uppsättning sådana värden genom en funktion som återspeglar ett eller flera kriterier. Medan det generellt förväntas att olika omvandlingar leder till olika "bästa" platser, har lite varit känt om hur sådana skillnader uppstår (eller inte uppstår). Exempel på sådana rumsliga beslutsproblem kan lätt hittas i litteraturen och många av dem handlar om valet av en uppsättning celler (som markanvändningen övervägs tilldelas) från en rasteryta av lämplighet eller kostnad beroende på kontext. För att underlätta GISs algoritmiska tillvägagångssätt antas det ofta att kvaliteten på uppsättningen av celler kan utvärderas som helhet genom summan av deras cellvärden. Giltigheten av detta antagande måste emellertid ifrågasättas om dessa värden mäts på en skala som inte tillåter aritmetiska transformationer. Användning av ordinal skala enligt Stevens typologi är ett exempel av detta. En fråga uppstår naturligt: Finns det ett mer matematiskt sunt och konsekvent tillvägagångssätt för att utvärdera kvaliteten på en rutt när kvaliteten på varje cell i det givna rutnätet mäts med ordinalskala? Avhandlingen försöker svara på ovanstående frågor i samband med ruttplanering genom en serie beräkningsexperiment med hjälp av ett antal slumpmässigt genererade landskapsnät med en rad olika rumsliga och icke-rumsliga strukturer. I den första uppsättningen experiment genererade vi minsta-kostnad rutter på ett antal kostnadsnät som transformerats från landskapsnätverket med hjälp av en mängd olika transformationsparametrar, och analyserade lägen och de (viktade) längderna för dessa rutter. Resultaten visar att samma par ändpunkter mycket väl kan vara sammanbundna med olika minsta-kostnad banor på olika kostnadsraster härledda från samma landskapsraster, och att variationen mellan dessa banor påverkas av hur givna värden fördelas i landskapsrastret såväl som av hur härledda värden fördelas i kostnadsrastret. Mest signifikant är att variationen tenderar att vara mindre när landskapsrastret innehåller mer distinkta grupper av celler som potentiellt lockar eller distraherar kostnadsbesparande passage, eller när kostnadsrastret innehåller ett mindre antal låg-kostnad celler. Den andra uppsättningen experiment syftar till att jämföra två optimeringsmodeller, minisum och minimax (eller maximin) sökmodeller, vilka sammanställer värdena för cellerna som är associerade med en sökväg med summanfunktionen respektive maximum (eller minimum) funktionen. Resultaten tyder på att minisumbanemodellen är effektiv om sökningen av sökvägen kan översättas till det konventionella minsta kostnadsproblemet, vilket syftar till att hitta en väg med den minsta kostnadsvägda längden mellan två terminaler på en ratio-skalad rasterkostyta, men minimax (eller maximin) banmodellen är matematiskt sundare om kostnadsvärdena mäts i ordinär skala och praktiskt användbar om problemet inte bara avser minimering av kostnad men samtidigt maximering av någon önskvärd egenskap såsom lämplighet. / <p>QC 20181002</p>