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.

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>