TY - RPRT A1 - Fügenschuh, Armin A1 - Müllenstedt, Daniel A1 - Schmidt, Johannes ED - Fügenschuh, Armin T1 - Mission planning for unmanned aerial vehicles N2 - We formulate the mission planning problem for a meet of unmanned aerial vehicles (UAVs) as a mixed-integer nonlinear programming problem (MINLP). The problem asks for a selection of targets from a list to the UAVs, and trajectories that visit the chosen targets. To be feasible, a trajectory must pass each target at a desired maximal distance and within a certain time window, obstacles or regions of high risk must be avoided, and the fuel limitations must be obeyed. An optimal trajectory maximizes the sum of values of all targets that can be visited, and as a secondary goal, conducts the mission in the shortest possible time. In order to obtain numerical solutions to this model, we approximate the MINLP by a mixed-integer linear program (MILP), and apply a state-of-the-art solver (GUROBI) to the latter on a set of test instances. N2 - Das Missionsplanungsproblem für eine Flotte unbemannter Luftfahrzeuge (UAVs) formulieren wir als nichtlineares gemischt-ganzzahliges Optimierungsproblem (MINLP). Das Problem erfordert eine Auswahl von Zielen aus einer Liste von gegebenen UAVs und deren Flugbahnen, welche die ausgewählten Ziele besuchen. Um zulässig zu sein, muss eine Flugbahn jedes Ziel in einer vorgegebenen maximalen Entfernung und innerhalb eines bestimmten Zeitfensters passieren. Ferner müssen Hindernisse oder Bereiche mit hohem Risiko vermieden werden, und die Kraftstoffbeschränkungen müssen berücksichtigt werden. Eine optimale Mission maximiert die Summe der Werte aller Ziele, die besucht werden können, und führt als sekundäres Ziel die Mission in kürzester Zeit aus. Um numerische Lösungen für dieses Modell zu erhalten, approximieren wir das MINLP durch ein gemischt-ganzzahliges lineares Programm (MILP) und wenden auf Testinstanzen einen numerischen Löser (GUROBI) an. T3 - Cottbus Mathematical Preprints - 6, 2019 KW - Mixed-integer nonlinear programming KW - Trajectory planning KW - Unmanned aerial vehicles KW - Linear approximation KW - Flugkörper KW - Tourenplanung KW - Optimierung Y1 - 2019 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:co1-opus4-48285 SN - 2627-6100 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 - Schmidt, Johannes A1 - Fügenschuh, Armin T1 - Planning inspection flights with an inhomogeneous fleet of micro aerial vehicles T1 - Planung von Inspektionsflügen mit einer inhomogenen Flotte von Kleinstdrohnen N2 - We consider the problem of planning an inspection flight to a given set of waypo- ints using an inhomogeneous fleet of multirotor, battery-driven micro aerial vehicles (MAVs). Therein, two subproblems must be solved. On the one side, the detailed trajectories of all MAVs must be planned, taking technical and environmental restrictions into account and on the other side, the MAVs must be assigned to the waypoints considering their installed equipment. The goal is to visit all waypoints in minimal time. The strong interaction of the two subproblems makes it necessary to tackle them simultaneously. Several aspects are taken into account to allow realistic solutions. A two-level time grid approach is applied to achieve smooth trajectories, while the flight dynamics of the MAVs are modeled in great detail. Safety distances must be maintained between them and they can recharge at charging stations located within the mission area. There can be polyhedral restricted air spaces that must be avoided. Furthermore, weather conditions are incorporated by polyhedral wind zones affecting the drones and each waypoint has a time window within it must be visited. We formulate this problem as a mixed-integer linear program and show whether the state-of-the-art numerical solver Gurobi is applicable to solve model instances. N2 - Wir betrachten das Problem der Planung eines Inspektionsfluges zu einer gegebenen Menge von Wegpunkten unter Verwendung einer inhomogenen Flotte von batteriebetriebenen Mikroluftfahrzeugen (Kleinstdrohnen, MAVs) mit mehreren Rotoren. Dabei müssen zwei Teilprobleme gelöst werden. Einerseits müssen die detaillierten Trajektorien aller MAVs unter Berücksichtigung technischer und umweltbedingter Restriktionen geplant werden und andererseits müssen die MAVs unter Berücksichtigung ihrer installierten Ausrüstung den Wegpunkten zugeordnet werden. Ziel ist es, alle Wegpunkte in kürzester Zeit zu erreichen. Die starke Wechselwirkung der beiden Teilprobleme macht es notwendig, sie gleichzeitig zu betrachten. Mehrere Aspekte werden berücksichtigt, um realistische Lösungen zu ermöglichen. Ein zweistufiger Zeitrasteransatz wird angewendet, um glatte Flugbahnen zu erzielen, während die Flugdynamik der MAVs sehr detailliert modelliert wird. Zwischen ihnen müssen Sicherheitsabstände eingehalten werden und sie können an Ladestationen im Einsatzgebiet aufgeladen werden. Es kann polyedrisch begrenzte Lufträume geben, die umflogen werden müssen. Darüber hinaus werden Wetterbedingungen durch polyedrische Windzonen berücksichtigt, die die Drohnen beeinflussen und jeder Wegpunkt hat ein Zeitfenster, innerhalb dessen er besucht werden muss. Wir formulieren dieses Problem als gemischt-ganzzahliges lineares Programm und zeigen, dass moderne numerische Löser, wie Gurobi, zur Lösung von Modellinstanzen anwendbar sind. T3 - Cottbus Mathematical Preprints - 21, 2021 KW - Mixed integer linear programming KW - Inspection path planning KW - Trajectory planning KW - Micro aerial vehicles KW - Gemischt-ganzzahlige Programmierung KW - Inspektionspfadplanung KW - Trajektorienplanung KW - Kleinstdrohnen KW - Ganzzahlige Optimierung KW - Tourenplanung KW - Drohne Y1 - 2021 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:co1-opus4-56569 ER - TY - RPRT A1 - Bähr, Martin A1 - Buhl, Johannes A1 - Radow, Georg A1 - Schmidt, Johannes A1 - Bambach, Markus A1 - Breuß, Michael A1 - Fügenschuh, Armin ED - Fügenschuh, Armin T1 - Stable honeycomb structures and temperature based trajectory optimization for wire-arc additive manufacturing N2 - We consider two mathematical problems that are connected and occur in the layer-wise production process of a workpiece using Wire-Arc Additive Manufacturing. As the first task, we consider the automatic construction of a honeycomb structure, given the boundary of a shape of interest. In doing this we employ Lloyd’s algorithm in two different realizations. For computing the incorporated Voronoi tesselation we consider the use of a Delaunay triangulation or alternatively, the eikonal equation. We compare and modify these approaches with the aim of combining their respective advantages. Then in the second task, to find an optimal tool path guaranteeing minimal production time and high quality of the workpiece, a mixed-integer linear programming problem is derived. The model takes thermal conduction and radiation during the process into account and aims to minimize temperature gradients inside the material. Its solvability for standard mixed-integer solvers is demonstrated on several test-instances. The results are compared with manufactured workpieces. N2 - Wir betrachten zwei verbundene mathematische Probleme, welche bei der schichtweisen Herstellung eines Werkstücks mittels des Lichtbogendraht-Auftragschweißen, einem additiven Fertigungsverfahren, auftreten. Als erste Aufgabe betrachten wir die automatische Konstruktion einer Wabenstruktur unter Berücksichtigung des Randes einer gewünschten Form. Dabei setzen wir Lloyds Algorithmus in zwei verschiedenen Varianten ein. Zur Berechnung der einbezogenen Voronoi-Parkettierung betrachten wir die Verwendung einer Delaunay-Triangulation und alternativ dazu der Eikonal-Gleichung. Wir vergleichen und modifizieren diese Ansätze mit dem Ziel, ihre jeweiligen Vorteile zu kombinieren. In der zweiten Aufgabe wird dann, um einen optimalen Weg für das Werkzeug zu finden, der eine minimale Produktionszeit zusammen mit einer hohen Qualität des Werkstücks garantiert, ein gemischt-ganzzahliges lineares Programm (MILP) hergeleitet. Das Modell berücksichtigt Wärmeleitung und Strahlung während des Prozesses und zielt darauf ab, Temperaturgradienten innerhalb des Materials zu minimieren. Die Lösbarkeit für Standard-MILP-Löser wird in mehreren Testfällen demonstriert. Die Ergebnisse werden mit real gefertigten Werkstücken verglichen. T3 - Cottbus Mathematical Preprints - 10, 2019 KW - Eikonal equation KW - Centroidal Voronoi tessellation KW - Additive manufacturing KW - Heat transmission KW - Mixed-integer linear programming KW - Geometric optimization KW - Additive Fertigung KW - Gemischt-ganzzahlige Programmierung KW - Geometrische Optimierung KW - Eikonal-Gleichung KW - Zentrierte Voronoi-Parkettierung KW - Wärmeleitung KW - Rapid Prototyping KW - Eikonal KW - Ganzzahlige Optimierung KW - Geometrische Optimierung KW - Wärmeleitung Y1 - 2019 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:co1-opus4-50796 SN - 2627-6100 ER - TY - RPRT A1 - Zazai, M. Fawad A1 - Fügenschuh, Armin ED - Fügenschuh, Armin T1 - Computing the trajectories for the development of optimal routes T1 - Berechnung von Trajektorien für die Entwicklung optimaler Routen N2 - Planning the construction of new transport 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 an optimal trajectory for the construction of new transit routes and power lines between two locations on a submanifold U _ R3 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 minimum distance, 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. N2 - Die Planung des Baus neuer Transportwege oder Stromleitungen im Gelände erfolgt in der Regel manuell durch Ingenieure, ohne Nachweis für deren Optimalität. Wir stellen einen neuen Ansatz für die Berechnung einer optimalen Trajektorie für den Bau neuer Transitrouten und Stromleitungen zwischen zwei Standorten auf einer Untermannigfaltigkeit U des dreidimensionalen Raums vor, welche die Topographie eines Geländes darstellt. U wird durch einen speziell gewichtetes Gittergraphen näherungsweise modelliert. In diesem Graph werden die kürzesten Wege für den Bau neuer Strecken ermittelt, wobei drei Optimierungskriterien berücksichtigt werden: Strecken mit minimaler Entfernung, Strecken mit geringsten Baukosten und Strecken mit minimalen absoluten Höhenunterschieden oder minimalen absoluten Steigungen. Anschließend wird eine Kombination dieser Kriterien verwendet, um dieses Problem zu einem Optimierungsproblem mit mehreren Kriterien zu erweitern. Ein Kürzeste-Wege-Algorithmus, wie das Dijkstra-Verfahren, wird verwendet, um optimale Kompromisse für die Erstellung neuer Routen zu berechnen. T3 - Cottbus Mathematical Preprints - 9, 2019 KW - Shortest path KW - Graph construction KW - Multi-criteria optimization (Pareto frontier) KW - Trajectory planning KW - Topography KW - Kürzeste Wege KW - Graphen-Aufbau KW - Geographische Informationssysteme (GIS) KW - Mehrzieloptimierung (Pareto-Front) KW - Trajektorienplanung KW - Geoinformationssystem KW - Kürzester-Weg-Problem KW - Bahnplanung Y1 - 2019 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:co1-opus4-50651 SN - 2627-6100 ER - TY - RPRT A1 - Gnegel, Fabian A1 - Schaudt, Stefan A1 - Clausen, Uwe A1 - Fügenschuh, Armin ED - Fügenschuh, Armin T1 - A 2D layered graph approach for scheduling delivery robots T1 - Ein geschichteter 2D Graphen Ansatz für die Ablaufplanung von Lieferrobotern N2 - In recent years parcel volumes reached record highs. The logistics industry is seeking new innovative concepts to keep pace. For densely populated areas delivery robots are a promising alternative to conventional trucking. These electric robots drive autonomously on sidewalks and deliver urgent goods, such as express parcels, medicine, or meals. The limited cargo space and battery capacity of these vehicles necessitates a depot visit after each customer served. The problem can be formulated as an electric vehicle routing problem with soft time windows and a single unit capacity. The goal is to serve all customers such that the quadratic sum of delays is minimized and each vehicle operates within its battery bounds. To solve this problem, we formulate an MIQP and present an expanded formulation based on a layered graph. For this layered graph we derive two solution approaches based on relaxations, which use less nodes and arcs. The first, Iterative Refinement, always solves the current relaxation to optimality and refines the graph if the solution is not feasible for the expanded formulation. This is repeated until a proven optimal solution is found. The second, Branch and Refine, integrates the graph refinement into a branch and bound framework avoiding restarts. Computational experiments performed on modified Solomon instances demonstrate the advantage of using our solution approaches and show that Branch and Refine outperforms Iterative Refinement in all studied parameter configurations. N2 - In den letzten Jahren erreichte das Paketvolumen Rekordhöhen. Die Logistikbranche sucht nach neuen innovativen Konzepten, um Schritt zu halten. Für dicht besiedelte Gebiete sind Lieferroboter eine vielversprechende Alternative zum konventionellen LKW-Transport. Diese elektrischen Roboter fahren autonom auf Bürgersteigen und liefern Waren wie Expresspakete, Medikamente oder Mahlzeiten aus. Der begrenzte Laderaum und die begrenzte Batteriekapazität dieser Fahrzeuge erfordern nach jedem Kunden einen Depotbesuch. Das Problem kann als Routingproblem für Elektrofahrzeuge mit weichen Zeitfenstern und einer Kapazität von einer einzelnen Einheit formuliert werden. Ziel ist es, alle Kunden so zu bedienen, dass die quadratische Summe der Verspätungen minimiert wird und jede Fahrzeugroute innerhalb der Batterieladungsgrenzen liegt. Um dieses Problem zu lösen, formulieren wir einen MIQP und präsentieren eine erweiterte Formulierung basierend auf einem geschichteten Graphen. Für diesen geschichtete Graphen leiten wir zwei Lösungsansätze ab, die auf Relaxationen basieren und weniger Knoten und Bögen verwenden. Der erste, iterative Verfeinerung, löst die aktuelle Relaxation immer optimal und verfeinert den Graphen, wenn die erweiterte Formulierung keine zulässige Lösung enthält. Dies wird wiederholt, bis eine optimale Lösung gefunden ist. Die zweite Option, Verzweigen und Verfeinern, integriert die Graphenverfeinerung in einen Verzweige und Beschränke Rahmen, um Neustarts zu vermeiden. Computerexperimente, die an modifizierten Solomon-Instanzen durchgeführt wurden, zeigen den Vorteil der Verwendung unserer Lösungsansätze und zeigen, dass Verzweigen und Verfeinern die iterative Verfeinerung in allen untersuchten Parameterkonfigurationen übertrifft. T3 - Cottbus Mathematical Preprints - 17, 2021 KW - Delivery robots KW - Electric vehicle routing problem KW - Graph refinement KW - Layered graphs KW - Partial recharging KW - Lieferroboter KW - Streckenplanung für elektrische Fahrzeuge KW - Graphenverfeinerung KW - Geschichtete Graphen KW - Partielles Aufladen KW - Mobiler Roboter KW - Tourenplanung KW - Optimierung Y1 - 2021 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:co1-opus4-54931 SN - 2627-6100 ER - TY - RPRT A1 - Ocloo, Valentina E. A1 - Fügenschuh, Armin A1 - Pamen, Olivier M. ED - Fügenschuh, Armin T1 - A new mathematical model for a 3D container packing problem N2 - Wir betrachten das Problem der Einzelcontainerpackung eines Unternehmens, das seine Kunden bedienen muss, indem es zuerst die Produkte in Kartons legt und diese dann in einen Container lädt. Für dieses Problem entwickeln und lösen wir ein lineares gemischt-ganzzahliges Modell. Unser Modell berücksichtigt geometrische Randbedingungen, beispielsweise Überlappungsverbote, Orientierungs-Bedingungen und Randbedingungen für die relative Positionierung der Kartons. Wir betrachten auch die Erweiterung des Modells durch die Integration der Schwerpunktsabweichung der Packung vom Containermittelpunkt. Das Modell wurde an einer großen Anzahl von realen Instanzen getestet, die bis zu 41 Kartons enthalten. In den meisten Fällen wurden optimale Lösungen erzielt bzw. nah-optimale Lösungen mit beweisbar kleiner Optimalitätslücke. N2 - We address the single container packing problem of a company that has to serve its customers by first placing the products in boxes and then loading the boxes into a container. We approach the problem by developing and solving mixed-integer linear models. Our models consider geometric constraints that feature non-overlapping constraints, box orientation constraints, dimensionality constraints, relative packing position constraints, and linearity constraints. We also develop an extension of the models by integrating load balance and the deviation of the center of gravity. We tested the models on a broad set of real instances involving up to 41 boxes and obtained optimal solutions in most cases and very small gaps when optimality could not be proven. T3 - Cottbus Mathematical Preprints - 12, 2020 KW - Container packing problem KW - Mixed-integer programming KW - Box orientation KW - Non-overlapping KW - Center of gravity deviation KW - Optimierungsproblem KW - Container KW - Lineare Optimierung KW - Logistik Y1 - 2020 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:co1-opus4-50880 SN - 2627-6100 ER - TY - RPRT A1 - Gnegel, Fabian A1 - Fügenschuh, Armin ED - Fügenschuh, Armin T1 - Branch-and-refine for solving time-dependent problems T1 - Branch-and-Refine zur Lösung zeitabhängiger Probleme N2 - Einer der Standardansätze zur Lösung zeitabhängiger diskreter Optimierungsprobleme, wie z.B. das Problem des Handlungsreisenden mit Zeitfenstern oder das Kürzeste Wege Problem mit Zeitfenstern, ist die Herleitung einer sogenannten zeitindizierten Formulierung. Wenn dem Problem eine Struktur zu Grunde liegt, die durch einen Graphen beschrieben werden kann, basiert die zeitindizierte Formulierung normalerweise auf einem anderen, erweiterten Graphen, der in der Literatur als zeitexpandierter Graph bezeichnet wird. Der zeitexpandierte Graph kann oft so generiert werden, dass alle Zeitbeschränkungen bereits aufgrund seiner Topologie erfüllt sind und somit Algorithmen für die entsprechende zeitunabhängige Variante angewendet werden können. Der Nachteil dieses Ansatzes ist, dass die Mengen der Ecken und Bögen des zeitexpandierten Graphen viel größer sind als die des ursprünglichen Graphen. In neueren Arbeiten hat sich jedoch gezeigt, dass für viele praktische Anwendungen eine partielle Expandierung des Graphen, die möglicherweise zeitunmögliche Pfade zulässt, oft ausreicht, um eine beweisbar optimale Lösung zu finden. Diese Ansätze verfeinern iterativ den ursprünglichen Graphen und lösen in jeder Iteration eine Relaxierung der zeitexpandierten Formulierung. Wenn die Lösung der aktuellen Relaxation alle Zeitbeschränkungen erfüllt, kann daraus eine optimale Lösung abgeleitet werden, und der Algorithmus terminiert. In dieser Arbeit stellen wir neue Ideen vor, die das Übertragen von Informationen über die optimale Lösung eines gröberen Graphen zu einem verfeinerten Graphen ermöglichen und zeigen, wie diese in Algorithmen verwendet werden können. Genauer gesagt stellen wir einen neuen Algorithmus zur Lösung von MILP-Formulierungen (Mixed Integer Linear Program) von zeitabhängigen Problemen vor, der es ermöglicht, die Graphenverfeinerung während der Untersuchung des Branch-and-Bound Baums durchzuführen, anstatt jedes Mal neu zu starten, wenn die optimale Lösung sich als nicht zulässig herausgestellt hat. Um die praktische Relevanz dieses Algorithmus zu demonstrieren, präsentieren wir Ergebnisse von numerische Experimenten seiner Anwendung auf das Kürzeste Wege Problem mit Zeitfenstern und das Problem des Handlungsreisenden mit Zeitfenstern. N2 - One of the standard approaches for solving time-dependent discrete optimization problems, such as the travelling salesman problem with time-windows or the shortest path 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 is time feasible an optimal solution can be derived from it and the algorithm terminates. In this work we 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, which are based on graph refinement. More precisely we present a new algorithm for solving Mixed Integer Linear Program (MILP) formulations of time-dependent problems that allows for the graph refinement to be carried out during the exploration of the branch-and-bound tree instead of restarting whenever the optimal solution was found to be infeasible. For demonstrating the practical relevance of this algorithm we present numerical results on its application to the shortest path problem with time-windows and the traveling salesman problem with time-windows. T3 - Cottbus Mathematical Preprints - 13, 2020 KW - Graphenverfeinerung KW - Branch-and-Bound KW - Kürzeste Wege Problem mit Zeitfenstern KW - Problem des Handlungsreisenden mit Zeitfenstern KW - Graph refinement KW - Branch-and-bound KW - Shortest path problem with time-windows KW - Travelling salesman problem with time-windows KW - Branch-and-Bound-Methode KW - Kürzester-Weg-Problem KW - Travelling-salesman-Problem Y1 - 2020 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:co1-opus4-51995 SN - 2627-6100 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 - JOUR A1 - Gnegel, Fabian A1 - Schaudt, Stefan A1 - Clausen, Uwe A1 - Fügenschuh, Armin T1 - A graph-refinement algorithm to minimize squared delivery delays using parcel robots JF - Mathematics N2 - In recent years, parcel volumes have reached record highs, prompting the logistics industry to explore innovative solutions to meet growing demand. In densely populated areas, delivery robots offer a promising alternative to traditional truck-based delivery systems. These autonomous electric robots operate on sidewalks and deliver time-sensitive goods, such as express parcels, medicine and meals. However, their limited cargo capacity and battery life require a return to a depot after each delivery. This challenge can be modeled as an electric vehicle-routing problem with soft time windows and single-unit capacity constraints. The objective is to serve all customers while minimizing the quadratic sum of delivery delays and ensuring each vehicle operates within its battery limitations. To address this problem, we propose a mixed-integer quadratic programming model and introduce an enhanced formulation using a layered graph structure. For this layered graph, we present two solution approaches based on relaxations that reduce the number of nodes and arcs compared to the expanded formulation. The first approach, Iterative Refinement, solves the current relaxation to optimality and refines the graph when the solution is infeasible for the expanded formulation. This process continues until a proven optimal solution is obtained. The second approach, Branch and Refine, integrates graph refinement into a branch-and-bound framework, eliminating the need for restarts. Computational experiments on modified Solomon instances demonstrate the effectiveness of our solution approaches, with Branch and Refine consistently outperforming Iterative Refinement across all tested parameter configurations. KW - Integer programming KW - Layered graph refinement KW - Delivery robots KW - Electric vehicle-routing problem KW - Partial recharging Y1 - 2024 U6 - https://doi.org/10.3390/math12203201 SN - 2227-7390 VL - 12 PB - MDPI CY - Basel 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 -