@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} } @techreport{SchmidtFuegenschuhBoeschow2025, type = {Working Paper}, author = {Schmidt, Johannes and F{\"u}genschuh, Armin and B{\"o}schow, Moritz M.}, title = {Sports league scheduling with minitournaments}, doi = {10.26127/BTUOpen-7029}, url = {http://nbn-resolving.de/urn:nbn:de:kobv:co1-opus4-70293}, year = {2025}, abstract = {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.}, subject = {Discrete optimization; Linear optimization; Orbital shrinking; Sport scheduling; Diskrete Optimierung; Lineare Optimierung; Sportligenplanung; Lineare Optimierung; Diskrete Optimierung; Wettkampfklasse; Amateursport; Jugendsport; Spielplan }, language = {en} } @techreport{ZellFuegenschuh2025, type = {Working Paper}, author = {Zell, Sascha and F{\"u}genschuh, Armin}, title = {Optimizing autonomous unmanned aircraft system deployment locations for enhanced wildfire detection and monitoring}, doi = {10.26127/BTUOpen-6942}, url = {http://nbn-resolving.de/urn:nbn:de:kobv:co1-opus4-69422}, year = {2025}, abstract = {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.}, subject = {Mixed-lnteger linear programming; Unmanned aircraft systems; Micro air vehicles; Autonomous wildfire monitoring; Location-allocation optimization; Gemischt-ganzzahlige Programmierung; Drohnen; Drohnenhangar; Standortproblem; Autonome Waldbrandbek{\"a}mpfung; Waldbrand; {\"U}berwachung; Drohne (Flugk{\"o}rper); Autonomes System; Standortproblem; Lineare Optimierung}, language = {en} } @article{GnegelSchaudtClausenetal.2024, author = {Gnegel, Fabian and Schaudt, Stefan and Clausen, Uwe and F{\"u}genschuh, Armin}, title = {A graph-refinement algorithm to minimize squared delivery delays using parcel robots}, series = {Mathematics}, volume = {12}, journal = {Mathematics}, publisher = {MDPI}, address = {Basel}, issn = {2227-7390}, doi = {10.3390/math12203201}, year = {2024}, abstract = {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.}, subject = {Integer programming; Layered graph refinement; Delivery robots; Electric vehicle-routing problem; Partial recharging}, language = {en} } @techreport{ZellSchneidereitFuegenschuhetal.2024, type = {Working Paper}, author = {Zell, Sascha and Schneidereit, Toni and F{\"u}genschuh, Armin and Breuß, Michael}, title = {Advanced search and rescue operations for drowning swimmers using autonomous unmanned aircraft systems : location optimization, flight trajectory planning and image-based localization}, doi = {10.26127/BTUOpen-6866}, url = {http://nbn-resolving.de/urn:nbn:de:kobv:co1-opus4-68669}, year = {2024}, abstract = {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.}, subject = {Unmanned Aerial Vehicle; Unmanned Aircraft System; Water Rescue; Mixed-Integer Linear Programming; You Only Look Once; Drohne; Drohnenhangar; Wasserrettung; Gemischt-ganzzahlige Programmierung; Standortoptimierung; Drohne ; Wasserrettung; Lineare Optimierung}, language = {en} } @techreport{SchmidtFuegenschuh2023, type = {Working Paper}, author = {Schmidt, Johannes and F{\"u}genschuh, Armin}, title = {Trajectory optimization for arbitrary layered geometries in wire-arc additive manufacturing}, doi = {10.26127/BTUOpen-6267}, url = {http://nbn-resolving.de/urn:nbn:de:kobv:co1-opus4-62678}, year = {2023}, abstract = {In wire-arc additive manufacturing, a wire is molten by an electrical or laser arc and deposited droplet-by-droplet to construct the desired workpiece, given as a set of two-dimensional layers. The weld source can move freely over a substrate plate, processing each layer, but there is also the possibility of moving without welding. A primary reason for stress inside the material is the large thermal gradient caused by the weld source, resulting in lower product quality. Thus, it is desirable to control the temperature of the workpiece during the process. One way of its optimization is the trajectory of the weld source. We consider the problem of finding a trajectory of the moving weld source for a single layer of an arbitrary workpiece that maximizes the quality of the part and derive a novel mixed-integer PDE-constrained model, including the calculation of a detailed temperature distribution measuring the overall quality. The resulting optimization problem is linearized and solved using the state-of-the-art numerical solver IBM CPLEX. Its performance is examined by several computational studies.}, subject = {Mixed-integer programming; Trajektorie ; Partielle Differentialgleichung; Finite-Volumen-Methode; W{\"a}rmeleitung; Wire are additive manufacturing; Trajectory planning; Partial differential equations; Finite element method; Heat conduction; Gemischt-ganzzahlige Programmierung; Additive Draht-Lichtbogen-Fertigung,; Trajektorienplanung; Partielle Differenzialgleichungen; Finite-Elemente-Methode; W{\"a}rmeleitung}, language = {en} } @techreport{BeisegelBuhlIsraretal.2021, type = {Working Paper}, author = {Beisegel, Jesse and Buhl, Johannes and Israr, Rameez and Schmidt, Johannes and Bambach, Markus and F{\"u}genschuh, Armin}, title = {Mixed-integer programming for additive manufacturing}, doi = {10.26127/BTUOpen-5731}, url = {http://nbn-resolving.de/urn:nbn:de:kobv:co1-opus4-57317}, year = {2021}, abstract = {Since the beginning of its development in the 1950s, mixed integer programming (MIP) has been used for a variety of practical application problems, such as sequence optimization. Exact solution techniques for MIPs, most prominently branch-and-cut techniques, have the advantage (compared to heuristics such as genetic algorithms) that they can generate solutions with optimality certificates. The novel process of additive manufacturing opens up a further perspective for their use. With the two common techniques, Wire Arc Additive Manufacturing (WAAM) and Laser Powder Bed Fusion (LPBD), the sequence in which a given component geometry must be manufactured can be planned. In particular, the heat transfer within the component must be taken into account here, since excessive temperature gradients can lead to internal stresses and warpage after cooling. In order to integrate the temperature, heat transfer models (heat conduction, heat radiation) are integrated into a sequencing model. This leads to the problem class of MIPDECO: MIPs with partial differential equations (PDEs) as further constraints. We present these model approaches for both manufacturing techniques and carry out test calculations for sample geometries in order to demonstrate the feasibility of the approach.}, subject = {Wire arc additive manufacturing; Laser powder bed fusion; Mixed-integer programming; Partial differential equations; Finite element method; Additive Fertigung mit Drahtlichtbogen; Laser-Pulverbett-Schmelzen; Gemischt-ganzzahlige Programmierung; Partielle Differenzialgleichungen; Finite-Elemente-Methode; Rapid Prototyping ; Ganzzahlige Optimierung; Finite-Elemente-Methode; Partielle Differentialgleichung}, 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{SchmidtFuegenschuh2021, type = {Working Paper}, author = {Schmidt, Johannes and F{\"u}genschuh, Armin}, title = {Planning inspection flights with an inhomogeneous fleet of micro aerial vehicles}, doi = {10.26127/BTUOpen-5656}, url = {http://nbn-resolving.de/urn:nbn:de:kobv:co1-opus4-56569}, year = {2021}, abstract = {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.}, subject = {Mixed integer linear programming; Inspection path planning; Trajectory planning; Micro aerial vehicles; Gemischt-ganzzahlige Programmierung; Inspektionspfadplanung; Trajektorienplanung; Kleinstdrohnen; Ganzzahlige Optimierung; Tourenplanung; Drohne }, language = {en} } @techreport{SchmidtBuhlFuegenschuh2021, type = {Working Paper}, author = {Schmidt, Johannes and Buhl, Johannes and F{\"u}genschuh, Armin}, title = {A finite element approach for trajectory optimization in Wire-Arc Additive Manufacturing}, editor = {F{\"u}genschuh, Armin}, doi = {10.26127/BTUOpen-5575}, url = {http://nbn-resolving.de/urn:nbn:de:kobv:co1-opus4-55753}, year = {2021}, abstract = {In wire-arc additive manufacturing (WAAM), the desired workpiece is built layerwise by a moving heat source depositing droplets of molten wire on a substrate plate. To reduce material accumulations, the trajectory of the weld source should be continuous, but transit moves without welding, called deadheading, are possible. The enormous heat of the weld source causes large temperature gradients, leading to a strain distribution in the welded material which can lead even to cracks. In summary, it can be concluded that the temperature gradient reduce the quality of the workpiece. We consider the problem of finding a trajectory of the weld source with minimal temperature deviation from a given target temperature for one layer of a workpiece with welding segments broader than the width of the weld pool. The temperature distribution is modeled using the finite element method. We formulate this problem as a mixed-integer linear programming model and demonstrate its solvability by a standard mixed-integer solver.}, subject = {Additive manufacturing; Heat equation; Path optimization; Finite element method; Mixed-integer linear programming; Additive Fertigung; Pfadoptimierung; W{\"a}rmeleitungsgleichung; Finite-Elemente-Methode; Gemischt-ganzzahlige lineare Programmierung; Rapid Prototyping ; W{\"a}rmeleitungsgleichung; Bahnplanung; Ganzzahlige lineare Optimierung; Finite-Elemente-Methode}, language = {en} }