TY - RPRT A1 - Dee, Robin A1 - Fügenschuh, Armin A1 - Kaimakamis, George T1 - The unit re-balancing problem T1 - Das Einheiten-Umverteilungs-Problem N2 - 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. N2 - Wir beschreiben das Problem der Umverteilung einer Anzahl von Einheiten, die über ein geografisches Gebiet verteilt sind. Jede Einheit besteht aus einer Reihe von Komponenten. Ein Wert zwischen 0 und 1 beschreibt die aktuelle Bewertung jeder Komponente. Durch eine stückweise lineare Funktion wird dieser Wert in eine nominale Zustandsbewertung umgerechnet. Der niedrigste Status bestimmt die Effizienz einer Einheit und der höchste Status seine Kosten. Eine unausgeglichene Einheit weist eine Lücke zwischen diesen beiden auf. Um die Einheiten neu auszubalancieren, können Komponenten übertragen werden. Ziel ist es, die Effizienz aller Einheiten zu maximieren. Auf einer untergeordneten Ebene sollten die Kosten für die Umverteilung minimal sein. Für dieses Problem stellen wir eine gemischt-ganzzahlige nichtlineare Modellformulierung vor, die die potenzielle Bewegung von Komponenten als Mehrgüterfluss beschreibt. Die stückweise linearen Funktionen, die zum Erhalten der Statuswerte benötigt werden, werden unter Verwendung von Ungleichungen und binären Variablen umformuliert. Dies führt zu einem gemischt-ganzzahligen linearen Programm, und numerische Standardlöser sind in der Lage, beweisbar optimale Lösungen für Instanzen mit bis zu 100 Einheiten zu berechnen. Wir präsentieren numerische Lösungen für eine Reihe von Testinstanzen und eine bikriterielle Zielfunktion und diskutieren den Kompromiss zwischen Kosten und Effizienz. T3 - Cottbus Mathematical Preprints - 22, 2021 KW - Re-balancing problem KW - Efficiency KW - Mixed-integer linear programming KW - Bi-criteria optimization KW - Umverteilungsproblem KW - Effizienz KW - Gemischt-ganzzahlige Programmierung KW - Bikriterielle Optimierung KW - Ganzzahlige Optimierung KW - Optimierungsproblem KW - Effizienz Y1 - 2021 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:co1-opus4-56587 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 - THES A1 - Roman, Anschel Julio ED - Fügenschuh, Armin T1 - Künstliche neuronale Netze in biomedizinischen Anwendungen T1 - Artificial neuronal networks in biomedical applications N2 - 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. N2 - The bachelor thesis deals with the development of efficient methods for the classification of cell stages. The focus here is on so-called deep learning algorithms. Among other things, these have proven to be very powerful in image recognition and can be used to classify large quantities of microscopic cell images in a short time. Possibilities for optimizing such algorithms with the aim of improving accuracy and memory size are shown. The influence of various parameters on the performance of an algorithm was examined and compared, various established models were compared with one another and a selection of common methods for model optimization were tested. The TensorFlow software library was used, which is addressed via the Python programming language. Real application data were provided by Medipan. T3 - Cottbus Mathematical Preprints - 20, 2021 KW - Künstliche neuronale Netze KW - Tiefes Lernen KW - Nichtlineare Optimierung KW - Bilderkennung KW - Bildklassifizierung KW - Artificial neuronal networks KW - Deep learning KW - Nonlinear optimization KW - Image recognition KW - Image classification KW - Neuronales Netz KW - Mustererkennung KW - Deep learning KW - Nichtlineare Optimierung Y1 - 2021 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:co1-opus4-56309 ER - TY - THES A1 - Flister, Tobias ED - Fügenschuh, Armin T1 - Eine Heuristik zur Lösung ganzzahliger Programme mit quadratischen Nebenbedingungen T1 - A heuristic for the solution of integer programs with quadratic constraints N2 - Die Frage nach dem Lösen von ganzzahligen Programmen mit quadratischen Nebenbedingungen spielt beim Aufbau multistatischer Sonar-Netze eine Rolle. Hierbei werden Schall-Sender und -Empfänger in einem Ozeanabschnitt so platziert, dass möglichst jeder Bereich durch mindestens ein Sender-Empfänger-Paar überwacht werden kann. Diskretisiert man den Abschnitt räumlich, so kann die Frage nach der Platzierung durch binäre Entscheidungsvariablen beschrieben werden. Da es auf die paarweise Platzierung ankommt, werden in den Modellen die Binärvariablen multipliziert, was einem logischen „Und“ entspricht. Um die Modelle halbwegs schnell numerisch zu lösen, wurden in der Literatur zahlreiche Linearisierungstechniken entwickelt und erprobt. Trotz allem Fortschritt ist man weit davon entfernt, Instanzen mit deutlich mehr als 100 Diskretisierungspunkten in annehmbarer Zeit zur Optimalität zu lösen. In dieser Bachelorarbeit werden heuristische Lösungsverfahren entwickelt, welche in der Lage sind, innerhalb kürzester Zeit gute (aber nicht beweisbar optimale) Lösungen zu liefern. Ausgangspunkt war die Grundidee, Sender und Empfänger abwechselnd zu optimieren, bis keine weitere Verbesserung mehr eintritt. Numerische Ergebnisse werden anhand von Testinstanzen präsentiert und mit einem exakten Ansatz verglichen. N2 - The question of solving integer programs with quadratic constraints plays a role when setting up multistatic sonar networks. Sound transmitters and receivers are placed in an ocean section in such a way that, if possible, every area can be monitored by at least one transmitter-receiver pair. If the section is discretized spatially, the question of placement can be described by binary decision variables. Since it depends on the placement in pairs, the binary variables are multiplied in the models, which corresponds to a logical "And". In order to numerically solve the models reasonably quickly, numerous linearization techniques have been developed and tested in the literature. Despite all the progress, one is far from solving instances with significantly more than 100 discretization points in a reasonable time to optimality. In this bachelor thesis, heuristic solution methods are developed, which are able to deliver good (but not provable optimal) solutions within a very short time. The starting point was the basic idea of alternately optimizing the transmitter and receiver until there was no further improvement. Numerical results are presented using test instances and compared with an exact approach. T3 - Cottbus Mathematical Preprints - 19, 2021 KW - Heuristiken KW - Ganzzahlige Programmierung KW - Quadratische Nebenbedingungen KW - Multistatisches Sonar KW - Netzplanung KW - Heuristics KW - Integer programming KW - Quadratic constraints KW - Multi-static sonar KW - Network planning KW - Ganzzahlige Optimierung KW - Heuristik KW - Netzplanung Y1 - 2021 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:co1-opus4-56175 ER - TY - RPRT A1 - Schmidt, Johannes A1 - Buhl, Johannes A1 - Fügenschuh, Armin ED - Fügenschuh, Armin T1 - A finite element approach for trajectory optimization in Wire-Arc Additive Manufacturing T1 - Einsatz der Finite-Elemente-Methode zur Pfadoptimierung in Wire-Arc Additive Manufacturing N2 - 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. N2 - Beim Fertigungssprozess des Wire-Arc Additive Manufacturing (WAAM) wird ein Werkstück schichtweise durch eine sich bewegende Wärmequelle aufgebaut, die Tropfen aus geschmolzenem Schweißdraht auf eine Grundplatte aufbringt. Um Materialansammlungen zu reduzieren, sollte die Trajektorie der Schweißquelle zusammenhängend sein, aber Bewegungen ohne Schweißen, Deadheading genannt, sind ebenfalls möglich. Durch die enorme Hitze der Schweißquelle werden große Temperaturunterschiede verursacht, die zu einer Spannungsverteilung im Bauteil führen. Dadurch entsteht Verzug und sogar Risse können auftreten. Deshalb verringern große Temperaturunterschiede die Qualität des Werkstücks. Wir untersuchen das Problem, eine Trajektorie der Schweißquelle mit minimaler Temperaturabweichung von einer gegebenen Zieltemperatur für eine Lage eines Werkstücks mit Schweißsegmenten, die breiter als die Breite des Schweißbads sind, zu finden. Die Temperaturverteilung wird mit Hilfe der Finiten-Elemente-Methode modelliert. Wir formulieren dieses Problem als ein gemischt-ganzzahliges lineares Optimierungsmodell und demonstrieren seine Anwendbarkeit durch einen Standardlöser für gemischt-ganzzahlige Optimierungsprobleme. T3 - Cottbus Mathematical Preprints - 18, 2021 KW - Additive manufacturing KW - Heat equation KW - Path optimization KW - Finite element method KW - Mixed-integer linear programming KW - Additive Fertigung KW - Pfadoptimierung KW - Wärmeleitungsgleichung KW - Finite-Elemente-Methode KW - Gemischt-ganzzahlige lineare Programmierung KW - Rapid Prototyping KW - Wärmeleitungsgleichung KW - Bahnplanung KW - Ganzzahlige lineare Optimierung KW - Finite-Elemente-Methode Y1 - 2021 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:co1-opus4-55753 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 - Schmidt, Johannes A1 - Fügenschuh, Armin ED - Fügenschuh, Armin T1 - A two-time-level model for mission and flight planning of an inhomogeneous fleet of unmanned aerial vehicles T1 - Ein Zwei-Zeitraster-Modell für die Missions- und Flugplanung einer inhomogenen Flotte unbemannter Luftfahrzeuge N2 - 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. N2 - Wir betrachten das Missions- und Flugplanungsproblem für eine inhomogene Flotte unbemannter Luftfahrzeuge (UAVs). Darin werden das Missionsplanungsproblem der Zuweisung von Zielen zu einer Flotte von UAVs und das Flugplanungsproblem der Suche nach optimalen Flugbahnen zwischen einer gegebenen Menge von Wegpunkten in einem Modell kombiniert und gelöst. Darin müssen die Flugbahnen einer inhomogenen Flotte von UAVs so spezifiziert werden, dass die Summe der wegpunktbezogenen Bewertungen unter Berücksichtigung technischer und umweltbedingter Einschränkungen maximiert wird. Eine vorhandenes Grundmodell wird erweitert, um eine detailliertere Lösung zu erzielen. Ein zweistufiger Zeitrasteransatz wird vorgestellt, um die berechneten Trajektorien zu glätten. Das dreidimensionale Missionsgebiet kann konvex geformte eingeschränkte Lufträume und konvexe Teilbereiche enthalten, in denen Wind die Flugbahnen beeinflusst. Darüber hinaus hängt die Flugdynamik mit der Massenänderung aufgrund des Kraftstoffverbrauchs zusammen, und die Reichweite jedes UAV ist höhenabhängig. Eine Klasse von Benchmark-Instanzen zur Kollisionsvermeidung wird an unser Modell angepasst und erweitert, und wir beweisen eine Obergrenze für den Zielfunktionswert. Schließlich werden die vorgestellten Funktionen und Ergebnisse an mehreren Testinstanzen getestet und diskutiert, wobei GUROBI als hochmoderner numerischer Löser verwendet wird. T3 - Cottbus Mathematical Preprints - 16, 2021 KW - Mixed-integer nonlinear programming KW - Mission Planning KW - Inhomogeneous Fleet KW - Time Windows KW - Linearization methods KW - Gemischt-ganzzahlige nichtlineare Programming KW - Missionsplanung KW - Inhomogene Flotte KW - Zeitfenster KW - Linearisierungsmethoden KW - Nichtlineare Optimierung KW - Tourenplanung KW - Flugkörper Y1 - 2021 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:co1-opus4-54619 ER - TY - THES A1 - Tchouto Mbatchou, Thierry ED - Fügenschuh, Armin T1 - Training of artificial neuronal networks with nonlinear optimization techniques T1 - Training künstlicher Neuronaler Netze mit Techniken der nichtlinearen Optimierung N2 - Machine learning is a field that has been the object of study of many researchers around the globe during the last decades. Very often to solve machine learning challenges like classification problems for example, one needs to train an artificial neural network. To train this network a certain loss function has to be minimized. There is a ubiquitous approach to achieve this which consists of using variants of the stochastic gradient descent combined with the backpropagation algorithm. In our work, we aimed at testing a rather non-conventional scheme consisting of making use of the solvers a software called AMPL offers. N2 - Maschinelles Lernen ist ein Gebiet, mit dem sich in den letzten Jahrzehnten viele Forscher rund um den Globus intensiv auseinandergesetzt haben. Um Probleme im Gebiet des maschinellen Lernens lösen zu können, wie zum Beispiel Klassifizierungsprobleme, muss man sehr oft ein künstliches neuronales Netz trainieren. Damit ein solches Netz erfolgreich trainiert werden kann, muss eine bestimmte Verlustfunktion minimiert werden. Es gibt einen allgegenwärtigen Ansatz, um dies zu erreichen, der darin besteht, Varianten des stochastischen Gradientenabstiegs kombiniert mit dem Backpropagation-Algorithmus zu verwenden. In unserer Arbeit wollten wir ein eher unkonventionelles Schema testen, indem wir die von einer Software names AMPL angebotenen Solver gebrauchen. T3 - Cottbus Mathematical Preprints - 15, 2021 KW - Nonlinear optimization KW - Artificial neuronal networks KW - Image recognition KW - Nichtlineare Optimierung KW - Künstliche Neuronale Netze KW - Bilderkennung KW - Bilderkennung KW - Neuronales Netz KW - Nichtlineare Optimierung KW - AMPL Y1 - 2021 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:co1-opus4-54042 ER - TY - THES A1 - Zazai, M. Fawad ED - Fügenschuh, Armin T1 - Berechnung der Trajektorien für die Entwicklung von optimalen Routen T1 - Computing the trajectories for the development of optimal routes N2 - Die Konstruktionsplanung von neuen Transitrouten oder Energieleitungen auf einem topografischen Gelände wird von Ingenieuren in der Regel manuell vorgenommen, ohne dass eine Optimalität garantiert werden kann. Wir stellen einen neuen Ansatz zur Berechnung von Trajektorien für die Entwicklung neuer optimaler Transitrouten und Energieleitungen zwischen zwei Standorten auf einer Untermannigfaltigkeit U von IR³ vor. Diese Untermannigfaltigkeit repräsentiert die Topographie eines Geländes. U wird näherungsweise durch ein spezielles gewichtetes Gitternetz modelliert. Auf diesem Gitternetz werden die kürzesten Wege für den Bau neuer Routen bestimmt, wobei wir drei Optimierungskriterien betrachten werden: Routen mit minimaler Länge, Routen mit geringsten Baukosten und Routen mit minimalen absoluten Höhenvariationen oder minimalen absoluten Steigungen. Anschließend wird eine Kombination dieser Kriterien gebildet, um dieses Problem zu einem multikriteriellen Optimierungsproblem zu erweitern. Ein Algorithmus für den kürzesten Weg, wie der Dijkstra-Algorithmus, wird verwendet, um optimale Kompromisse für die Konstruktion neuer Routen zu berechnen. N2 - Planning the construction of new transit 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 optimal trajectories for the development of new transit routes and power lines between two locations on a submanifold U of IR³ 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 minimal length, 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. T3 - Cottbus Mathematical Preprints - 14, 2020 KW - Kürzeste Wege KW - Trajektorienplanung KW - Optimale Routen KW - Multikriterielle Optimierung (Pareto-Front) KW - Geoinformationssysteme KW - Shortest paths KW - Trajectory planning KW - Optimal routes KW - Multi-criteria optimization (Pareto frontier) KW - Geographic information system KW - Bahnplanung KW - Geoinformationssystem KW - Kürzester-Weg-Problem KW - Multikriterielle Optimierung Y1 - 2020 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:co1-opus4-52286 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 -