@phdthesis{Zazai2020, author = {Zazai, M. Fawad}, title = {Berechnung der Trajektorien f{\"u}r die Entwicklung von optimalen Routen}, editor = {F{\"u}genschuh, Armin}, issn = {2627-6100}, doi = {10.26127/BTUOpen-5228}, url = {http://nbn-resolving.de/urn:nbn:de:kobv:co1-opus4-52286}, school = {BTU Cottbus - Senftenberg}, year = {2020}, abstract = {Die Konstruktionsplanung von neuen Transitrouten oder Energieleitungen auf einem topografischen Gel{\"a}nde wird von Ingenieuren in der Regel manuell vorgenommen, ohne dass eine Optimalit{\"a}t garantiert werden kann. Wir stellen einen neuen Ansatz zur Berechnung von Trajektorien f{\"u}r die Entwicklung neuer optimaler Transitrouten und Energieleitungen zwischen zwei Standorten auf einer Untermannigfaltigkeit U von IR³ vor. Diese Untermannigfaltigkeit repr{\"a}sentiert die Topographie eines Gel{\"a}ndes. U wird n{\"a}herungsweise durch ein spezielles gewichtetes Gitternetz modelliert. Auf diesem Gitternetz werden die k{\"u}rzesten Wege f{\"u}r den Bau neuer Routen bestimmt, wobei wir drei Optimierungskriterien betrachten werden: Routen mit minimaler L{\"a}nge, Routen mit geringsten Baukosten und Routen mit minimalen absoluten H{\"o}henvariationen oder minimalen absoluten Steigungen. Anschließend wird eine Kombination dieser Kriterien gebildet, um dieses Problem zu einem multikriteriellen Optimierungsproblem zu erweitern. Ein Algorithmus f{\"u}r den k{\"u}rzesten Weg, wie der Dijkstra-Algorithmus, wird verwendet, um optimale Kompromisse f{\"u}r die Konstruktion neuer Routen zu berechnen.}, subject = {K{\"u}rzeste Wege; Trajektorienplanung; Optimale Routen; Multikriterielle Optimierung (Pareto-Front); Geoinformationssysteme; Shortest paths; Trajectory planning; Optimal routes; Multi-criteria optimization (Pareto frontier); Geographic information system; Bahnplanung; Geoinformationssystem; K{\"u}rzester-Weg-Problem; Multikriterielle Optimierung}, language = {de} } @misc{Werger2021, type = {Master Thesis}, author = {Werger, Tabea}, title = {Instandhaltungsprogramm - NH90 : ein ganzzahliger Ansatz zur Optimierung des Instandhaltungsprogramms eines milit{\"a}rischen Luftfahrzeugs}, doi = {10.26127/BTUOpen-5872}, url = {http://nbn-resolving.de/urn:nbn:de:kobv:co1-opus4-58724}, school = {BTU Cottbus - Senftenberg}, year = {2021}, abstract = {Die vorliegende Arbeit untersucht die Instandhaltungsplanung eines milit{\"a}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{\"a}ß 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{\"u}r wird ein multikriterielles, ganzzahliges Optimierungsmodell entwickelt. Zum L{\"o}sen wird der Solver IBM ILOG CPLEX Optimization Studio (V 20.1.0.0) verwendet. In der Auswertung wird zus{\"a}tzlich zu den Ergebnissen der Optimierung die Auswirkung von aggregierten und disaggregierten Formulierungen untersucht sowie der Effekt von Ver{\"a}nderungen der Aggressivit{\"a}t von Schnittebenenverfahren.}, subject = {Gemischt-ganzzahlige Optimierung; Hubschrauber; Instandhaltung; Planung; Schnittebenenverfahren; Mixed-integer optimization; Helicopter; Maintenance; Planning; Cutting plane method; Gemischt-ganzzahlige Optimierung; Schnittebenenverfahren; Instandhaltungsplanung}, language = {de} } @masterthesis{Werger2019, type = {Bachelor Thesis}, author = {Werger, Tabea}, title = {Eine Anwendung der ganzzahligen Optimierung auf die Stundenplanerstellung einer Unteroffiziersschule der Bundeswehr}, editor = {F{\"u}genschuh, Armin}, issn = {2627-6100}, doi = {10.26127/BTUOpen-4803}, url = {http://nbn-resolving.de/urn:nbn:de:kobv:co1-opus4-48036}, school = {BTU Cottbus - Senftenberg}, year = {2019}, abstract = {Die Bachelorarbeit besch{\"a}ftigt sich mit der Erstellung eines m{\"o}glichst guten, zul{\"a}ssigen Stundenplans f{\"u}r eine Unteroffiziersschule der Bundeswehr. Die Bildungseinrichtung kann vorhandene Optimierungsprogramme f{\"u}r Stundenpl{\"a}ne nur teilweise zu Rate ziehen, da hier im Vergleich zu normalen Schulen und Universit{\"a}ten die Veranstaltungen nicht in einem Wochenzyklus stattfinden. Des Weiteren gibt es Spezialveranstaltungen, die nur an bestimmten Tagen besucht werden k{\"o}nnen. Zus{\"a}tzlich haben die zu absolvierenden Kurse eine fest vorgegebene Reihenfolge, die beachtet werden muss.}, subject = {Mixed-integer programming; Operational research; School time table planning; Ganzzahlige Optimierung; Stundenplanerstellung}, language = {de} } @techreport{GnegelFuegenschuh2019, author = {Gnegel, Fabian and F{\"u}genschuh, Armin}, title = {An iterative graph expansion approach for the scheduling and routing of airplanes}, editor = {F{\"u}genschuh, Armin}, issn = {2627-6100}, doi = {10.26127/BTUOpen-4806}, url = {http://nbn-resolving.de/urn:nbn:de:kobv:co1-opus4-48069}, year = {2019}, abstract = {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.}, subject = {Mixed Integer Linear Programming; Operational Research; Vehicle Routing Problem; Time-Dependent Airplane Routing; Dynamic Graph Expansion; Routing; Mehrdepotproblem; Expandierender Graph}, language = {en} } @techreport{DeeFuegenschuhKaimakamis2021, type = {Working Paper}, author = {Dee, Robin and F{\"u}genschuh, Armin and Kaimakamis, George}, title = {The unit re-balancing problem}, doi = {10.26127/BTUOpen-5658}, url = {http://nbn-resolving.de/urn:nbn:de:kobv:co1-opus4-56587}, year = {2021}, abstract = {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.}, subject = {Re-balancing problem; Efficiency; Mixed-integer linear programming; Bi-criteria optimization; Umverteilungsproblem; Effizienz; Gemischt-ganzzahlige Programmierung; Bikriterielle Optimierung; Ganzzahlige Optimierung; Optimierungsproblem; Effizienz}, language = {en} } @techreport{JohannsmannCraparoDiekenetal.2020, type = {Working Paper}, author = {Johannsmann, Leonie M. and Craparo, Emily M. and Dieken, Thor L. and F{\"u}genschuh, Armin and Seitner, Bj{\"o}rn O.}, title = {Stochastic mixed-integer programming for a spare parts inventory management problem}, editor = {F{\"u}genschuh, Armin}, issn = {2627-6100}, doi = {10.26127/BTUOpen-5080}, url = {http://nbn-resolving.de/urn:nbn:de:kobv:co1-opus4-50802}, year = {2020}, abstract = {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.}, subject = {Logisitcs; Scenario generation; Bestandsmanagement; Logistik; Ganzzahlige Optimierung; Stochastische Optimierung; Operations Research; Uncertainty; Warehouse management; Operations research; Two-stage stochastic optimization; Mixed-integer programming; Logistik; Szenario-Erzeugung; Unsicherheit; Lagermanagement; Gemischt-ganzzahlige Optimierung; Unternehmensforschung; Zweistufige stochastische Optimierung}, language = {en} } @techreport{StieberFuegenschuh2019, author = {Stieber, Anke and F{\"u}genschuh, Armin}, title = {Dealing with time in the multiple traveling salesmen problem with moving targets}, editor = {F{\"u}genschuh, Armin}, issn = {2627-6100}, doi = {10.26127/BTUOpen-4824}, url = {http://nbn-resolving.de/urn:nbn:de:kobv:co1-opus4-48245}, year = {2019}, abstract = {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.}, subject = {Dynamic traveling salesmen problem; Moving targets; Time-relaxation; Integer linear programming; Second-order cone programming; Travelling-salesman-Problem}, language = {en} } @techreport{SchmidtFuegenschuh2025, type = {Working Paper}, author = {Schmidt, Johannes and F{\"u}genschuh, Armin}, title = {Inter-sample avoidance in trajectory planning via an integer-polytope formulation for mixed-integer optimization}, doi = {10.26127/BTUOpen-7169}, url = {http://nbn-resolving.de/urn:nbn:de:kobv:co1-opus4-71697}, year = {2025}, abstract = {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.}, subject = {Mixed-integer optimization; Inter-sample avoidance; Trajectory planning; Convex hull; Unmanned aerial vehicles; Gemischt-ganzzahlige Optimierung; Trajektorienplanung; Konvexe H{\"u}lle; Unbemannte Luftfahrzeuge; Drohne (Flugk{\"o}rper); Autonomes System; Bahnplanung; Gemischt-ganzzahlige Optimierung; Konvexe H{\"u}lle}, language = {en} } @inproceedings{OPUS4-7129, title = {Book of open problems : 11th workshop on graph classes, optimization, and width parameters (GROW 2024)}, editor = {Beisegel, Jesse and Scheffler, Robert and K{\"o}hler, Ekkehard}, doi = {10.26127/BTUOpen-7129}, url = {http://nbn-resolving.de/urn:nbn:de:kobv:co1-opus4-71295}, year = {2025}, abstract = {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.}, subject = {Graph theory; Graph classes; Graph parameters; Graph algorithms; Graphenalgorithmen; Graphklassen; Graphparameter; Graphentheorie; Graphentheorie}, language = {en} } @techreport{AuerDosaDulaietal.2019, author = {Auer, Peter and D{\´o}sa, Gy{\"o}rgy and Dulai, Tibor and F{\"u}genschuh, Armin and N{\"a}ser, Peggy and Ortner, Ronald and Werner-Stark, {\´A}gnes}, title = {A new heuristic and an exact approach for a production planning problem}, editor = {F{\"u}genschuh, Armin}, issn = {2627-6100}, doi = {10.26127/BTUOpen-4827}, url = {http://nbn-resolving.de/urn:nbn:de:kobv:co1-opus4-48278}, year = {2019}, abstract = {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.}, subject = {Production planning; Mixed-integer programming; Heuristics; Simulation; Fertigungsprogrammplanung; Heuristik; Optimierung}, language = {en} }