TY - THES A1 - Beisegel, Jesse T1 - Convexity in graphs: vertex order characterisations and graph searching T1 - Konvexität in Graphen: lineare Knotenordnungen und Graphensuchen N2 - We study convexities designed to characterise some of the most fundamental classes of graphs. To this end, we present some known results on this topic in a slightly different form, so as to give a homogeneous representation of a very disparate field. Furthermore, we present some new results on the Caratheodory number of interval graphs and also give a more or less exhaustive account of everything that is known in this context on AT-free graphs, including new results on characterising linear vertex orders and the structure of the intervals of this class. We introduce the new class of bilateral AT-free graphs which is motivated by the linear order characterisation and the convexity used to describe AT-free graphs. We discuss their relation to other known classes and consider the complexity of recognition. Furthermore, as a consequence of notions from abstract convexity we present algorithmic results with regards to some natural subclasses of these. As an application of notion of an extreme vertex of a convex geometry, we discuss structural aspects of avoidable vertices in graphs, which form a generalisation of simplicial vertices. This includes a characterisation of avoidable vertices as simplicial vertices in some minimal triangulation of the graph and a new proof of the existence result. Furthermore, we discuss the algorithmic issues regarding the problem of efficient computation of avoidable vertices in a given graph. This is complemented by an algorithmic application of the concept of avoidable vertices to the maximum weight clique problem, by identifying a rather general class of graphs in which every avoidable vertex is bisimplicial. This leads to a polynomial-time algorithm for the maximum weight clique problem in this class of graphs. Implications of this approach for digraphs are also discussed. All of these results lead to a conjecture concerning the generalisation of avoidable vertices to avoidable paths and we prove this conjecture for paths of length less or equal to two. Finally, we analyse the properties of many different and widely used forms of graph search. Here, we discuss the problem of recognising whether a given vertex can be the last vertex visited by some fixed graph search. Moreover, we present some new aspects of the problem of deciding whether a given spanning tree of a graph is a graph search tree of a particular type of search. We generalise the concept of such trees to many well-known searches and give a broad analysis of the computational complexity of this problem. Both of these discussions are motivated by the use of graph searches in the context of computing properties of convexity. N2 - In dieser Arbeit betrachten wir Konvexitäten, die entworfen wurden, um einige der grundlegendsten Graphenklassen zu charakterisieren. Dazu präsentieren wir einige bekannte Resultate zu diesem Thema in einer abgeänderten Form, um eine homogene Darstellung eines diversen Felds zu bieten. Außerdem, geben wir neue Resultate über die Caratheodory Zahl von Intervallgraphen, sowie einen weitestgehend vollständigen Überblick über alle Ergebnisse bezüglich der charakterisierenden Konvexität von AT-freien Graphen, welcher auch neue Ergebnisse über charakterisierende Knotenordnungen und die Struktur der Intervalle dieser Klasse umfasst. Wir führen die neue Klasse der bilateral AT-freien Graphen ein, welche durch die charakterisierende Knotenordnung und Konvexität der AT-freien Graphen motiviert ist. Wir diskutieren das Verhältnis dieser Graphen zu anderen Unterklassen der AT-freien Graphen und untersuchen die Komplexität ihrer Erkennung. Außerdem geben wir einige algorithmische Ergebnisse zu Unterklassen von bilateral AT-freien Graphen, welche aus der Analyse ihrer Konvexität folgen. Als Anwendung des Begriffs eines Extremknoten einer konvexen Geometrie diskutieren wir einige strukturelle Aspekte von vermeidbaren Knoten, welche eine Verallgemeinerung der simplizialen Knoten darstellen. Dies beinhaltet eine Charakterisierung von vermeidbaren Knoten als simpliziale Knoten einer minimalen Triangulierung eines Graphen, sowie einen neuen Beweis über deren Existenz. Wir analysieren die algorithmischen Aspekte des Erkennungsproblems von vermeidbaren Knoten eines gegebenen Graphen. Diese Ergebnisse verwenden wir, um das Konzept eines vermeidbaren Knotens zur Berechnung von Cliquen maximalen Gewichts algorithmisch auszunutzen, indem eine Klasse ermittelt wird, für die jeder vermeidbare Knoten bisimplizial ist. Dies führt zu einem Polynomialzeitalgorithmus zur Berechnung einer Clique maximalen Gewichts auf dieser Klasse. Die Konsequenzen dieses Ansatzes werden auch für gerichtete Graphen analysiert. Alle diese Ergebnisse geben den Anlass zu einer Vermutung, die die Existenz vermeidbarer Knoten zu der Existenz vermeidbarer Pfade ausweitet; diese Vermutung wird für Pfade der Länge 1 und 2 bewiesen. Schließlich betrachten wir die Eigenschaften einiger unterschiedlicher und häufig genutzter Graphensuchen. Wir diskutieren das Problem der Erkennung von Endknoten dieser Suchen. Außerdem präsentieren wir neue Ergebnisse über die Erkennung von Suchbäumen verschiedener Graphensuchen. Wir verallgemeinern das Konzept solcher Suchbäume, um weitere komplexere Suchstrategien abzufangen, und betrachten die Komplexität der Erkennung solcher Bäume. Diese Untersuchungen sind motiviert durch die häufige Verwendung von Graphensuchen, um Eigenschaften von Konvexitäten algorithmisch zu ermitteln. KW - Graph convexity KW - Convex geometry KW - Graph searching KW - Vertex order characterisation KW - Asteroidal triples KW - Asteroidale Tripel KW - Lineare Knotenordnung KW - Graphensuche KW - Konvexe Geometrie KW - Konvexität KW - Graph KW - Konvexität KW - Konvexe Geometrie Y1 - 2020 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:co1-opus4-51452 ER - TY - THES A1 - Schmidt, Johannes T1 - The mission and flight planning problem : a physics-based MILP routing approach for an inhomogeneous fleet of unmanned aerial vehicles with collision-free trajectories T1 - Das Missions- und Flugplanungsproblem : Ein physik-basierter, gemischt-ganzzahlig linearer Routenplanungsansatz für eine inhomogene Flotte unbemannter Luftfahrzeuge mit kollisionsfreien Trajektorien N2 - 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. N2 - Heute sind Drohnen, aufgrund ihrer einfachen Steuerung und geringen Einsatzkosten im Vergleich zu bemannten Luftfahrzeugen, eine hilfreiche Ergänzung oder sogar eine effiziente Alternative in vielen Bereichen. Oft soll der Einsatz der Drohne dabei autonom erfolgen. Deshalb spielt neben dem operativen Betrieb auch die strategische Planung solcher Missionen für ihre effiziente Ausführung eine wesentliche Rolle. Weiterhin ist sie auch für die Flugsicherung von großem Interesse, um UAVs sicher in den Luftraum der bemannten Luftfahrt zu integrieren. Auf einer strategischen Ebene lassen sich viele Anwendungsfälle mit Hilfe einer Menge von Wegpunkten darstellen. Von diesen können eventuell nicht alle innerhalb eines gegebenen Zeithorizonts oder nur von Drohnen mit spezieller Ausrüstung besucht werden. Somit müssen vor dem Start einer Mission jeder beteiligten Drohne die von ihr zu bearbeitenden Wegpunkte zugewiesen und ihre Flugtrajektorie geplant werden, um einen sicheren und effizienten Ablauf zu garantieren. Diese beiden Teilprobleme des Planungsprozesses beeinflussen sich gegenseitig und können nicht losgelöst voneinander behandelt werden. In dieser Arbeit begegnen wir diesem Problem, indem wir das Missions- und Flugplanungsproblem (MFPP) einführen. Darin wird die Zuordnung der UAVs zu den gegebenen Wegpunkten mit der Berechnung exakter Flugtrajektorien in einem linearen, gemischt-ganzzahligen Optimierungsproblem kombiniert. Die Grundlage dafür ist ein "Team Orienteering"- Problem mit Zeitfenstern, in welchem die Positionen aller UAVs mit Hilfe der diskretisierten Newton'schen Bewegungsgesetze berechnet werden. Bezüglich der Flugdynamik werden bauartbedingte Parameter und Masse-, Geschwindigkeits-, sowie Höhenabhängigkeiten der Leistungskennzahlen jeder Drohne in das Modell einbezogen. Jede Drohne wird per Funk gesteuert und kann sich nicht außerhalb der Reichweite ihrer Kontrollstation bewegen. Innerhalb des Missionsgebietes können sich Hindernisse befinden. Außerdem müssen die UAVs untereinander Sicherheitsabstände zur Kollisionsvermeidung einhalten. Zusätzlich zum Modell diskutieren wir auch verschiedene Arten von gültigen Ungleichungen. Wir präsentieren einen neuen Modellierungsansatz zur Kollisionsvermeidung zwischen Zeitschritten, basierend auf der Zerlegung des Missionsgebietes in mehrere Teilgebiete und deren Identifikation mit Binärvektoren. Die Konstruktion eines ganzzahligen Polyeders, welches diese Binärvektoren enthält, wird angegeben und wir untersuchen seine Struktur. Zudem werden verschiedene Möglichkeiten zur Implementierung der neuen Nebenbedingungen diskutiert. Für zwei spezielle Typen von MFPP-Instanzen präsentieren wir angepasste Lösungsmethoden, die sich deren Struktur zu Nutze machen, einen sequenziellen Lösungsansatz und Spaltengenerierung. Die Performanz des vorgestellten Modells wird in ausführlichen Berechnungsstudien untersucht und wir diskutieren an verschiedenen Beispielen seine wesentlichen Eigenschaften. T3 - Cottbus Mathematical Preprints - 30, 2024 KW - Mixed-integer linear programming KW - Trajectory optimization KW - Inter-sample avoidance KW - Unmanned aerial vehicles KW - Gemischt-ganzzahlige lineare Programmierung KW - Trajektorienoptimierung KW - Kollisionsvermeidung zwischen Zeitschritten KW - Unbemannte Luftfahrzeuge KW - Flugkörper KW - Optimierungsproblem KW - Strategische Planung KW - Kollisionsschutz KW - Trajektorie Y1 - 2024 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:co1-opus4-68415 ER - TY - THES A1 - Scheffler, Robert T1 - Ready to order? : on vertex and edge orderings of graphs T1 - Ready to order? : über Knoten- und Kantenordnungen von Graphen N2 - Vertex and edge orderings of graphs are commonly used in algorithmic graph theory. Such orderings can encode structural properties of graphs in a condensed way and, thus, they can be used to process a graph efficiently. A common approach to find particular vertex orderings are graph searches. Here, we study the complexity of deciding whether vertex orderings with special properties can be found by particular graph searches. The properties of these orderings concern their end-vertices, their search trees or constraints encoded by partial orders. Many graph classes can be characterized via special vertex orderings. We introduce another example, the semi-proper interval graphs, generalizations of connected proper interval graphs that are characterized via special variants of perfect elimination orderings. We study the structure of these graphs, present a linear-time recognition algorithm and show that they share some strong properties on Hamiltonian paths and cycles with proper interval graphs. We also generalize the notion of graph classes to the case of edge-weighted graphs. A weighted graph is a member of such a weighted class if subgraphs containing edges of particular weights are members of the respective unweighted graph class. We present conditions on an unweighted graph class that ensure a linear-time recognition algorithm for its corresponding weighted graph class. This conditions make use of a novel edge monotonicity and of particular edge orderings. We apply this result to three well-known graph classes, namely split graphs, threshold graphs, and chain graphs. Finally, we consider dynamic algorithms on threshold and chain graphs. These algorithms update certain properties of a graph after small modifications are applied to its vertex or edge set. We present certifying dynamic recognition algorithms of these classes, i.e., if the graph leaves the class after the modification, we can prove this by providing a forbidden induced subgraph of bounded size. Building on these results, we extend the notion of dynamic recognition algorithms to whole sets of edges and vertices. Furthermore, we present dynamic algorithms for the Hamiltonian path and cycle problems. N2 - Knoten- und Kantenordnungen von Graphen werden häufig in der algorithmischen Graphentheorie verwendet. Solche Ordnungen können Eigenschaften von Graphen in komprimierter Form kodieren und können damit zur effizienten Verarbeitung eines Graphen verwendet werden. Ein gängiger Ansatz, um bestimmte Knotenordnungen zu finden, sind Graphensuchen. Wir untersuchen hier wie schwer es ist zu entscheiden, ob Knotenordnungen mit speziellen Eigenschaften durch bestimmte Graphensuchen gefunden werden können. Die Eigenschaften dieser Ordnungen betreffen ihre Endknoten, ihre Suchbäume oder Einschränkungen, die durch partielle Ordnungen gegeben sind. Viele Graphenklassen lassen sich durch spezielle Knotenordnungen charakterisieren. Wir stellen ein weiteres Beispiel vor, die Semi-Proper-Intervallgraphen, Verallgemeinerungen von zusammenhängenden Proper-Intervallgraphen, die durch spezielle Varianten perfekter Eliminationsordnungen charakterisiert sind. Wir untersuchen die Struktur dieser Graphen, stellen einen Linearzeit-Erkennungsalgorithmus vor und zeigen, dass sie einige starke Eigenschaften in Bezug auf Hamiltonpfade und -kreise mit Proper-Intervallgraphen teilen. Wir verallgemeinern auch den Begriff der Graphenklassen auf den Fall von Graphen mit gewichteten Kanten. Ein gewichteter Graph ist Element einer solchen gewichteten Klasse, wenn Untergraphen mit Kanten bestimmter Gewichte Elemente der jeweiligen ungewichteten Graphenklasse sind. Wir präsentieren Bedingungen für eine ungewichtete Graphenklasse, die einen Erkennungsalgorithmus mit linearer Laufzeit für die entsprechende gewichtete Graphenklasse sicherstellen. Diese Bedingungen nutzen eine neuartige Monotonieeigenschaft und spezielle Kantenordnungen. Diese Ergebnisse wenden wir auf drei bekannte Graphenklassen an: Split-Graphen, Threshold-Graphen und Chain-Graphen. Am Ende betrachten wir dynamische Algorithmen für Threshold- und Chain-Graphen. Diese Algorithmen aktualisieren bestimmte Eigenschaften eines Graphen, nachdem kleinere Änderungen an seiner Knoten- oder Kantenmenge vorgenommen wurden. Wir stellen zertifizierende dynamische Erkennungsalgorithmen für diese Klassen vor, das heißt falls der Graph die Klasse nach der Modifikation verlässt, können wir dies mit einem verbotenen induzierten Untergraphen von beschränkter Größe beweisen. Aufbauend auf diesen Ergebnissen erweitern wir den Begriff der dynamischen Erkennungsalgorithmen auf ganze Mengen von Kanten und Knoten. Außerdem stellen wir dynamische Algorithmen für das Hamiltonpfad- und das Hamiltonkreis-Problem vor. KW - Graph search KW - Graphensuche KW - Dynamic algorithm KW - Dynamischer Algorithmus KW - Edge ordering KW - Kantenordnung KW - Vertex ordering KW - Knotenordnung KW - Weighted graph KW - Gewichteter Graph KW - Graphentheorie KW - Graphenklasse Y1 - 2023 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:co1-opus4-63019 ER - TY - THES A1 - Strehler, Martin T1 - Signalized flows - optimizing traffic signals and guideposts and related network flow problems T1 - Signalisierte Netzwerkflüsse - Optimierung von Lichtsignalanlagen und Vorwegweisern und daraus resultierende Netzwerkflussprobleme N2 - Guideposts and traffic signals are important devices for controlling inner-city traffic and their optimized operation is essential for efficient traffic flow without congestion. In this thesis, we develop a mathematical model for guideposts and traffic signals in the context of network flow theory. Guideposts lead to confluent flows where each node in the network may have at most one outgoing flow-carrying arc. The complexity of finding maximum confluent flows is studied and several polynomial time algorithms for special graph classes are developed. For traffic signal optimization, a cyclically time-expanded model is suggested which provides the possibility of the simultaneous optimization of offsets and traffic assignment. Thus, the influence of offsets on travel times can be accounted directly. The potential of the presented approach is demonstrated by simulation of real-world instances. N2 - Vorwegweiser und Lichtsignalanlagen sind wichtige Elemente zur Steuerung innerstädtischen Verkehrs und ihre optimale Nutzung ist von entscheidender Bedeutung für einen staufreien Verkehrsfluss. In dieser Arbeit werden Vorwegweiser und Lichtsignalanlagen mittels der Netzwerkflusstheorie mathematisch modelliert. Vorwegweiser führen dabei zu konfluenten Flüssen, bei denen Fluss einen Knoten des Netzwerks nur gebündelt auf einer einzigen Kante verlassen darf. Diese konfluenten Flüsse werden hinsichtlich ihrer Komplexität untersucht und es werden Polynomialzeitalgorithmen für das Finden maximaler Flüsse auf ausgewählten Graphenklassen vorgestellt. Für die Versatzzeitoptimierung von Lichtsignalanlagen wird ein zyklisch zeitexpandiertes Modell entwickelt, das die gleichzeitige Optimierung der Verkehrsumlegung ermöglicht. So kann der Einfluss geänderter Versatzzeiten auf die Fahrzeiten direkt berücksichtigt werden. Die Leistungsfähigkeit dieses Ansatzes wird mit Hilfe von Simulationen realistischer Szenarien nachgewiesen. KW - Stadtverkehr KW - Verkehrsablauf KW - Netzwerkfluss KW - Optimierung KW - Netzwerkfluss KW - Verkehrsfluss KW - Konfluenter Fluss KW - Lichtsignalanlagenoptimierung KW - Optimierung von Wegweisern KW - Network flow KW - Traffic flow KW - Confluent flow KW - Traffic signal optimization KW - Flow with path restrictions Y1 - 2011 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:co1-opus-23637 ER - TY - THES A1 - Reich, Alexander T1 - Cycle bases of graphs and spanning trees with many leaves - complexity results on planar and regular graphs T1 - Kreisbasen von Graphen und spannende Bäume mit vielen Blättern - Komplexitätsergebnisse zu planaren und regulären Graphen N2 - A cycle basis of a graph is a basis of its cycle space, the vector space which is spanned by the cycles of the graph. Practical applications for cycle bases are for example the optimization of periodic timetables, electrical engineering, and chemistry. Often, cycle bases belong to the input of algorithms concerning these fields. In these cases, the running time of the algorithm can depend on the size of the given cycle basis. In this thesis, we study the complexity of finding minimum cycle bases of several types on different graph classes. As a main result, we show that the problem of minimizing strictly fundamental cycle bases on planar graphs is NP-complete. We also give a similarly structured proof for problem of finding a maximum leaf spanning tree on the very restricted class of cubic planar graphs. Additionally, we show that this problem is APX-complete on k-regular graphs for odd k greater than 3. Furthermore, we classify types of robust cycle bases and study their relationship to fundamental cycle bases. N2 - Eine Kreisbasis eines Graphen ist eine Basis des Zyklenraumes des Graphen, also des Vektorraumes, der von den Kreisen des Graphen aufgespannt wird. Praktische Anwendungsgebiete von Kreisbasen finden sich zum Beispiel bei der Optimierung von Taktfahrplänen, in der Elektrotechnik und der Chemie. Oft gehören Kreisbasen zur Eingabe von Algorithmen aus diesen Gebieten. In diesen Fällen kann die Laufzeit der Algorithmen von der Größe der eingegebenen Kreisbasis abhängen. In dieser Arbeit untersuchen wir die Komplexität, minimale Kreisbasen unterschiedlicher Typen auf verschiedenen Graphenklassen zu finden. Als ein Hauptergebnis zeigen wir, dass das Problem minimale streng fundamentale Kreisbasen von planaren Graphen zu finden NP-vollständig ist. Wir geben einen ähnlich strukturierten Beweis für das Problem, auf der sehr eingeschränkten Graphenklasse der kubischen planaren Graphen einen spannenden Baum mit der maximalen Anzahl an Blättern zu finden. Zusätzlich zeigen wir, dass dieses Problem auf k-regulären Graphen für ungerade k größer als 3 APX-vollständig ist. Ein weiteres Thema der Arbeit ist die Klassifizierung von Typen robuster Kreisbasen und ihre Beziehung zu fundamentalen Kreisbasen. KW - Planarer Graph KW - Zyklenraum KW - NP-vollständiges Problem KW - Spannbäume mit vielen Blättern KW - Minimale streng fundamentale Kreisbasen KW - NP-Vollständigkeit KW - APX-Vollständigkeit KW - Planare Graphen KW - Maximum leaf spanning tree KW - Minimum strictly fundamental cycle basis KW - NP-completeness KW - APX-completeness KW - Planar graphs Y1 - 2014 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:co1-opus-30692 ER - TY - THES A1 - Gnegel, Fabian ED - Fügenschuh, Armin T1 - Refinement algorithms for time-dependent discrete optimization problems T1 - Verfeinerungsalgorithmen für zeitabhängige diskrete Optimierungsprobleme N2 - 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. N2 - Das Herleiten einer so genannten zeitindizierten Formulierung ist einer der Standardansätze zum Lösen diskreter Optimierungsprobleme, die den Aspekt der Zeit einbeziehen, wie z. B. das Problem des Handlungsreisenden mit Zeitfenstern. Liegt dem Problem eine Struktur zugrunde, die durch einen Graphen beschrieben werden kann, so basiert die zeitindizierte Formulierung in der Regel auf einem anderen, erweiterten Graphen, der gemeinhin als zeitexpandierter Graph bezeichnet wird. Der zeitexpandierte Graph kann oft so konstruiert werden, dass alle zeitlichen Beschränkungen bereits in seine Topologie einfließen und Algorithmen für die entsprechende zeitunabhängige Variante anwendbar werden. Der Nachteil dieses Ansatzes ist, dass die Mengen der Knoten und Bögen des zeitexpandierten Graphen viel größer sind als die des ursprünglichen Graphen. In neueren Arbeiten wurde jedoch gezeigt, dass für viele praktische Anwendungen eine partielle Expansion des Graphen, die möglicherweise nicht alle zeitlich unzulässigen Pfade verbietet, oft ausreicht, um eine nachweislich optimale Lösung zu finden. Bei diesem Ansatz wird stattdessen der zeitexpandierte Graph iterativ sukzessive aufgebaut und verfeinert und in jedem Schritt wird eine Relaxierung der zeitexpandierten Formulierung gelöst. Wenn die Lösung der aktuellen Relaxierung einen realisierbaren Zeitplan zulässt, kann daraus eine optimale Lösung abgeleitet werden und der Algorithmus wird beendet. In dieser Arbeit stellen wir zunächst neue Ideen vor, die es ermöglichen, Informationen über die optimale Lösung eines gröberen Graphen auf einen verfeinerten Graphen zu übertragen, und zeigen, wie diese in Algorithmen verwendet werden können. Genauer gesagt stellen wir zwei allgemeine Algorithmen zur Lösung von gemischt-ganzzahligen linearen Programmen vor, die wir als `iterative refinement' und `branch-and-refine' bezeichnen. Bei der iterativen Verfeinerung geht es im Wesentlichen darum, Relaxierungen des Problems zu lösen, bis eine machbare Lösung für das ursprüngliche Problem gefunden wird. Branch-and-refine ist eine Art Branch-and-Bound-Algorithmus, bei dem die Verfeinerung des Graphen während der Erkundung des Branch-and-Bound-Suchbaums durchgeführt wird. Um die praktische Relevanz dieser Algorithmen zu demonstrieren, untersuchen wir ihn nicht nur im Zusammenhang mit akademischen Beispielen, sondern wenden ihn auch auf zwei praktisch motivierte Fragestellungen an. Das erste ist ein Problem aus der Literatur, bei dem die Routen und Zeitpläne kleiner Passagierflugzeuge so geplant werden müssen, dass Fluganfragen von Touristengruppen zu bedienen und dabei eine Vielzahl von Bedingungen zu erfüllen. Die Bedingungen betreffen unter anderem Treibstoffverbrauch, Gewicht und Umwege. Wir zeigen hier, dass Verfeinerungsalgorithmen verwendet werden können, um die besten Ergebnisse aus der Literatur zu verbessern. Das zweite Problem, das wir betrachten, ist die Aufgabe, Lieferungen und Ladezeiten von elektrischen Lieferrobotern optimal zu planen, so dass Verzögerungen minimiert werden. In diesem Fall zeigen wir, dass Verfeinerungsalgorithmen besser abschneiden als ein direkter Lösungsansatz, bei dem ein allgemeiner Löser für gemischt-ganzzahlige Probleme eingesetzt wird. T3 - Cottbus Mathematical Preprints - 27, 2022 KW - Discrete optimization KW - Mixed integer linear programming KW - Graph refinement KW - Branch and bound KW - Time-dependent airplane routing KW - Diskrete Optimierung KW - Gemischt-ganzzahlige lineare Programmierung KW - Verfeinerung von Graphen KW - Zeitabhängige Flugroutenplanung KW - Tourenplanung von E-Fahrzeugen KW - Ganzzahlige Optimierung KW - Tourenplanung KW - Travelling-salesman-Problem KW - Branch-and-Bound-Methode Y1 - 2022 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:co1-opus4-61275 ER - TY - THES A1 - Stieber, Anke ED - Fügenschuh, Armin T1 - The multiple traveling salesperson problem with moving targets T1 - Das multiple Handlungsreisendenproblem mit beweglichen Zielen N2 - 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. N2 - Bei militärischen Operationen und Auslandseinsätzen ist es notwendig, die verwendete Infrastruktur sowie militärische Objekte, wie beispielsweise Militärflugplätze oder Feldlager vor feindlichem Beschuss zu schützen. Laserwaffen können diese feindlichen Geschosse (Ziele) in Sekundenschnelle neutralisieren. Zur Abwehr eines Zieles wird derjenige Laser ausgewählt, der die Zerstörung des Zieles mit geringster Bewegung der Strahlführungseinheit ermöglicht. Es sollen möglichst alle Ziele eliminiert werden. In der vorliegenden Arbeit wird diese Anwendung als multiples Handlungsreisendenproblem mit beweglichen Zielen beschrieben, wobei die Laser als Verfolger fungieren, welche die Ziele in bestimmten Zeitfenstern besuchen müssen. Die Ziele bewegen sich kontinuierlich über der Zeit auf sogenannten Trajektorien (Flugbahnen). Der Fokus der Arbeit liegt darauf, zu untersuchen, ob exakte Verfahren in der Lage sind, reale Instanzen adäquat schnell zu lösen. Dazu betrachten wir das Problem zuerst offline und anschließend online. Ein zentraler Aspekt dieser Arbeit ist es, den Zeitaspekt geeignet zu modellieren. In diesem Zusammenhang werden fünf verschiedene Modelle vorgestellt, die zum einen auf einer diskreten oder kontinuierlichen Zeitrepräsentation basieren und zum anderen die Zeitzulässigkeit direkt oder über Unterprogramme realisieren. Die zufällig generierten Testinstanzen berücksichtigen 6 bis 20 Ziele und 1 bis 6 Verfolger. Das beste Modell löst offline-Instanzen mit bis zu 10 Zielen im Schnitt innerhalb von 3 Sekunden. Die Tests berücksichtigen sowohl lineare als auch nicht-lineare Trajektorien. Für die Online-Experimente werden bekannte Update-Strategien (REPLAN, IGNORE) adaptiert. Ein weiterer wichtiger Teil dieser Arbeit ist der Beitrag zur Kompetitivitätsanalyse, einer Methode zur Bewertung von Online-Algorithmen. Dazu beschränken wir uns auf einen Verfolger und betrachten das Online-Traveling-Salesperson-Problem mit sich bewegenden Zielen auf der reellen Zahlengeraden. Zu diesem Problem wird eine untere Schranke für den Kompetitivitätsfaktor angegeben. Außerdem präsentiert diese Arbeit einen Online-Algorithmus und den Beweis seines Kompetitivitätsfaktors. Dieser ist abhängig vom Geschwindigkeitsverhältnis von Verfolger und Zielen und für bestimmte Geschwindigkeitsverhältnisse besser als der eines vergleichbaren Online-Algorithmus aus der Literatur. Die erzielten theoretischen Resultate zum Online-Handlungsreisendenproblem mit beweglichen Zielen auf der reellen Zahlengeraden stellen neue Ergebnisse in diesem Bereich dar. T3 - Cottbus Mathematical Preprints - 26, 2022 KW - Multiple traveling salesperson problem KW - Moving targets KW - Modeling of time KW - Online algorithms KW - Competitive analysis KW - Multiples Handlungsreisendenproblem KW - Bewegliche Ziele KW - Modellierung von Zeit KW - Online-Algorithmen KW - Kompetitivitätsanalyse KW - Competitive analysis KW - Travelling-salesman-Problem Y1 - 2022 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:co1-opus4-61104 ER - TY - THES A1 - Flister, Tobias ED - Fügenschuh, Armin T1 - Eine Heuristik zur Lösung ganzzahliger Programme mit quadratischen Nebenbedingungen T1 - A heuristic for the solution of integer programs with quadratic constraints N2 - Die Frage nach dem Lösen von ganzzahligen Programmen mit quadratischen Nebenbedingungen spielt beim Aufbau multistatischer Sonar-Netze eine Rolle. Hierbei werden Schall-Sender und -Empfänger in einem Ozeanabschnitt so platziert, dass möglichst jeder Bereich durch mindestens ein Sender-Empfänger-Paar überwacht werden kann. Diskretisiert man den Abschnitt räumlich, so kann die Frage nach der Platzierung durch binäre Entscheidungsvariablen beschrieben werden. Da es auf die paarweise Platzierung ankommt, werden in den Modellen die Binärvariablen multipliziert, was einem logischen „Und“ entspricht. Um die Modelle halbwegs schnell numerisch zu lösen, wurden in der Literatur zahlreiche Linearisierungstechniken entwickelt und erprobt. Trotz allem Fortschritt ist man weit davon entfernt, Instanzen mit deutlich mehr als 100 Diskretisierungspunkten in annehmbarer Zeit zur Optimalität zu lösen. In dieser Bachelorarbeit werden heuristische Lösungsverfahren entwickelt, welche in der Lage sind, innerhalb kürzester Zeit gute (aber nicht beweisbar optimale) Lösungen zu liefern. Ausgangspunkt war die Grundidee, Sender und Empfänger abwechselnd zu optimieren, bis keine weitere Verbesserung mehr eintritt. Numerische Ergebnisse werden anhand von Testinstanzen präsentiert und mit einem exakten Ansatz verglichen. N2 - The question of solving integer programs with quadratic constraints plays a role when setting up multistatic sonar networks. Sound transmitters and receivers are placed in an ocean section in such a way that, if possible, every area can be monitored by at least one transmitter-receiver pair. If the section is discretized spatially, the question of placement can be described by binary decision variables. Since it depends on the placement in pairs, the binary variables are multiplied in the models, which corresponds to a logical "And". In order to numerically solve the models reasonably quickly, numerous linearization techniques have been developed and tested in the literature. Despite all the progress, one is far from solving instances with significantly more than 100 discretization points in a reasonable time to optimality. In this bachelor thesis, heuristic solution methods are developed, which are able to deliver good (but not provable optimal) solutions within a very short time. The starting point was the basic idea of alternately optimizing the transmitter and receiver until there was no further improvement. Numerical results are presented using test instances and compared with an exact approach. T3 - Cottbus Mathematical Preprints - 19, 2021 KW - Heuristiken KW - Ganzzahlige Programmierung KW - Quadratische Nebenbedingungen KW - Multistatisches Sonar KW - Netzplanung KW - Heuristics KW - Integer programming KW - Quadratic constraints KW - Multi-static sonar KW - Network planning KW - Ganzzahlige Optimierung KW - Heuristik KW - Netzplanung Y1 - 2021 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:co1-opus4-56175 ER -