TY - RPRT A1 - Schmidt, Johannes A1 - Fügenschuh, Armin T1 - Inter-sample avoidance in trajectory planning via an integer-polytope formulation for mixed-integer optimization T1 - Vermeidung von Kollisionen zwischen diskreten Zeitpunkten in der Trajektorienplanung mittels eines ganzzahligen Polytops für gemischt-ganzzahlige Optimierungsprobleme N2 - Autonomous vehicles such as drones or mobile robots must plan trajectories that avoid static obstacles. Their dynamics are captured by Newton’s laws and discretized numerically, so the vehicle’s position is tracked only at finitely many sample points. The resulting information gap allows a path to cut through an obstacle while still appearing feasible at all samples, a phenomenon called corner cutting. Finer time grids mitigate but never eliminate this artefact and increase computation time. We propose a new inter-sample avoidance scheme for polyhedral obstacles. The facet-defining half-spaces partition the three-dimensional mission space into sub-domains that we encode with binary sign vectors. Feasible one-step moves correspond to a specific subset of these vectors; we (i) enumerate that set exhaustively and (ii) give an integer-polytope formulation that enforces it without additional state variables or extra time steps. For planar motion with a single triangular no-fly zone we prove that the formulation is tight-the polytope equals the convex hull of its 0/1 points. The method is compared qualitatively with existing inter-sample avoidance techniques and its limitations are discussed. Computational experiments with a mixed-integer linear programming model for UAV mission planning, solved by Gurobi, demonstrate that the new formulation achieves realistic trajectories at competitive, or lower, solution times. N2 - Autonome Fahrzeuge wie Drohnen oder mobile Roboter müssen Routen planen, die statische Hindernisse umgehen. Ihre Dynamik wird durch die Newtonschen Gesetze erfasst und numerisch diskretisiert, sodass die Position des Fahrzeugs nur an einer endlichen Anzahl von Zeitpunkten verfolgt wird. Die daraus resultierende Informationslücke ermöglicht es, dass eine Route ein Hindernis durchschneidet und dennoch zu allen Zeitpunkten als machbar erscheint – ein Phänomen, das als „Corner Cutting“ bezeichnet wird. Feinere Zeitraster mildern dieses Artefakt, können es jedoch nie vollständig beseitigen und erhöhen zudem die Rechenzeit. Wir schlagen ein neues Schema zur Vermeidung von Hindernissen zwischen den Zeitpunkten für polyedrische Hindernisse vor. Die facettendefinierenden Halbräume unterteilen den dreidimensionalen Missionsraum in Teilgebiete, die wir mit binären Vorzeichenvektoren kodieren. Machbare Ein-Schritt-Bewegungen entsprechen einer bestimmten Teilmenge dieser Vektoren; wir (i) zählen diese Menge vollständig auf und (ii) geben eine ganzzahlige Polytopformulierung an, die sie ohne zusätzliche Zustandsvariablen oder zusätzliche Zeitschritte sicherstellt. Für planare Bewegungen mit einer einzigen dreieckigen Flugverbotszone beweisen wir, dass die Formulierung effizient ist – das Polytop entspricht der konvexen Hülle seiner 0/1-Punkte. Die Methode wird qualitativ mit bestehenden Techniken zur Vermeidung von Hindernissen zwischen den Zeitpunkten verglichen und ihre Grenzen werden diskutiert. Rechenexperimente mit einem gemischt-ganzzahligen linearen Optimierungsmodell für die Missionsplanung von UAVs, gelöst von Gurobi, zeigen, dass die neue Formulierung realistische Routen bei konkurrenzfähigen oder niedrigeren Rechenzeiten erzielt. T3 - Cottbus Mathematical Preprints - 34, 2025 KW - Mixed-integer optimization KW - Inter-sample avoidance KW - Trajectory planning KW - Convex hull KW - Unmanned aerial vehicles KW - Gemischt-ganzzahlige Optimierung KW - Trajektorienplanung KW - Konvexe Hülle KW - Unbemannte Luftfahrzeuge KW - Drohne (Flugkörper) KW - Autonomes System KW - Bahnplanung KW - Gemischt-ganzzahlige Optimierung KW - Konvexe Hülle Y1 - 2025 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:co1-opus4-71697 ER - TY - RPRT A1 - Schmidt, Johannes A1 - Fügenschuh, Armin A1 - Böschow, Moritz M. T1 - Sports league scheduling with minitournaments T1 - Planung von Sportligen mit Miniturnieren N2 - In amateur or youth sports leagues, the teams play all matches during their leisure time. Thus, a schedule with a smaller number of game days is preferred and the teams are willing to partly renounce on the fairness for this by playing minitournaments instead of single matches. In this format, multiple teams meet at one of them and play against each other, reducing the number of necessary game days and required referees at the cost of unevenly distributed home field advantages. The travel times of all teams now depend on their assignment to the respective minitournaments and the choice of the home team. We present a binary linear optimization model to schedule a sports league as a double Round Robin tournament with minitournaments and most evenly distributed home field advantages, yielding a feasible league schedule with minimal total traveling distances for all teams. After adjusting orbital shrinking to break the occurring symmetries in the possible assignments, we discuss the computational efficiency and evaluate an existing schedule for the "Basketball Senioren Landesliga Brandenburg" amateur basketball league in Germany. N2 - In Amateur- oder Jugendsportligen tragen die Mannschaften alle Spiele in ihrer Freizeit aus. Daher wird ein Spielplan mit einer geringeren Anzahl von Spieltagen bevorzugt, und die Mannschaften sind bereit, dafür teilweise auf die Fairness zu verzichten, indem sie Miniturniere anstelle von Einzelspielen spielen. Bei diesem Format treffen sich mehrere Mannschaften an einem Spieltag und spielen gegeneinander, wodurch die Anzahl der notwendigen Spieltage und der benötigten Schiedsrichter reduziert wird, allerdings auf Kosten eines ungleich verteilten Heimvorteils. Die Reisezeiten aller Mannschaften hängen nun von ihrer Zuordnung zu den jeweiligen Miniturnieren und der Wahl der Heimmannschaft ab. Wir stellen ein binäres lineares Optimierungsmodell vor, um eine Sportliga als doppeltes Round-Robin-Turnier mit Miniturnieren und möglichst gleichmäßig verteilten Heimvorteilen zu planen. Das Ziel ist ein zulässiger Ligaplan mit minimalen Gesamtreisezeiten für alle Mannschaften. Nach der Anpassung der "orbital shrinking"-Methode, um die auftretenden Symmetrien in den möglichen Zuordnungen zu brechen, diskutieren wir die rechnerische Effizienz und evaluieren einen bestehenden Spielplan für die Basketball Senioren Landesliga Brandenburg in Deutschland. T3 - Cottbus Mathematical Preprints - 33, 2025 KW - Discrete optimization KW - Linear optimization KW - Orbital shrinking KW - Sport scheduling KW - Diskrete Optimierung KW - Lineare Optimierung KW - Sportligenplanung KW - Lineare Optimierung KW - Diskrete Optimierung KW - Wettkampfklasse KW - Amateursport KW - Jugendsport KW - Spielplan Y1 - 2025 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:co1-opus4-70293 ER - TY - RPRT A1 - Zell, Sascha A1 - Fügenschuh, Armin T1 - Optimizing autonomous unmanned aircraft system deployment locations for enhanced wildfire detection and monitoring T1 - Standortoptimierung autonomer unbemannter Flugsysteme zur fortgeschrittenen Erkennung und Beobachtung von Waldbränden N2 - The increase in the frequency and severity of wildfires as a symptom of climate change requires innovative methods of wildfire fighting. For this reason, we propose a framework for an autonomous Unmanned Aircraft System (UAS), consisting of a fleet of Micro Air Vehicles (MAVs) stored in purpose-built hangars. The intention is to deploy the UAS as the first responder to an alarm and have the sensor-equipped MAVs monitor the target area even before other standard firefighting vehicles have arrived. The focus of this paper is primarily on the development and application of a location-allocation optimization Mixed-Integer Linear Programming (MILP) model that selects different MAV and hangar types and locates them, with the objective of approaching the target area as quickly as possible while guaranteeing a certain monitoring time at the scene. The model is applied to a large, sparsely populated, rural operational area, around a third of which consists of forest in the South of Brandenburg, Germany. The spatial demand is measured through an easily reproducible and transferable open data approach. Finally, several instances with different fixed numbers of hangars and MAVs to be set up are solved by the commercial state-of-the-art solver CPLEX and analyzed for their computation time. N2 - Die Zunahme der Häufigkeit und Schwere von Waldbränden als Symptom des Klimawandels erfordert innovative Methoden der Waldbrandbekämpfung. Für diesen Zweck nutzen wir ein autonomes unbemanntes Luftfahrtsystem (Unmanned Aricraft System - UAS), das aus einer Flotte von Drohnen besteht, die in eigens dafür errichteten Hangars gelagert werden. Ziel ist, das UAS als Erstreaktion bei einem Alarm einzusetzen und die mit Sensoren ausgestatteten Drohnen das Zielgebiet beobachten zu lassen, noch bevor die ersten Einsatzkräfte vor Ort eintreffen. Der Fokus dieses Papers liegt in erster Linie auf der Entwicklung und Anwendung eines Modells der gemischt-ganzzahligen Programmierung (Mixed-Integer Linear Programming - MILP) zur Optimierung der Standortzuweisung. Es werden verschiedene Drohnen- und Hangartypen auswählt und platziert, mit dem Ziel, die Einsatzbereiche so schnell wie möglich anzufliegen und gleichzeitig eine bestimmte Beobachtungszeit am Einsatzort zu garantieren. Das Modell wird auf ein großes, dünn besiedeltes, ländliches Einsatzgebiet, das zu etwa einem Drittel aus Wald besteht, im Süden von Brandenburg, Deutschland angewendet. Die räumliche Nachfrage wird durch einen leicht reproduzierbaren und übertragbaren Ansatz mittels Open Data gemessen. Schließlich werden mehrere Instanzen mit unterschiedlichen festgelegten Anzahlen von Hangars und aufzustellenden MAVs mit dem kommerziellen State-of-the-Art Solver CPLEX gelöst und auf ihre Rechenzeit hin analysiert. T3 - Cottbus Mathematical Preprints - 32, 2025 KW - Mixed-lnteger linear programming KW - Unmanned aircraft systems KW - Micro air vehicles KW - Autonomous wildfire monitoring KW - Location-allocation optimization KW - Gemischt-ganzzahlige Programmierung KW - Drohnen KW - Drohnenhangar KW - Standortproblem KW - Autonome Waldbrandbekämpfung KW - Waldbrand KW - Überwachung KW - Drohne (Flugkörper) KW - Autonomes System KW - Standortproblem KW - Lineare Optimierung Y1 - 2025 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:co1-opus4-69422 N1 - This paper is a preprint that will be published as a post-conference proceedings of the Optimization and Wildfire Conference (O&W) that took place in Luso, Portugal, 2024 in "Lecture Notes in Operations Research" by Springer. https://doi.org/10.1007/978-3-032-03108-2 ER - TY - RPRT A1 - Zell, Sascha A1 - Schneidereit, Toni A1 - Fügenschuh, Armin A1 - Breuß, Michael T1 - Advanced search and rescue operations for drowning swimmers using autonomous unmanned aircraft systems : location optimization, flight trajectory planning and image-based localization T1 - Fortgeschrittene Such- und Rettungseinsätze für ertrinkende Schwimmer mit autonomen unbemannten Flugsystemen : Standortoptimierung, Flugtrajektorienplanung und bildgestützte Lokalisierung N2 - Drowning is among the most prevalent causes of death from unintentional injuries worldwide. Because of the time-sensitive nature of swimming accidents and the shortage of lifeguard staff resulting in unsupervised swimming areas, interest in supportive rescue methods increases. In this paper, we propose an autonomous Unmanned Aircraft System (UAS) usable by Emergency Medical Service (EMS) providers in swimmer rescue scenarios additionally to Standard Rescue Operation (SRO) equipment. The UAS consists of Unmanned Aerial Vehicles (UAVs) and purpose-built hangars located near the swimming area to store the UAVs. When receiving an alert, the UAVs autonomously navigate to the emergency site to conduct a Search and Rescue (S&R) operation for the drowning person. We introduce a Mixed-Integer Linear Programming (MILP) model to address the Facility Location Problem (FLP), assisting with identification of accessibility-optimal UAV hangar placements near the swimming area. Additionally, we present a MILP model to optimize the UAV flight trajectories in advance of the operation, allowing for efficient coordination of a heterogeneous UAV fleet. We apply the presented MILP models to a real-world scenario in the Lusatian Lake District using the state-of-the-art commercial solver CPLEX to solve the instances. Furthermore, we present a method for automated image-based swimmer localization using the state-of-the-art neural network You Only Look Once (YOLO). Finally, we use a Discrete-Event Simulation (DES) approach to quantify how much time is saved by using additional resources. N2 - Ertrinken ist weltweit eine der häufigsten Todesursachen durch unbeabsichtigte Verletzungen. Aufgrund der zeitkritischen Natur von Badeunfällen und des Personalmangels an Rettungsschwimmern, der in vielen unbewachten Badegebieten resultiert, steigt das Interesse an unterstützenden innovativen Rettungsmethoden. In diesem Beitrag stellen wir ein autonomes unbemanntes Luftfahrzeugsystem (Unmanned Aircraft System - UAS) vor, das von Rettungsdiensten bei der Rettung von Schwimmern zusätzlich zu Standard-Rettungsmitteln eingesetzt werden kann. Das UAS besteht aus unbemannten Luftfahrzeugen (Unmanned Aerial Vehicles - UAVs) und speziell angefertigten Hangars, die in der Nähe des Schwimmbereichs aufgestellt werden, um darin die UAVs zu lagern. Sobald ein Alarm eingeht, navigieren die UAVs autonom zum Unfallort, um eine Such- und Rettungsaktion (Search and Rescue - S&R) für die ertrinkende Person durchzuführen. Wir stellen ein gemischt-ganzzahliges lineares Programm (Mixed-Integer Linear Program - MILP) vor, um das Standortproblem (Facility Location Problem - FLP) zu lösen, welches die Identifizierung zeitoptimaler UAV-Hangarstandorte in der Nähe des Schwimmbereichs ermöglicht. Außerdem stellen wir ein MILP zur Optimierung von Flugtrajektorien der UAVs im Vorfeld der Mission vor, was eine effiziente Koordination einer heterogenen UAV-Flotte ermöglicht. Wir wenden die vorgestellten MILP-Modelle auf ein reales Szenario im Lausitzer Seenland an und verwenden den modernen kommerziellen Löser CPLEX, um Optimallösungen der Instanzen zufinden. Darüber hinaus stellen wir eine Methode zur automatischen bildbasierten Lokalisierung von Schwimmern vor, die das moderne neuronale Netzwerk You Only Look Once (YOLO) verwendet. Schließlich verwenden wir ereignisorientierte Simulation (Discrete-Event Simulation - DES), um zu quantifizieren, wie viel Zeit durch die Verwendung zusätzlicher Ressourcen eingespart wird. T3 - Cottbus Mathematical Preprints - 31, 2024 KW - Unmanned Aerial Vehicle KW - Unmanned Aircraft System KW - Water Rescue KW - Mixed-Integer Linear Programming KW - You Only Look Once KW - Drohne KW - Drohnenhangar KW - Wasserrettung KW - Gemischt-ganzzahlige Programmierung KW - Standortoptimierung KW - Drohne KW - Wasserrettung KW - Lineare Optimierung Y1 - 2024 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:co1-opus4-68669 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 - Zhong, Lingyu T1 - Set Covering Probleme in der Funknetzplanung T1 - Set covering problems in radio network planning N2 - In dieser Bachelorarbeit wird das Problem der Auswahl von Antennenstandorten für eine maximale räumliche Abdeckung in 5G-Funknetzen untersucht. Das Hauptziel besteht darin, eine effiziente Lösung für dieses kombinatorische Optimierungsproblem zu finden, indem es als Partial Set Covering Problem formuliert und gelöst wird. Die Arbeit gliedert sich in zwei Teile: Der erste Teil bietet eine Einführung in die mathematischen Grundlagen des Partial Set Covering Problems, einschließlich Definitionen, Formulierung und Lösungsverfahren. Im zweiten Teil wird ein praktischer Ansatz zur Lösung dieses Problems präsentiert, wobei realen Instanzen für die Auswahl von Antennenstandorten analysiert werden. Hierbei werden zwei Hauptfragen untersucht: 1) Wie kann die gegebene Instanz in ein Partial Set Covering Problem umformuliert werden? 2) Wie kann dieses Problem mithilfe eines heuristischen Verfahrens, insbesondere des Simulated-Annealing-Algorithmus, gelöst werden? Die Ergebnisse dieser Arbeit tragen dazu bei, fundierte Entscheidungen über den Aufbau von 5G-Netzen zu treffen und die Netzwerkabdeckung unter Berücksichtigung von Nebenbedingungen zu maximieren. N2 - This bachelor thesis examines the problem of selecting antenna sites for maximum spatial coverage in 5G radio networks. The main goal is to find an efficient solution to this combinatorial optimization problem by formulating and solving it as a partial set covering problem. The thesis is divided into two parts: The first part provides an introduction to the mathematical foundations of the Partial Set Covering Problem, including definitions, formulation and solution methods. In the second part, a practical approach to solve this problem is presented, analyzing real instances for antenna site selection. Two main questions are examined here: 1) How can the given instance be reformulated into a partial set covering problem? 2) How can this problem be solved using a heuristic method, in particular the simulated annealing algorithm? The results of this work help to make informed decisions about building 5G networks and to maximize network coverage considering constraints. T3 - Cottbus Mathematical Preprints - 29, 2023 KW - 5G-Funknetze KW - Antennenstandort-Optimierung KW - Kombinatorische Optimierung KW - Partial Set Covering Problem KW - Simulated-Annealing-Algorithmus KW - 5G radio networks KW - Antenna site optimization KW - Combinatorial optimization KW - Partial set covering problem KW - Simulated annealing algorithm KW - 5G KW - Funknetz KW - Antenne KW - Kombinatorische Optimierung Y1 - 2023 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:co1-opus4-63556 ER - TY - RPRT A1 - Schmidt, Johannes A1 - Fügenschuh, Armin T1 - Trajectory optimization for arbitrary layered geometries in wire-arc additive manufacturing T1 - Trajektorienoptimierung für beliebige Schichtgeometrien in der additiven Draht-Lichtbogen-Fertigung N2 - In wire-arc additive manufacturing, a wire is molten by an electrical or laser arc and deposited droplet-by-droplet to construct the desired workpiece, given as a set of two-dimensional layers. The weld source can move freely over a substrate plate, processing each layer, but there is also the possibility of moving without welding. A primary reason for stress inside the material is the large thermal gradient caused by the weld source, resulting in lower product quality. Thus, it is desirable to control the temperature of the workpiece during the process. One way of its optimization is the trajectory of the weld source. We consider the problem of finding a trajectory of the moving weld source for a single layer of an arbitrary workpiece that maximizes the quality of the part and derive a novel mixed-integer PDE-constrained model, including the calculation of a detailed temperature distribution measuring the overall quality. The resulting optimization problem is linearized and solved using the state-of-the-art numerical solver IBM CPLEX. Its performance is examined by several computational studies. N2 - Bei der additiven Draht-Lichtbogen-Fertigung wird ein Draht durch einen Licht- oder Laserlichtbogen geschmolzen und Tropfen für Tropfen aufgebracht, um das gewünschte Werkstück aus zweidimensionalen Schichten aufzubauen. Die Schweißquelle kann sich frei über eine Substratplatte bewegen und jede Schicht bearbeiten; zudem besteht auch die Möglichkeit, sich ohne Schweißen zu bewegen. Ein Hauptgrund für Spannungen im Material ist der große Wärmegradient, der durch die Schweißquelle verursacht wird, was zu einer geringeren Produktqualität führt. Daher ist es wünschenswert, die Temperatur des Werkstücks während des Prozesses zu steuern. Eine Möglichkeit dafür ist die Trajektorie der Schweißquelle. Wir betrachten das Problem, eine Trajektorie der sich bewegenden Schweißquelle für eine einzelne Schicht eines beliebigen Werkstücks zu finden, die die Qualität des Teils maximiert, und leiten ein neuartiges gemischt-ganzzahliges PDE-beschränktes Modell ab, einschließlich der Berechnung einer detaillierten Temperaturverteilung, welche zur Beurteilung der Gesamtqualität benötigt wird. Das resultierende Optimierungsproblem wird linearisiert und mit dem aktuellen numerischen Löser IBM CPLEX gelöst. Die Performanz wird in mehreren Rechenstudien untersucht. T3 - Cottbus Mathematical Preprints - 28, 2023 KW - Mixed-integer programming KW - Trajektorie KW - Partielle Differentialgleichung KW - Finite-Volumen-Methode KW - Wärmeleitung KW - Wire are additive manufacturing KW - Trajectory planning KW - Partial differential equations KW - Finite element method KW - Heat conduction KW - Gemischt-ganzzahlige Programmierung KW - Additive Draht-Lichtbogen-Fertigung, KW - Trajektorienplanung KW - Partielle Differenzialgleichungen KW - Finite-Elemente-Methode KW - Wärmeleitung Y1 - 2023 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:co1-opus4-62678 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 - Zell, Sascha T1 - Agentenbasierte Modellierung und Simulation der Rettungskette : eine Fallstudie in der Lausitz T1 - Agent based modelling and simulation of the rescue chain N2 - A functioning prehospital Emergency Medical Service (EMS) system is of special importance for society and subject to many new challenges of present time. Socioeconomic change and technical progress affect existing systems and force responsibles to adopt new approaches for performance optimization. Therefore this work provides a literature review on different EMS planning problems and presents an agent-based simulation approach to model the rescue chain of a region specific EMS system. Underlying data from urban region Cottbus, Brandenburg, Germany is used to parameterize and verify the model. Using a geographic information system (GIS), the model generates emergency calls according to population density with a time dependent rate and displays different key figures for evaluation of system performance. A graphical interface including operation and statistics monitoring was designed to lay the foundation for practical application. N2 - Ein funktionierender Rettungsdienst ist für die Gesellschaft von zentraler Bedeutung, da in medizinischen Notsituationen die Gesundheit eines Verunfallten von der Qualität der praäklinischen medizinischen Versorgung abhängt. Dabei steht man vor immer neuen Herausforderungen des sozioökonomischen Wandels und technischen Fortschritts, die neue Ansätze zur Systemoptimierung erfordern. Diese Arbeit beinhaltet eine Literaturübersicht über Planungsprobleme, sowie eine Klassifizierung von Emergency Medical Service (EMS) Systemen. Ein agentenbasiertes Simulationsmodell für ein notarztbasiertes EMS-System wird vorgestellt und auf die Rettungskette eines städtischen Gebietes Cottbus, Brandenburg, Deutschland angewandt. Die Parametrisierung des Modells erfolgt durch zugrundeliegende Einsatzdaten, dabei wird ein Geoinformationssystem (GIS) genutzt, Notrufe über die Bevölkerungsdichte mit einer zeitabhängigen Rate generiert und statistische Kenngrößen des Systems ausgewertet. Das in AnyLogic implementierte Simulationsmodell enthält eine graphische Nutzeroberfläche, in der Einsatzdetails und Statistiken als Grundlage für Anwendungen in der Praxis angezeigt werden. T3 - Cottbus Mathematical Preprints - 25, 2022 KW - Emergency medical service system KW - Agent-based simulation KW - Rescue chain KW - Rettungsdienst KW - Rettungskette KW - Agentenbasiertes Simulationsmodell KW - Cottbus KW - Rettungswesen KW - Geoinformationssystem KW - Simulation Y1 - 2022 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:co1-opus4-58731 ER - TY - THES A1 - Werger, Tabea T1 - Instandhaltungsprogramm - NH90 : ein ganzzahliger Ansatz zur Optimierung des Instandhaltungsprogramms eines militärischen Luftfahrzeugs T1 - Maintenance programme - NH90 : an integer approach for optimizing the maintenance program of a military aircraft N2 - Die vorliegende Arbeit untersucht die Instandhaltungsplanung eines militärischen Luftfahrzeugs. Das Ziel ist die Eingliederung aller Instandhaltungsaufgaben des Luftfahrzeugs in Wartungsintervalle, die durch das aktuelle Instandhaltungsprogramm festgelegt sind. Dieses besteht aus bereits gemäß ihrer Frist paketierten Instandhaltungsaufgaben und aus nicht zugeordneten Aufgaben, welche im Folgenden betrachtet werden. Gegenstand der Untersuchung sind die Arbeitsdauer und die Frist der Instandhaltungsaufgaben. Die nicht paketierten Instandhaltungsaufgaben sollen so zugeordnet werden, dass der Arbeitsaufwand und die verlorenen Tage, die durch das Vorziehen von Instandhaltungsaufgaben entstehen, auf ein Minimum reduziert werden. Dafür wird ein multikriterielles, ganzzahliges Optimierungsmodell entwickelt. Zum Lösen wird der Solver IBM ILOG CPLEX Optimization Studio (V 20.1.0.0) verwendet. In der Auswertung wird zusätzlich zu den Ergebnissen der Optimierung die Auswirkung von aggregierten und disaggregierten Formulierungen untersucht sowie der Effekt von Veränderungen der Aggressivität von Schnittebenenverfahren. N2 - The following work examines the maintenance planning of a military aircraft. The goal is the integration of all maintenance tasks of the aircraft into maintenance intervals, which are defined by the current maintenance program. The totality of the maintenance tasks consists of the already packaged tasks and those yet to be assigned. The considered factors for the assignment are the working time and the deadline of the tasks. The unpackaged maintenance tasks are to be assigned such that the workload and the lost days caused by early execution of maintenance tasks are reduced to a minimum. For this purpose a multiobjective integer optimization model was developed. The solver IBM ILOG CPLEX Optimization Studio (V 20.1.0.0) was used for solving. In addition to the general results of the optimization approach, the disparities of aggregated and disaggregated formulations were studied. Further, the consequences of altering the aggressiveness of cutting plane methods were analysed. T3 - Cottbus Mathematical Preprints - 24, 2022 KW - Gemischt-ganzzahlige Optimierung KW - Hubschrauber KW - Instandhaltung KW - Planung KW - Schnittebenenverfahren KW - Mixed-integer optimization KW - Helicopter KW - Maintenance KW - Planning KW - Cutting plane method KW - Gemischt-ganzzahlige Optimierung KW - Schnittebenenverfahren KW - Instandhaltungsplanung Y1 - 2021 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:co1-opus4-58724 ER -