TY - THES A1 - Zazai, M. Fawad ED - Fügenschuh, Armin T1 - Berechnung der Trajektorien für die Entwicklung von optimalen Routen T1 - Computing the trajectories for the development of optimal routes N2 - Die Konstruktionsplanung von neuen Transitrouten oder Energieleitungen auf einem topografischen Gelände wird von Ingenieuren in der Regel manuell vorgenommen, ohne dass eine Optimalität garantiert werden kann. Wir stellen einen neuen Ansatz zur Berechnung von Trajektorien für die Entwicklung neuer optimaler Transitrouten und Energieleitungen zwischen zwei Standorten auf einer Untermannigfaltigkeit U von IR³ vor. Diese Untermannigfaltigkeit repräsentiert die Topographie eines Geländes. U wird näherungsweise durch ein spezielles gewichtetes Gitternetz modelliert. Auf diesem Gitternetz werden die kürzesten Wege für den Bau neuer Routen bestimmt, wobei wir drei Optimierungskriterien betrachten werden: Routen mit minimaler Länge, Routen mit geringsten Baukosten und Routen mit minimalen absoluten Hö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ür den kürzesten Weg, wie der Dijkstra-Algorithmus, wird verwendet, um optimale Kompromisse für die Konstruktion neuer Routen zu berechnen. N2 - Planning the construction of new transit routes or power lines on terrain is usually carried out manually by engineers, with no guarantee of optimality. We introduce a new approach for the computation of optimal trajectories for the development of new transit routes and power lines between two locations on a submanifold U of IR³ representing the topography of a terrain. U is approximatively modeled by a special weighted grid. On this grid, the shortest paths for the construction of new routes are determined, whereby we consider three optimization criteria: routes with minimal length, routes with lowest construction costs, and routes with minimum absolute altitude variations or minimum absolute gradients. Subsequently, a combination of these criteria is used to expand this problem into a multi-criteria optimization problem. A shortest path algorithm, such as the Dijkstra algorithm, is used to compute optimal compromises for the construction of new routes. T3 - Cottbus Mathematical Preprints - 14, 2020 KW - Kürzeste Wege KW - Trajektorienplanung KW - Optimale Routen KW - Multikriterielle Optimierung (Pareto-Front) KW - Geoinformationssysteme KW - Shortest paths KW - Trajectory planning KW - Optimal routes KW - Multi-criteria optimization (Pareto frontier) KW - Geographic information system KW - Bahnplanung KW - Geoinformationssystem KW - Kürzester-Weg-Problem KW - Multikriterielle Optimierung Y1 - 2020 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:co1-opus4-52286 SN - 2627-6100 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 - TY - THES A1 - Werger, Tabea ED - Fügenschuh, Armin T1 - Eine Anwendung der ganzzahligen Optimierung auf die Stundenplanerstellung einer Unteroffiziersschule der Bundeswehr N2 - Die Bachelorarbeit beschäftigt sich mit der Erstellung eines möglichst guten, zulässigen Stundenplans für eine Unteroffiziersschule der Bundeswehr. Die Bildungseinrichtung kann vorhandene Optimierungsprogramme für Stundenpläne nur teilweise zu Rate ziehen, da hier im Vergleich zu normalen Schulen und Universitäten die Veranstaltungen nicht in einem Wochenzyklus stattfinden. Des Weiteren gibt es Spezialveranstaltungen, die nur an bestimmten Tagen besucht werden können. Zusätzlich haben die zu absolvierenden Kurse eine fest vorgegebene Reihenfolge, die beachtet werden muss. T3 - Cottbus Mathematical Preprints - 2, 2019 KW - Mixed-integer programming KW - Operational research KW - School time table planning KW - Ganzzahlige Optimierung KW - Stundenplanerstellung Y1 - 2019 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:co1-opus4-48036 SN - 2627-6100 ER - TY - RPRT A1 - Gnegel, Fabian A1 - Fügenschuh, Armin ED - Fügenschuh, Armin T1 - An iterative graph expansion approach for the scheduling and routing of airplanes N2 - A tourism company that offers fly-in safaris is faced with the challenge to route and schedule its fleet of airplanes in an optimal way. Over the course of a given time horizon several groups of tourists have to be picked up at airports and flown to their destinations within a certain time-window. Furthermore the number of available seats, the consumption of fuel, the maximal takeoff weight, and restrictions on the detour of the individual groups have to be taken into account. The task of optimally scheduling the airplanes and tour groups belongs to the class of vehicle routing problems with pickup and delivery and time-windows. A flow-over-flow formulation on the time expanded graph of the airports was used in the literature in order to model this problem as a mixed integer linear program. Most of the benchmark problems however could not be solved within a time limit of three hours, which was overcome by formulating the problem for a simplified (time-free) graph and the use of an incumbent callback to check for feasibility in the original graph. While this approach led to very good results for instances, where few time-free solutions were infeasible for the original problem, some instances remained unsolved. In order to overcome this problem we derive two new exact formulations that include time as variables. Although these formulations by themselves are not better than the approach from the literature, they allow for an effective construction of graphs which can be interpreted as intermediate graphs between the graph of airports and the expanded graph with vertices for each visit. Using similar relaxation techniques to the time-free approach and constructing these graphs based on solutions of the relaxations guarantees that only critical airports are expanded. A computational study was performed in order to compare the new formulations to the methods from the literature. Within a time limit of 3 hours the new approach was able to find proven optimal solutions for all previously unsolved benchmark instances. Furthermore the average computation time of all benchmark instances was reduced by 90 percent. N2 - Ein Reiseunternehmen, das Fly-in Safaris anbietet, stellt sich die Aufgabe, seine Flottenrouten und deren Zeitplanung optimal zu gestalten. In einem feststehenden Zeitraum müssen mehrere Touristengruppen unter Einhaltung von Fristen von ihrem aktuellen Aufenthaltsort per Flugzeug abgeholt und zu ihrem nächsten Zielflughafen geflogen werden. Weiterhin muss Rücksicht auf die beschränkte Anzahl von Sitzen, den Treibstoffverbrauch, das maximale Startgewicht und Bedingungen an die Umwege der einzelnen Gruppen genommen werden. Die Aufgabe, die Routen der Flugzeuge festzulegen und zeitlich zu planen, gehört zur Problemklasse der Vehicle Routing Probleme mit Pickup und Delivery und Zeitfenstern. Eine Flow-over-Flow Formulierung auf dem zeitexpandierten Graphen der Flughäfen wurde in der Literatur benutzt, um dieses Problem als gemischt-ganzzahliges lineares Programm zu formulieren. Allerdings konnten die meisten Benchmarkprobleme nicht innerhalb von einem Zeitlimit von drei Stunden gelöst werden, was dadurch behoben wurde, dass das Problem für einen vereinfachten (zeitfreien) Graphen formuliert und ein Incumbent Callback zum Überprüfen der Zulässigkeit für den ursprünglichen Graphen implementiert wurde. Während dieser Ansatz sehr gute Resultate für Probleminstanzen lieferte, bei denen nur wenige zeitfreie Lösungen für das ursprüngliche Problem unzulässig waren, blieben einige Instanzen ungelöst. Um dies zu verbessern, leiten wir zwei neue exakte Formulierungen her, die den Aspekt der Zeit als Variablen beinhalten. Obwohl diese Formulierungen für sich genommen nicht besser sind als der zeitfreie Ansatz aus der Literatur, erlauben sie eine effektive Konstruktion von Graphen, die als Zwischenstufen vom Graphen der Flughäfen und dem expandierten Graphen mit Knoten für jede Ankunft angesehen werden können. Die Benutzung von ähnlichen Relaxationstechniken wie im zeitfreien Ansatz und das Aufbauen dieser Graphen anhand von Lösungen der Relaxierungen garantiert, dass nur kritische Knoten expandiert werden. Eine Rechenstudie wurde durchgeführt, um die neuen Formulierungen mit den Methoden aus der Literatur zu vergleichen. Innerhalb eines Zeitlimits von drei Stunden war der neue Ansatz in der Lage, alle vorher ungelösten Benchmarkproblem bis zur beweisbaren Optimalität zu lösen. Außerdem wurde die durchschnittliche Rechenzeit um 90 Prozent reduziert. T3 - Cottbus Mathematical Preprints - 3, 2019 KW - Mixed Integer Linear Programming KW - Operational Research KW - Vehicle Routing Problem KW - Time-Dependent Airplane Routing KW - Dynamic Graph Expansion KW - Routing KW - Mehrdepotproblem KW - Expandierender Graph Y1 - 2019 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:co1-opus4-48069 SN - 2627-6100 ER - TY - RPRT A1 - Dee, Robin A1 - Fügenschuh, Armin A1 - Kaimakamis, George T1 - The unit re-balancing problem T1 - Das Einheiten-Umverteilungs-Problem N2 - We describe the problem of re-balancing a number of units distributed over a geographic area. Each unit consists of a number of components. A value between 0 and 1 describes the current rating of each component. By a piecewise linear function this value is converted into a nominal status assessment. The lowest of the statuses determines the efficiency of a unit, and the highest status its cost. An unbalanced unit has a gap between these two. To re-balance the units, components can be transferred. The goal is to maximize the efficiency of all units. On a secondary level, the cost for the re-balancing should be minimal. We present a mixed-integer nonlinear programming formulation for this problem, which describes the potential movement of components as a multi-commodity flow. The piecewise linear functions needed to obtain the status values are reformulated using inequalities and binary variables. This results in a mixed-integer linear program, and numerical standard solvers are able to compute proven optimal solutions for instances with up to 100 units. We present numerical solutions for a set of test instances and a bi-criteria objective function, and discuss the trade-off between cost and efficiency. N2 - Wir beschreiben das Problem der Umverteilung einer Anzahl von Einheiten, die über ein geografisches Gebiet verteilt sind. Jede Einheit besteht aus einer Reihe von Komponenten. Ein Wert zwischen 0 und 1 beschreibt die aktuelle Bewertung jeder Komponente. Durch eine stückweise lineare Funktion wird dieser Wert in eine nominale Zustandsbewertung umgerechnet. Der niedrigste Status bestimmt die Effizienz einer Einheit und der höchste Status seine Kosten. Eine unausgeglichene Einheit weist eine Lücke zwischen diesen beiden auf. Um die Einheiten neu auszubalancieren, können Komponenten übertragen werden. Ziel ist es, die Effizienz aller Einheiten zu maximieren. Auf einer untergeordneten Ebene sollten die Kosten für die Umverteilung minimal sein. Für dieses Problem stellen wir eine gemischt-ganzzahlige nichtlineare Modellformulierung vor, die die potenzielle Bewegung von Komponenten als Mehrgüterfluss beschreibt. Die stückweise linearen Funktionen, die zum Erhalten der Statuswerte benötigt werden, werden unter Verwendung von Ungleichungen und binären Variablen umformuliert. Dies führt zu einem gemischt-ganzzahligen linearen Programm, und numerische Standardlöser sind in der Lage, beweisbar optimale Lösungen für Instanzen mit bis zu 100 Einheiten zu berechnen. Wir präsentieren numerische Lösungen für eine Reihe von Testinstanzen und eine bikriterielle Zielfunktion und diskutieren den Kompromiss zwischen Kosten und Effizienz. T3 - Cottbus Mathematical Preprints - 22, 2021 KW - Re-balancing problem KW - Efficiency KW - Mixed-integer linear programming KW - Bi-criteria optimization KW - Umverteilungsproblem KW - Effizienz KW - Gemischt-ganzzahlige Programmierung KW - Bikriterielle Optimierung KW - Ganzzahlige Optimierung KW - Optimierungsproblem KW - Effizienz Y1 - 2021 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:co1-opus4-56587 ER - TY - RPRT A1 - Johannsmann, Leonie M. A1 - Craparo, Emily M. A1 - Dieken, Thor L. A1 - Fügenschuh, Armin A1 - Seitner, Björn O. ED - Fügenschuh, Armin T1 - Stochastic mixed-integer programming for a spare parts inventory management problem N2 - The German Armed Forces provide an operation contingent to support the North Atlantic Treaty Organization (NATO) Response Force (NRF). For this purpose, a „warehouse” containing accommodations, food supplies, medical supplies, and spare parts for the systems has to be available. Such a warehouse is restricted in weight, in order to be quickly movable in an upcoming deployment situation. It should be able to supply the NRF troops for a certain amount of time (e.g., one month) without re-supply from the outside. To ensure optimal use of such a restricted warehouse, we developed the computer program „The OPtimization of a Spare Parts Inventory” (TOPSPIN) to find an optimal mix of spare parts to restore a set of systems to functionality. Each system is composed of several parts, and it can only be used again in the mission if all broken parts are replaced. The failure rate of the individual parts follows a given random distribution, and during deployment it is expected to be higher than in the homeland. Due to the stochastic nature of the problem, we generate scenarios that simulate the actual failure of the parts. The backbone of TOPSPIN is a mixed-integer linear program that determines an optimal, scenario-robust mix of spare parts and is solved using standard state-of-the-art numerical solvers. Using input data provided by the Logistikzentrum, we analyze how many scenarios need to be generated in order to determine reliable solutions. Moreover, we analyze the composition of the warehouse over a variety of different weight restrictions, and we calculate the number of repairable systems as a function of this bound. N2 - Die Bundeswehr stellt ein Einsatzkontingent zur Unterstützung der NATO Response Force (NRF) zur Verfügung. Zu diesem Zweck muss ein Lager mit Unterkünften, Lebensmitteln, medizinischer Versorgung und Ersatzteilen für die Systeme vorhanden sein. Ein solches Lager ist gewichtsbeschränkt, um in einer bevorstehenden Einsatzsituation schnell versendbar zu sein. Es sollte in der Lage sein, die NRF-Truppen für eine bestimmte Zeitspanne (z. B. einen Monat) zu versorgen, ohne von außen erneut zu versorgt zu werden. Um eine optimale Nutzung eines solchen eingeschränkten Lagers zu gewährleisten, haben wir das Computerprogramm „The OPtimization of a Spare Parts INventory" (TOPSPIN) entwickelt, um eine optimale Mischung von Ersatzteilen zu finden, mit der die Funktionalität einer Reihe von Systemen wiederhergestellt werden kann. Jedes System besteht aus mehreren Teilen und kann nur dann in der Mission wieder verwendet werden, wenn alle defekten Teile ersetzt wurden. Die Ausfallrate der einzelnen Teile richtet sich nach einer vorgegebenen Zufallsverteilung und wird im Einsatz voraussichtlich höher sein als im Heimatland. Aufgrund der stochastischen Natur des Problems generieren wir Szenarien, die den tatsächlichen Ausfall der Teile simulieren. Das Grundgerüst von TOPSPIN ist ein lineares gemischt-ganzzahliges Programm, das einen optimalen, Szenario-stabilen Ersatzteilmix ermittelt und mit den modernen numerischen Standardverfahren gelöst wird. Anhand der vom Logistikzentrum der Bundeswehr bereitgestellten Eingangsdaten analysieren wir, wie viele Szenarien generiert werden müssen, um verlässliche Lösungen zu ermitteln. Darüber hinaus analysieren wir die Zusammensetzung des Lagers über verschiedene Gewichtsbeschränkungen und berechnen die Anzahl der reparierbaren Systeme in Abhängigkeit von dieser Grenze. T3 - Cottbus Mathematical Preprints - 11, 2020 KW - Logisitcs KW - Scenario generation KW - Bestandsmanagement KW - Logistik KW - Ganzzahlige Optimierung KW - Stochastische Optimierung KW - Operations Research KW - Uncertainty KW - Warehouse management KW - Operations research KW - Two-stage stochastic optimization KW - Mixed-integer programming KW - Logistik KW - Szenario-Erzeugung KW - Unsicherheit KW - Lagermanagement KW - Gemischt-ganzzahlige Optimierung KW - Unternehmensforschung KW - Zweistufige stochastische Optimierung Y1 - 2020 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:co1-opus4-50802 SN - 2627-6100 ER - TY - RPRT A1 - Stieber, Anke A1 - Fügenschuh, Armin ED - Fügenschuh, Armin T1 - Dealing with time in the multiple traveling salesmen problem with moving targets N2 - The multiple traveling salesmen problem with moving targets is a generalization of the classical traveling salesmen problem, where the targets (cities or objects) are moving over time. Additionally, for each target a visibility time window is given. The task is to find routes for several salesmen so that each target is reached exactly once within its visibility time window and the sum of all traveled distances of all salesmen is minimal. We present different modeling formulations for this TSP variant. The time requirements are modeled differently in each approach. Our goal is to examine what formulation is most suitable in terms of runtime to solve the multiple traveling salesmen problem with moving targets with exact methods. Computational experiments are carried out on randomly generated test instances to compare the different modeling approaches. The results for large-scale instances show, that the best way to model time requirements is to directly insert them into a formulation with discrete time steps. N2 - Das Problem des multiplen Handlungsreisenden mit bewegten Zielen ist eine Verallgemeinerung des Problems des klassischen Handlungsreisenden (TSP), bei dem sich die Ziele (Städte oder Objekte) im Laufe der Zeit bewegen. Zusätzlich wird für jedes Ziel ein Sichtbarkeitszeitfenster angegeben. Die Aufgabe besteht darin, Routen für mehrere Handlungsreisende zu finden, so dass jedes Ziel innerhalb seines Sichtbarkeitszeitfensters genau einmal erreicht wird und die Summe aller zurückgelegten Entfernungen aller Handlungsreisenden minimal ist. Wir präsentieren verschiedene Modellformulierungen für diese TSP-Variante. Die Zeitrestriktionen werden in jedem Ansatz unterschiedlich modelliert. Unser Ziel ist es zu untersuchen, welche Formulierung in Bezug auf die Laufzeit am besten geeignet ist, um das Problem mit mehreren Handlungsreisenden mit bewegten Zielen mit exakten Methoden, welche globale Optimalität garantieren, zu lösen. Computerversuche werden an zufällig generierten Testinstanzen durchgeführt, um die verschiedenen Modellierungsansätze zu vergleichen. Die Ergebnisse für umfangreiche Instanzen zeigen, dass der beste Weg, um Zeitanforderungen zu modellieren, darin besteht, sie in diskreten Zeitschritten direkt in die Formulierung einzufügen. T3 - Cottbus Mathematical Preprints - 4, 2019 KW - Dynamic traveling salesmen problem KW - Moving targets KW - Time-relaxation KW - Integer linear programming KW - Second-order cone programming KW - Travelling-salesman-Problem Y1 - 2019 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:co1-opus4-48245 SN - 2627-6100 ER - 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 - CHAP ED - Beisegel, Jesse ED - Scheffler, Robert ED - Köhler, Ekkehard T1 - Book of open problems : 11th workshop on graph classes, optimization, and width parameters (GROW 2024) T1 - Sammlung offener Probleme : 11. Workshop über Graphenklassen, Optimierung und Weiteparameter (GROW 2024) N2 - The Workshop on Graph Classes, Optimization, and Width Parameters (GROW) series of workshops brings together experts in both theoretical and practical issues to design new strategies for dealing with intractable graph problems. Its 11th edition, GROW 2024, was hosted by the Brandenburg University of Technology, Faculty of Mathematics, Computer Science, Physics, Electrical Engineering and Information Technology, Cottbus, Germany, from September 9–12, 2024. This booklet contains descriptions of open problems presented at GROW 2024. N2 - Die Workshop-Reihe „Graph Classes, Optimization, and Width Parameters“ (GROW) bringt Experten für theoretische und praktische Fragestellungen zusammen, um neue Strategien für den Umgang mit schwer lösbaren Graphenproblemen zu entwickeln. Die 11. Ausgabe, GROW 2024, wurde vom 9. bis 12. September 2024 von der BTU Cottbus-Senftenberg, Fakultät für Mathematik, Informatik, Physik, Elektro- und Informationstechnik, Cottbus, Deutschland, ausgerichtet. Diese Sammlung enthält Beschreibungen offener Probleme, die bei der GROW 2024 vorgestellt wurden. KW - Graph theory KW - Graph classes KW - Graph parameters KW - Graph algorithms KW - Graphenalgorithmen KW - Graphklassen KW - Graphparameter KW - Graphentheorie KW - Graphentheorie Y1 - 2025 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:co1-opus4-71295 ER - TY - RPRT A1 - Auer, Peter A1 - Dósa, György A1 - Dulai, Tibor A1 - Fügenschuh, Armin A1 - Näser, Peggy A1 - Ortner, Ronald A1 - Werner-Stark, Ágnes ED - Fügenschuh, Armin T1 - A new heuristic and an exact approach for a production planning problem N2 - We deal with a very complex and hard scheduling problem. Several types of products are processed by a heterogeneous resource set, where resources have different operating capabilities and setup times are considered. The processing of the products follows different workflows, allowing also assembly lines. The goal is to process all products in minimum time, i.e., the makespan is to be minimized. Because of the complexity of the problem an exact solver would require too much running time. We propose a compound method where a heuristic is combined with an exact solver. Our proposed heuristic is composed of several phases applying different smart strategies. In order to reduce the computational complexity of the exact approach, we exploit the makespan determined by the heuristic as an upper bound for the time horizon, which has a direct in uence on the instance size used in the exact approach. We demonstrate the efficiency of our combined method on multiple problem classes. With the help of the heuristic the exact solver is able to obtain an optimal solution in a much shorter amount of time. N2 - Wir betrachten das folgende Planungsproblem: Verschiedene Arten von Produkten werden auf einer Menge von heterogenen Maschinen erstellt, welche unterschiedliche Betriebsarten und Umrüstzeiten haben. Die Verarbeitung der Produkte erfolgt nach unterschiedlichen Arbeitsablaufplänen, da die einzelnen Produkttypen unterschiedliche Fertigungsschritte erfordern. Das Ziel ist es, alle Produkte in minimaler Zeit herzustellen. Aufgrund der Komplexität des Problems benötigen exakte Lösungsverfahren eine recht hohe Rechenzeit. Wir schlagen eine zusammengesetzte Methode vor, bei dem eine Heuristik und ein exakter Löser kombiniert werden. Unsere vorgeschlagene Heuristik besteht aus mehreren Phasen, in denen verschiedene intelligente Strategien angewendet werden. Um die rechnerische Komplexität des exakten Ansatzes zu reduzieren, nutzen wir die durch die Heuristik bestimmte Fertigungsdauer als obere Grenze für den Zeithorizont, was einen direkten Einfluss auf die Instanzgröße des exakten Ansatzes hat. Wir demonstrieren die Effizienz unserer kombinierten Methode an einer großen Menge von Testinstanzen. Mit Hilfe der Heuristik ist der exakte Löser in der Lage, in deutlich kürzerer Zeit eine beweisbar-optimale Lösung zu bestimmen. T3 - Cottbus Mathematical Preprints - 5, 2019 KW - Production planning KW - Mixed-integer programming KW - Heuristics KW - Simulation KW - Fertigungsprogrammplanung KW - Heuristik KW - Optimierung Y1 - 2019 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:co1-opus4-48278 SN - 2627-6100 ER -