@phdthesis{Zazai2020, author = {Zazai, M. Fawad}, title = {Berechnung der Trajektorien f{\"u}r die Entwicklung von optimalen Routen}, editor = {F{\"u}genschuh, Armin}, issn = {2627-6100}, doi = {10.26127/BTUOpen-5228}, url = {http://nbn-resolving.de/urn:nbn:de:kobv:co1-opus4-52286}, school = {BTU Cottbus - Senftenberg}, year = {2020}, abstract = {Die Konstruktionsplanung von neuen Transitrouten oder Energieleitungen auf einem topografischen Gel{\"a}nde wird von Ingenieuren in der Regel manuell vorgenommen, ohne dass eine Optimalit{\"a}t garantiert werden kann. Wir stellen einen neuen Ansatz zur Berechnung von Trajektorien f{\"u}r die Entwicklung neuer optimaler Transitrouten und Energieleitungen zwischen zwei Standorten auf einer Untermannigfaltigkeit U von IR³ vor. Diese Untermannigfaltigkeit repr{\"a}sentiert die Topographie eines Gel{\"a}ndes. U wird n{\"a}herungsweise durch ein spezielles gewichtetes Gitternetz modelliert. Auf diesem Gitternetz werden die k{\"u}rzesten Wege f{\"u}r den Bau neuer Routen bestimmt, wobei wir drei Optimierungskriterien betrachten werden: Routen mit minimaler L{\"a}nge, Routen mit geringsten Baukosten und Routen mit minimalen absoluten H{\"o}henvariationen oder minimalen absoluten Steigungen. Anschließend wird eine Kombination dieser Kriterien gebildet, um dieses Problem zu einem multikriteriellen Optimierungsproblem zu erweitern. Ein Algorithmus f{\"u}r den k{\"u}rzesten Weg, wie der Dijkstra-Algorithmus, wird verwendet, um optimale Kompromisse f{\"u}r die Konstruktion neuer Routen zu berechnen.}, subject = {K{\"u}rzeste Wege; Trajektorienplanung; Optimale Routen; Multikriterielle Optimierung (Pareto-Front); Geoinformationssysteme; Shortest paths; Trajectory planning; Optimal routes; Multi-criteria optimization (Pareto frontier); Geographic information system; Bahnplanung; Geoinformationssystem; K{\"u}rzester-Weg-Problem; Multikriterielle Optimierung}, language = {de} } @phdthesis{Schmidt2024, author = {Schmidt, Johannes}, title = {The mission and flight planning problem : a physics-based MILP routing approach for an inhomogeneous fleet of unmanned aerial vehicles with collision-free trajectories}, doi = {10.26127/BTUOpen-6841}, url = {http://nbn-resolving.de/urn:nbn:de:kobv:co1-opus4-68415}, school = {BTU Cottbus - Senftenberg}, year = {2024}, abstract = {Today, drones are a helpful addition or even an efficient alternative in many areas due to their simple control and low operating costs compared to manned aircraft. Often, it is preferred that the UAV performs its mission autonomously. Thus, next to the operative control, the strategic planning of such missions plays an important role for their efficiency. Furthermore, it is also of interest for air traffic management to integrate UAVs into the airspace of manned aviation. At a strategic level, many use cases can be represented by a set of waypoints. Maybe not all of them can be visited within a given time horizon or only by drones with special hardware. Thus, before the start of a mission, each involved UAV must be assigned the waypoints to be processed and its flight trajectory must be planned to guarantee a safe and efficient process. These two sub-problems of the planning process influence each other and cannot be treated separately. In this paper, we address this problem by introducing the Mission and Flight Planning Problem (MFPP). Therein, the assignment of the UAVs to the given waypoints is combined with the computation of exact flight trajectories in a mixed-integer linear optimization problem (MILP). It is based on a team orienteering problem with time windows, in which the positions of all UAVs are calculated using discretized Newton's laws of motion. Concerning the flight dynamics, design-related parameters and mass, speed, and altitude dependencies of the performance data of each drone are included in the model. Each drone is controlled by radio and must not leave the range of its control station. There may be obstacles within the mission area. The UAVs must also maintain safety distances from each other to avoid collisions. In addition to the model, we discuss different types of valid inequalities. We present a new inter-sample avoidance approach based on decomposing the mission area into several sub-areas and their identification with binary vectors. The construction of an integer polyhedron containing these binary vectors is given and we investigate its structure. In addition, different possibilities for implementing the new constraints are discussed. For two special types of MFPP instances, we present adapted solution methods that exploit their respective structure, i.e., a sequential solution method and a column generation approach. The performance of the presented model is investigated in detailed computational studies and we discuss its essential properties in several examples.}, subject = {Mixed-integer linear programming; Trajectory optimization; Inter-sample avoidance; Unmanned aerial vehicles; Gemischt-ganzzahlige lineare Programmierung; Trajektorienoptimierung; Kollisionsvermeidung zwischen Zeitschritten; Unbemannte Luftfahrzeuge; Flugk{\"o}rper; Optimierungsproblem; Strategische Planung; Kollisionsschutz; Trajektorie }, language = {en} } @phdthesis{Gnegel2022, author = {Gnegel, Fabian}, title = {Refinement algorithms for time-dependent discrete optimization problems}, editor = {F{\"u}genschuh, Armin}, doi = {10.26127/BTUOpen-6127}, url = {http://nbn-resolving.de/urn:nbn:de:kobv:co1-opus4-61275}, school = {BTU Cottbus - Senftenberg}, year = {2022}, abstract = {One of the standard approaches for solving discrete optimization problems which include the aspect of time, such as the traveling salesman problem with time windows, is to derive a so-called time-indexed formulation. If the problem has an underlying structure that can be described by a graph, the time-indexed formulation is usually based on a different, extended graph, commonly referred to as the time-expanded graph. The time-expanded graph can often be derived in such a way that all time constraints are incorporated in its topology, and therefore algorithms for the corresponding time-independent variant become applicable. The downside of this approach is that the sets of vertices and arcs of the time-expanded graph are much larger than the ones of the original graph. In recent works, however, it has been shown that for many practical applications a partial graph expansion that might contain time-infeasible paths, often suffices to find a proven optimal solution. These approaches, instead, iteratively refine the original graph and solve a relaxation of the time-expanded formulation in each iteration. When the solution of the current relaxation allows for a feasible schedule, an optimal solution can be derived from it and the algorithm terminates. In this work, we first present new ideas that allow for the propagation of information about the optimal solution of a coarser graph to a more refined graph and show how these can be used in algorithms. More precisely, we present two general algorithms for solving Mixed Integer Linear Program formulations which we call iterative refinement and branch-and-refine. Iterative refinement basically is solving relaxations of the problem until a feasible solution to the original problem is found. Branch-and-refine is a kind of branch-and-bound algorithm that allows for the graph refinement to be carried out during the exploration of the branch-and-bound tree. For demonstrating the practical relevance of these algorithms, we not only study them in the context of academic examples but also apply them to two real-world problems. The first is a problem from the literature, where small passenger air-crafts have to be routed and scheduled to serve flight requests while fulfilling a variety of conditions on, for example, fuel consumption, weight, and detours. We show here that refinement algorithms can be used to improve the best known results from the literature. The second problem we consider is the task of optimally scheduling deliveries and charging times of delivery robots such that delays are minimized. In this case, we show that refinement algorithms perform better than a direct solution approach making use of state-of-the-art solvers.}, subject = {Discrete optimization; Mixed integer linear programming; Graph refinement; Branch and bound; Time-dependent airplane routing; Diskrete Optimierung; Gemischt-ganzzahlige lineare Programmierung; Verfeinerung von Graphen; Zeitabh{\"a}ngige Flugroutenplanung; Tourenplanung von E-Fahrzeugen; Ganzzahlige Optimierung; Tourenplanung; Travelling-salesman-Problem; Branch-and-Bound-Methode}, language = {en} } @phdthesis{Stieber2022, author = {Stieber, Anke}, title = {The multiple traveling salesperson problem with moving targets}, editor = {F{\"u}genschuh, Armin}, doi = {10.26127/BTUOpen-6110}, url = {http://nbn-resolving.de/urn:nbn:de:kobv:co1-opus4-61104}, school = {BTU Cottbus - Senftenberg}, year = {2022}, abstract = {Military installations and objects in out-of-area missions, e.g., an air base or a field camp, must be protected from incoming hostile rockets, artillery or mortar fire. Lasers as directed energy weapons are able to destroy those targets within seconds. Generally, the laser is assigned to a target, that applies the smallest movement of its direction unit to aim at it. The goal is to minimize the damage and thus, to destroy all incoming targets. We model the problem as a multiple traveling salesperson problem with moving targets, where the salespersons correspond to the lasers. The targets move over time on continuous trajectories. Additionally, each target is given a visibility time window. We investigate if exact methods are able to solve real-world instances in reasonable time. On that account, we address the problem from two sides, offline and online. One essential aspect studied in this work is to find an appropriate formulation to model the time requirements. We present five different modeling approaches, where the time aspect is handled in different ways: discrete, continuous, directly or via sub-problems. Our randomly generated test instances consider 6 to 20 targets and 1 to 6 salespersons. Computational experiments with linear and non-linear trajectories are performed. The best model can solve instances up to 10 targets within 3 seconds. For online experiments the two familiar strategies REPLAN and IGNORE are adapted to our problem. Another important aspect of this work is our contribution to competitive analysis, a method to evaluate the quality of online algorithms. Here, we restrict the problem considered so far to one salesperson and address the online moving targets traveling salesperson problem on the real line. We prove a lower bound for the competitive ratio regarding this problem. Then, we develop an online algorithm and present its competitive ratio with the corresponding proof. The competitive ratio depends on the speed ratio of salespersons and targets and outperforms a comparable online algorithm from the literature for certain speed ratios. The theoretical results obtained for the online moving target traveling salesperson problem on the real line are new in this research area.}, subject = {Multiple traveling salesperson problem; Moving targets; Modeling of time; Online algorithms; Competitive analysis; Multiples Handlungsreisendenproblem; Bewegliche Ziele; Modellierung von Zeit; Online-Algorithmen; Kompetitivit{\"a}tsanalyse; Competitive analysis; Travelling-salesman-Problem}, language = {en} }