Refine
Document Type
- Working paper (11)
- Bachelor thesis (7)
- Report (6)
- Doctoral thesis (3)
- Master thesis (2)
Has Fulltext
- yes (29)
Is part of the Bibliography
- no (29)
Keywords
- Ganzzahlige Optimierung (8)
- Mixed-integer programming (6)
- Gemischt-ganzzahlige Programmierung (5)
- Tourenplanung (5)
- Trajectory planning (5)
- Travelling-salesman-Problem (5)
- Finite-Elemente-Methode (4)
- Mixed-integer linear programming (4)
- Trajektorienplanung (4)
- Bahnplanung (3)
- Finite element method (3)
- Gemischt-ganzzahlige Optimierung (3)
- Gemischt-ganzzahlige lineare Programmierung (3)
- Geoinformationssystem (3)
- Graph refinement (3)
- Kürzester-Weg-Problem (3)
- Nichtlineare Optimierung (3)
- Optimierung (3)
- Partial differential equations (3)
- Rapid Prototyping <Fertigung> (3)
- Additive Fertigung (2)
- Additive manufacturing (2)
- Artificial neuronal networks (2)
- Bilderkennung (2)
- Branch-and-Bound-Methode (2)
- Flugkörper (2)
- Ganzzahlige lineare Optimierung (2)
- Graphenverfeinerung (2)
- Heuristics (2)
- Heuristik (2)
- Image recognition (2)
- Kürzeste Wege (2)
- Lineare Optimierung (2)
- Logistik (2)
- Mixed integer linear programming (2)
- Mixed-integer nonlinear programming (2)
- Moving targets (2)
- Multi-criteria optimization (Pareto frontier) (2)
- Neuronales Netz (2)
- Nonlinear optimization (2)
- Operational Research (2)
- Optimierungsproblem (2)
- Partielle Differentialgleichung (2)
- Partielle Differenzialgleichungen (2)
- Simulation (2)
- Wärmeleitung (2)
- 5G (1)
- 5G radio networks (1)
- 5G-Funknetze (1)
- AMPL (1)
- Additive Draht-Lichtbogen-Fertigung, (1)
- Additive Fertigung mit Drahtlichtbogen (1)
- Agent-based simulation (1)
- Agentenbasiertes Simulationsmodell (1)
- Antenna site optimization (1)
- Antenne (1)
- Antennenstandort-Optimierung (1)
- Bestandsmanagement (1)
- Bewegliche Ziele (1)
- Bi-criteria optimization (1)
- Bikriterielle Optimierung (1)
- Bildklassifizierung (1)
- Box orientation (1)
- Branch and bound (1)
- Branch-and-Bound (1)
- Branch-and-bound (1)
- Center of gravity deviation (1)
- Centroidal Voronoi tessellation (1)
- Combinatorial optimization (1)
- Competitive analysis (1)
- Container (1)
- Container packing problem (1)
- Convection-diffusion equation (1)
- Cottbus (1)
- Cutting plane method (1)
- Deep learning (1)
- Delivery robots (1)
- Discrete optimization (1)
- Diskrete Optimierung (1)
- Distribution function (1)
- Drohne <Flugkörper> (1)
- Dynamic Graph Expansion (1)
- Dynamic traveling salesmen problem (1)
- Efficiency (1)
- Effizienz (1)
- Eikonal (1)
- Eikonal equation (1)
- Eikonal-Gleichung (1)
- Electric vehicle routing problem (1)
- Emergency medical service system (1)
- Expandierender Graph (1)
- Fertigungsprogrammplanung (1)
- Finite-Volumen-Methode (1)
- Finite-element methods (1)
- Funknetz (1)
- Ganzzahlige Programmierung (1)
- Gemischt-ganzzahlige lineare Optimierung (1)
- Gemischt-ganzzahlige nichtlineare Programming (1)
- Geographic information system (1)
- Geographische Informationssysteme (GIS) (1)
- Geoinformationssysteme (1)
- Geometric optimization (1)
- Geometrische Optimierung (1)
- Geschichtete Graphen (1)
- Global optimal control (1)
- Globale Optimalsteuerung (1)
- Graph construction (1)
- Graphen-Aufbau (1)
- Handlungsreisendenproblem (1)
- Heat conduction (1)
- Heat equation (1)
- Heat transmission (1)
- Helicopter (1)
- Heuristiken (1)
- Hubschrauber (1)
- Image classification (1)
- Inhomogene Flotte (1)
- Inhomogeneous Fleet (1)
- Inspection path planning (1)
- Inspektionspfadplanung (1)
- Instandhaltung (1)
- Instandhaltungsplanung (1)
- Integer linear programming (1)
- Integer programming (1)
- Kleinstdrohnen (1)
- Kombinatorische Optimierung (1)
- Kompetitivitätsanalyse (1)
- Konvektions-Diffusions-Gleichung (1)
- Konvektions-Diffusionsgleichung (1)
- Künstliche Neuronale Netze (1)
- Künstliche neuronale Netze (1)
- Kürzeste Wege Problem mit Zeitfenstern (1)
- Lagermanagement (1)
- Laser powder bed fusion (1)
- Laser-Pulverbett-Schmelzen (1)
- Layered graphs (1)
- Lieferroboter (1)
- Linear approximation (1)
- Linearisierungsmethoden (1)
- Linearization methods (1)
- Logisitcs (1)
- Maintenance (1)
- Mathematische Modellierung (1)
- Mehrdepotproblem (1)
- Mehrzieloptimierung (Pareto-Front) (1)
- Micro aerial vehicles (1)
- Mission Planning (1)
- Missionsplanung (1)
- Mixed Integer Linear Programming (1)
- Mixed-Integer Programming (1)
- Mixed-integer linear optimization (1)
- Mixed-integer optimization (1)
- Mobiler Roboter (1)
- Modeling (1)
- Modeling of time (1)
- Modellierung (1)
- Modellierung von Zeit (1)
- Multi-static sonar (1)
- Multikriterielle Optimierung (1)
- Multikriterielle Optimierung (Pareto-Front) (1)
- Multiple traveling salesperson problem (1)
- Multiples Handlungsreisendenproblem (1)
- Multistatisches Sonar (1)
- Mustererkennung (1)
- Network planning (1)
- Netzplanung (1)
- Non-overlapping (1)
- Online algorithms (1)
- Online-Algorithmen (1)
- Operational research (1)
- Operations Research (1)
- Operations research (1)
- Optimal routes (1)
- Optimale Kontrolle (1)
- Optimale Routen (1)
- Optimization of Public Transportation (1)
- Partial Set Covering Problem (1)
- Partial recharging (1)
- Partial set covering problem (1)
- Partielle Differentialgleichungen (1)
- Partielles Aufladen (1)
- Path optimization (1)
- Pfadoptimierung (1)
- Planning (1)
- Planung (1)
- Problem des Handlungsreisenden mit Zeitfenstern (1)
- Production planning (1)
- Quadratic constraints (1)
- Quadratische Nebenbedingungen (1)
- Re-balancing problem (1)
- Rescue chain (1)
- Rettungsdienst (1)
- Rettungskette (1)
- Rettungswesen (1)
- Routing (1)
- Scenario generation (1)
- Schnittebenenverfahren (1)
- School Bell Scheduling (1)
- School time table planning (1)
- Schülertransport (1)
- Second-order cone programming (1)
- Shortest path (1)
- Shortest path problem with time-windows (1)
- Shortest paths (1)
- Simulated annealing algorithm (1)
- Simulated-Annealing-Algorithmus (1)
- Statistics (1)
- Statistik (1)
- Stochastische Optimierung (1)
- Streckenplanung für elektrische Fahrzeuge (1)
- Stundenplanerstellung (1)
- Szenario-Erzeugung (1)
- Tiefes Lernen (1)
- Time Windows (1)
- Time-Dependent Airplane Routing (1)
- Time-dependent airplane routing (1)
- Time-relaxation (1)
- Topography (1)
- Tourenplanung von E-Fahrzeugen (1)
- Trajektorie <Mathematik> (1)
- Traveling Salesman Problem (1)
- Travelling salesman problem with time-windows (1)
- Two-stage stochastic optimization (1)
- Umverteilungsproblem (1)
- Uncertainty (1)
- Unmanned aerial vehicles (1)
- Unsicherheit (1)
- Unternehmensforschung (1)
- Vehicle Routing Problem (1)
- Verfeinerung von Graphen (1)
- Verkehrsplanung (1)
- Verteilungsfunktion (1)
- Warehouse management (1)
- Wire arc additive manufacturing (1)
- Wire are additive manufacturing (1)
- Wärmeleitungsgleichung (1)
- Zeitabhängige Flugroutenplanung (1)
- Zeitfenster (1)
- Zentrierte Voronoi-Parkettierung (1)
- Zweistufige stochastische Optimierung (1)
Institute
- FG Ingenieurmathematik und Numerik der Optimierung (29) (remove)
In dieser Bachelorarbeit wird das Problem der Auswahl von Antennenstandorten für eine maximale räumliche Abdeckung in 5G-Funknetzen untersucht. Das Hauptziel besteht darin, eine effiziente Lösung für dieses kombinatorische Optimierungsproblem zu finden, indem es als Partial Set Covering Problem formuliert und gelöst wird. Die Arbeit gliedert sich in zwei Teile: Der erste Teil bietet eine Einführung in die mathematischen Grundlagen des Partial Set Covering Problems, einschließlich Definitionen, Formulierung und Lösungsverfahren. Im zweiten Teil wird ein praktischer Ansatz zur Lösung dieses Problems präsentiert, wobei realen Instanzen für die Auswahl von Antennenstandorten analysiert werden. Hierbei werden zwei Hauptfragen untersucht: 1) Wie kann die gegebene Instanz in ein Partial Set Covering Problem umformuliert werden? 2) Wie kann dieses Problem mithilfe eines heuristischen Verfahrens, insbesondere des Simulated-Annealing-Algorithmus, gelöst werden? Die Ergebnisse dieser Arbeit tragen dazu bei, fundierte Entscheidungen über den Aufbau von 5G-Netzen zu treffen und die Netzwerkabdeckung unter Berücksichtigung von Nebenbedingungen zu maximieren.
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.
One of the standard approaches for solving discrete optimization problems which include the aspect of time, such as the traveling salesman 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 allows for a feasible schedule, an optimal solution can be derived from it and the algorithm terminates.
In this work, we first 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. More precisely, we present two general algorithms for solving Mixed Integer Linear Program formulations which we call iterative refinement and branch-and-refine. Iterative refinement basically is solving relaxations of the problem until a feasible solution to the original problem is found. Branch-and-refine is a kind of branch-and-bound algorithm that allows for the graph refinement to be carried out during the exploration of the branch-and-bound tree. For demonstrating the practical relevance of these algorithms, we not only study them in the context of academic examples but also apply them to two real-world problems. The first is a problem from the literature, where small passenger air-crafts have to be routed and scheduled to serve flight requests while fulfilling a variety of conditions on, for example, fuel consumption, weight, and detours. We show here that refinement algorithms can be used to improve the best known results from the literature. The second problem we consider is the task of optimally scheduling deliveries and charging times of delivery robots such that delays are minimized. In this case, we show that refinement algorithms perform better than a direct solution approach making use of state-of-the-art solvers.
Military installations and objects in out-of-area missions, e.g., an air base or a field camp, must be protected from incoming hostile rockets, artillery or mortar fire. Lasers as directed energy weapons are able to destroy those targets within seconds. Generally, the laser is assigned to a target, that applies the smallest movement of its direction unit to aim at it. The goal is to minimize the damage and thus, to destroy all incoming targets. We model the problem as a multiple traveling salesperson problem with moving targets, where the salespersons correspond to the lasers. The targets move over time on continuous trajectories. Additionally, each target is given a visibility time window. We investigate if exact methods are able to solve real-world instances in reasonable time. On that account, we address the problem from two sides, offline and online.
One essential aspect studied in this work is to find an appropriate formulation to model the time requirements. We present five different modeling approaches, where the time aspect is handled in different ways: discrete, continuous, directly or via sub-problems. Our randomly generated test instances consider 6 to 20 targets and 1 to 6 salespersons. Computational experiments with linear and non-linear trajectories are performed. The best model can solve instances up to 10 targets within 3 seconds. For online experiments the two familiar strategies REPLAN and IGNORE are adapted to our problem.
Another important aspect of this work is our contribution to competitive analysis, a method to evaluate the quality of online algorithms. Here, we restrict the problem considered so far to one salesperson and address the online moving targets traveling salesperson problem on the real line. We prove a lower bound for the competitive ratio regarding this problem. Then, we develop an online algorithm and present its competitive ratio with the corresponding proof. The competitive ratio depends on the speed ratio of salespersons and targets and outperforms a comparable online algorithm from the literature for certain speed ratios. The theoretical results obtained for the online moving target traveling salesperson problem on the real line are new in this research area.
Agentenbasierte Modellierung und Simulation der Rettungskette : eine Fallstudie in der Lausitz
(2022)
Ein funktionierender Rettungsdienst ist für die Gesellschaft von zentraler Bedeutung, da in medizinischen Notsituationen die Gesundheit eines Verunfallten von der Qualität der praäklinischen medizinischen Versorgung abhängt. Dabei steht man vor immer neuen Herausforderungen des sozioökonomischen Wandels und technischen Fortschritts, die neue Ansätze zur Systemoptimierung erfordern. Diese Arbeit beinhaltet eine Literaturübersicht über Planungsprobleme, sowie eine Klassifizierung von Emergency Medical Service (EMS) Systemen. Ein agentenbasiertes Simulationsmodell für ein notarztbasiertes EMS-System wird vorgestellt und auf die Rettungskette eines städtischen Gebietes Cottbus, Brandenburg, Deutschland angewandt. Die Parametrisierung des Modells erfolgt durch zugrundeliegende Einsatzdaten, dabei wird ein Geoinformationssystem (GIS) genutzt, Notrufe über die Bevölkerungsdichte mit einer zeitabhängigen Rate generiert und statistische Kenngrößen des Systems ausgewertet. Das in AnyLogic implementierte Simulationsmodell enthält eine graphische Nutzeroberfläche, in der Einsatzdetails und Statistiken als Grundlage für Anwendungen in der Praxis angezeigt werden.
Die vorliegende Arbeit untersucht die Instandhaltungsplanung eines militä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äß 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ür wird ein multikriterielles, ganzzahliges Optimierungsmodell entwickelt. Zum Lösen wird der Solver IBM ILOG CPLEX Optimization Studio (V 20.1.0.0) verwendet. In der Auswertung wird zusätzlich zu den Ergebnissen der Optimierung die Auswirkung von aggregierten und disaggregierten Formulierungen untersucht sowie der Effekt von Veränderungen der Aggressivität von Schnittebenenverfahren.
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.
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.
Die Bachelorarbeit beschäftigt sich mit der Entwicklung effizienter Methoden für die Klassifizierung der Stadien von Zellen. Hierbei liegt der Fokus auf sogenannten Deep-Learning-Algorithmen. Diese haben sich unter anderem in der Bilderkennung als sehr leistungsfähig erwiesen und können genutzt werden, um große Mengen von mikroskopischen Zellbildern in kurzer Zeit zu klassifizieren. Aufgezeigt werden Möglichkeiten zur Optimierung solcher Algorithmen mit dem Ziel, Genauigkeit und Speichergröße zu verbessern. Es wurden hierbei der Einfluss von verschiedenen Parametern auf die Performance eines Algorithmus untersucht und gegenübergestellt, verschiedene etablierte Modelle miteinander verglichen und eine Auswahl gängiger Methoden zur Modell-Optimierung getestet. Genutzt wurde die Software-Bibliothek TensorFlow, welche über die Programmiersprache Python angesprochen wird. Reale Anwendungsdaten wurden von der Firma Medipan zur Verfügung gestellt.
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.