The purpose of this research is to develop a model and solution methodology for selecting and scheduling timely and cost-effective maintenance, rehabilitation, and reconstruction activities (M & R) for each pavement section in a highway network and allocating the funding levels through a finite multi-period horizon within the constraints imposed by budget availability in each period, frequency availability of activities, and specified minimum pavement quality requirements. M & R is defined as a chronological sequence of reconstruction, rehabilitation, and major/minor maintenance, including a "do nothing" activity. A procedure is developed for selecting an M & R activity for each pavement section in each period of a specified extended planning horizon. Each activity in the sequence consumes a known amount of capital and generates a known amount of effectiveness measured in pavement quality. The effectiveness of an activity is the expected value of the overall gains in pavement quality rating due to the activity performed on a highway network over an analysis period. It is assumed that the unused portion of the budget for one period can be carried over to subsequent periods. Dynamic Programming (DP) and Branch-and-Bound (B-and-B) approaches are combined to produce a hybrid algorithm for solving the problem under consideratioin. The algorithm is essentially a DP approach in the sense that the problem is divided into smaller subproblems corresponding to each single period problem. However, the idea of fathoming partial solutions that could not lead to an optimal solution is incorporated within the algorithm to reduce storage and computational requirements in the DP frame using the B-and-B approach. The imbedded-state approach is used to reduce a multi-dimensional DP to a one-dimensional DP. For bounding at each stage, the problem is relaxed in a Lagrangean fashion so that it separates into longest-path network model subproblems. The values of the Lagrangean multipliers are found by a subgradient optimization method, while the Ford-Bellman network algorithm is employed at each iteration of the subgradient optimization procedure to solve the longest-path network problem as well as to obtain an improved lower and upper bound. If the gap between lower and upper bound is sufficiently small, then we may choose to accept the best known solutions as being sufficiently close to optimal and terminate the algorithm rather than continue to the final stage.

The purpose of this research is to develop a model and solution methodology for selecting and scheduling timely and cost-effective maintenance, rehabilitation, and reconstruction activities (M & R) for each pavement section in a highway network and allocating the funding levels through a finite multi-period horizon within the constraints imposed by budget availability in each period, frequency availability of activities, and specified minimum pavement quality requirements. M & R is defined as a chronological sequence of reconstruction, rehabilitation, and major/minor maintenance, including a "do nothing" activity. A procedure is developed for selecting an M & R activity for each pavement section in each period of a specified extended planning horizon. Each activity in the sequence consumes a known amount of capital and generates a known amount of effectiveness measured in pavement quality. The effectiveness of an activity is the expected value of the overall gains in pavement quality rating due to the activity performed on a highway network over an analysis period. It is assumed that the unused portion of the budget for one period can be carried over to subsequent periods. Dynamic Programming (DP) and Branch-and-Bound (B-and-B) approaches are combined to produce a hybrid algorithm for solving the problem under consideratioin. The algorithm is essentially a DP approach in the sense that the problem is divided into smaller subproblems corresponding to each single period problem. However, the idea of fathoming partial solutions that could not lead to an optimal solution is incorporated within the algorithm to reduce storage and computational requirements in the DP frame using the B-and-B approach. The imbedded-state approach is used to reduce a multi-dimensional DP to a one-dimensional DP. For bounding at each stage, the problem is relaxed in a Lagrangean fashion so that it separates into longest-path network model subproblems. The values of the Lagrangean multipliers are found by a subgradient optimization method, while the Ford-Bellman network algorithm is employed at each iteration of the subgradient optimization procedure to solve the longest-path network problem as well as to obtain an improved lower and upper bound. If the gap between lower and upper bound is sufficiently small, then we may choose to accept the best known solutions as being sufficiently close to optimal and terminate the algorithm rather than continue to the final stage.

Unmanned aerial vehicles are becoming more popular in today’s society, which results in the rise of laws intended to maintain safety. To abide by these, while allowing the technology to expand, functioning path-planning algorithms are required.This also includes having methods for detecting and managing obstacles. This project aims to improve an existing path-planning algorithm that is based on A* and implemented in Python.The solution consisted of using functions for finding polytopeintersection,as well as optimizing the collision avoidance and the search algorithm. In addition to that, realistic constraints were implemented on the generated trajectory in order to reflect real-life limitations. The results demonstrated that the paths were always feasible, with respect to input and position constraints. The program’s computation time was also reduced up to 89% of the original run-time. There is, however, still room for improvement since the original code generated a shorter path for the three scenarios it was created for. On the other hand,the improved algorithm could handle a new scenario, which the original code failed to do. / Obemannade flygfarkoster blir alltmer vanliga i dagens samhälle, vilket resulterar i uppkomsten av nya lagar ämnade åt att upprätthålla säkerhet. För att förhålla sig till dessa, samtidigt som teknologin tillåts expandera, krävs fungerande vägplaneringsalgoritmer. Där ingår det även att ha metoder för att upptäcka och hantera hinder. Detta projekt syftar till att förbättra en befintlig vägplaneringsalgoritm som är baserad på A* och implenterad i Python. Lösningsmetoden bestod av att använda inbyggda Python-funktioner ämnade åt att finna skärningar mellan polytoper, samt optimera kollisionshantering och sökalgoritmen. Dessutom infördes realistiska krav på den framställda vägen i syfte om att reflektera verlighetens begränsningar. Resultatet visade att vägarna alltid var genomförbara, med avseende på inmatningsoch positionsrelaterade villkor. Programmets beräkningstid hade även reducerats upptill 89% av den ursprungliga körtiden. Det finns dock utrymme för förbättringar då den ursprungliga koden generar en kortare väg för de tre scenarion den tillverkades för. Däremot kinde den förbättrade algoritmen hantera ett nytt scenario, en ursprungliga koden misslyckades med. / Kandidatexjobb i elektroteknik 2022, KTH, Stockholm