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 -