@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} } @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{BaehrBuhlRadowetal.2019, type = {Working Paper}, author = {B{\"a}hr, Martin and Buhl, Johannes and Radow, Georg and Schmidt, Johannes and Bambach, Markus and Breuß, Michael and F{\"u}genschuh, Armin}, title = {Stable honeycomb structures and temperature based trajectory optimization for wire-arc additive manufacturing}, editor = {F{\"u}genschuh, Armin}, issn = {2627-6100}, doi = {10.26127/BTUOpen-5079}, url = {http://nbn-resolving.de/urn:nbn:de:kobv:co1-opus4-50796}, year = {2019}, abstract = {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.}, subject = {Eikonal equation; Centroidal Voronoi tessellation; Additive manufacturing; Heat transmission; Mixed-integer linear programming; Geometric optimization; Additive Fertigung; Gemischt-ganzzahlige Programmierung; Geometrische Optimierung; Eikonal-Gleichung; Zentrierte Voronoi-Parkettierung; W{\"a}rmeleitung; Rapid Prototyping ; Eikonal; Ganzzahlige Optimierung; Geometrische Optimierung; W{\"a}rmeleitung}, 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} } @phdthesis{Schmidt2024, author = {Schmidt, Johannes}, title = {The mission and flight planning problem : a physics-based MILP routing approach for an inhomogeneous fleet of unmanned aerial vehicles with collision-free trajectories}, doi = {10.26127/BTUOpen-6841}, url = {http://nbn-resolving.de/urn:nbn:de:kobv:co1-opus4-68415}, school = {BTU Cottbus - Senftenberg}, year = {2024}, abstract = {Today, drones are a helpful addition or even an efficient alternative in many areas due to their simple control and low operating costs compared to manned aircraft. Often, it is preferred that the UAV performs its mission autonomously. Thus, next to the operative control, the strategic planning of such missions plays an important role for their efficiency. Furthermore, it is also of interest for air traffic management to integrate UAVs into the airspace of manned aviation. At a strategic level, many use cases can be represented by a set of waypoints. Maybe not all of them can be visited within a given time horizon or only by drones with special hardware. Thus, before the start of a mission, each involved UAV must be assigned the waypoints to be processed and its flight trajectory must be planned to guarantee a safe and efficient process. These two sub-problems of the planning process influence each other and cannot be treated separately. In this paper, we address this problem by introducing the Mission and Flight Planning Problem (MFPP). Therein, the assignment of the UAVs to the given waypoints is combined with the computation of exact flight trajectories in a mixed-integer linear optimization problem (MILP). It is based on a team orienteering problem with time windows, in which the positions of all UAVs are calculated using discretized Newton's laws of motion. Concerning the flight dynamics, design-related parameters and mass, speed, and altitude dependencies of the performance data of each drone are included in the model. Each drone is controlled by radio and must not leave the range of its control station. There may be obstacles within the mission area. The UAVs must also maintain safety distances from each other to avoid collisions. In addition to the model, we discuss different types of valid inequalities. We present a new inter-sample avoidance approach based on decomposing the mission area into several sub-areas and their identification with binary vectors. The construction of an integer polyhedron containing these binary vectors is given and we investigate its structure. In addition, different possibilities for implementing the new constraints are discussed. For two special types of MFPP instances, we present adapted solution methods that exploit their respective structure, i.e., a sequential solution method and a column generation approach. The performance of the presented model is investigated in detailed computational studies and we discuss its essential properties in several examples.}, subject = {Mixed-integer linear programming; Trajectory optimization; Inter-sample avoidance; Unmanned aerial vehicles; Gemischt-ganzzahlige lineare Programmierung; Trajektorienoptimierung; Kollisionsvermeidung zwischen Zeitschritten; Unbemannte Luftfahrzeuge; Flugk{\"o}rper; Optimierungsproblem; Strategische Planung; Kollisionsschutz; Trajektorie }, language = {en} } @techreport{SchmidtFuegenschuh2021, type = {Working Paper}, author = {Schmidt, Johannes and F{\"u}genschuh, Armin}, title = {A two-time-level model for mission and flight planning of an inhomogeneous fleet of unmanned aerial vehicles}, editor = {F{\"u}genschuh, Armin}, doi = {10.26127/BTUOpen-5461}, url = {http://nbn-resolving.de/urn:nbn:de:kobv:co1-opus4-54619}, year = {2021}, abstract = {We consider the mission and flight planning problem for an inhomogeneous fleet of unmanned aerial vehicles (UAVs). Therein, the mission planning problem of assigning targets to a fleet of UAVs and the flight planning problem of finding optimal flight trajectories between a given set of waypoints are combined into one model and solved simultaneously. Thus, trajectories of an inhomogeneous fleet of UAVs have to be specified such that the sum of waypoint-related scores is maximized, considering technical and environmental constraints. Several aspects of an existing basic model are expanded to achieve a more detailed solution. A two-level time grid approach is presented to smooth the computed trajectories. The three-dimensional mission area can contain convex-shaped restricted airspaces and convex subareas where wind affects the flight trajectories. Furthermore, the flight dynamics are related to the mass change, due to fuel consumption, and the operating range of every UAV is altitude-dependent. A class of benchmark instances for collision avoidance is adapted and expanded to fit our model and we prove an upper bound on its objective value. Finally, the presented features and results are tested and discussed on several test instances using GUROBI as a state-of-the-art numerical solver.}, subject = {Mixed-integer nonlinear programming; Mission Planning; Inhomogeneous Fleet; Time Windows; Linearization methods; Gemischt-ganzzahlige nichtlineare Programming; Missionsplanung; Inhomogene Flotte; Zeitfenster; Linearisierungsmethoden; Nichtlineare Optimierung; Tourenplanung; Flugk{\"o}rper}, 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{FuegenschuhMuellenstedtSchmidt2019, author = {F{\"u}genschuh, Armin and M{\"u}llenstedt, Daniel and Schmidt, Johannes}, title = {Mission planning for unmanned aerial vehicles}, editor = {F{\"u}genschuh, Armin}, issn = {2627-6100}, doi = {10.26127/BTUOpen-4828}, url = {http://nbn-resolving.de/urn:nbn:de:kobv:co1-opus4-48285}, year = {2019}, abstract = {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.}, subject = {Mixed-integer nonlinear programming; Trajectory planning; Unmanned aerial vehicles; Linear approximation; Flugk{\"o}rper; Tourenplanung; Optimierung}, 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{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} }