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 - Johannsmann, Leonie M. A1 - Craparo, Emily M. A1 - Dieken, Thor L. A1 - Fügenschuh, Armin A1 - Seitner, Björn O. ED - Fügenschuh, Armin T1 - Stochastic mixed-integer programming for a spare parts inventory management problem N2 - The German Armed Forces provide an operation contingent to support the North Atlantic Treaty Organization (NATO) Response Force (NRF). For this purpose, a „warehouse” containing accommodations, food supplies, medical supplies, and spare parts for the systems has to be available. Such a warehouse is restricted in weight, in order to be quickly movable in an upcoming deployment situation. It should be able to supply the NRF troops for a certain amount of time (e.g., one month) without re-supply from the outside. To ensure optimal use of such a restricted warehouse, we developed the computer program „The OPtimization of a Spare Parts Inventory” (TOPSPIN) to find an optimal mix of spare parts to restore a set of systems to functionality. Each system is composed of several parts, and it can only be used again in the mission if all broken parts are replaced. The failure rate of the individual parts follows a given random distribution, and during deployment it is expected to be higher than in the homeland. Due to the stochastic nature of the problem, we generate scenarios that simulate the actual failure of the parts. The backbone of TOPSPIN is a mixed-integer linear program that determines an optimal, scenario-robust mix of spare parts and is solved using standard state-of-the-art numerical solvers. Using input data provided by the Logistikzentrum, we analyze how many scenarios need to be generated in order to determine reliable solutions. Moreover, we analyze the composition of the warehouse over a variety of different weight restrictions, and we calculate the number of repairable systems as a function of this bound. N2 - Die Bundeswehr stellt ein Einsatzkontingent zur Unterstützung der NATO Response Force (NRF) zur Verfügung. Zu diesem Zweck muss ein Lager mit Unterkünften, Lebensmitteln, medizinischer Versorgung und Ersatzteilen für die Systeme vorhanden sein. Ein solches Lager ist gewichtsbeschränkt, um in einer bevorstehenden Einsatzsituation schnell versendbar zu sein. Es sollte in der Lage sein, die NRF-Truppen für eine bestimmte Zeitspanne (z. B. einen Monat) zu versorgen, ohne von außen erneut zu versorgt zu werden. Um eine optimale Nutzung eines solchen eingeschränkten Lagers zu gewährleisten, haben wir das Computerprogramm „The OPtimization of a Spare Parts INventory" (TOPSPIN) entwickelt, um eine optimale Mischung von Ersatzteilen zu finden, mit der die Funktionalität einer Reihe von Systemen wiederhergestellt werden kann. Jedes System besteht aus mehreren Teilen und kann nur dann in der Mission wieder verwendet werden, wenn alle defekten Teile ersetzt wurden. Die Ausfallrate der einzelnen Teile richtet sich nach einer vorgegebenen Zufallsverteilung und wird im Einsatz voraussichtlich höher sein als im Heimatland. Aufgrund der stochastischen Natur des Problems generieren wir Szenarien, die den tatsächlichen Ausfall der Teile simulieren. Das Grundgerüst von TOPSPIN ist ein lineares gemischt-ganzzahliges Programm, das einen optimalen, Szenario-stabilen Ersatzteilmix ermittelt und mit den modernen numerischen Standardverfahren gelöst wird. Anhand der vom Logistikzentrum der Bundeswehr bereitgestellten Eingangsdaten analysieren wir, wie viele Szenarien generiert werden müssen, um verlässliche Lösungen zu ermitteln. Darüber hinaus analysieren wir die Zusammensetzung des Lagers über verschiedene Gewichtsbeschränkungen und berechnen die Anzahl der reparierbaren Systeme in Abhängigkeit von dieser Grenze. T3 - Cottbus Mathematical Preprints - 11, 2020 KW - Logisitcs KW - Scenario generation KW - Bestandsmanagement KW - Logistik KW - Ganzzahlige Optimierung KW - Stochastische Optimierung KW - Operations Research KW - Uncertainty KW - Warehouse management KW - Operations research KW - Two-stage stochastic optimization KW - Mixed-integer programming KW - Logistik KW - Szenario-Erzeugung KW - Unsicherheit KW - Lagermanagement KW - Gemischt-ganzzahlige Optimierung KW - Unternehmensforschung KW - Zweistufige stochastische Optimierung Y1 - 2020 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:co1-opus4-50802 SN - 2627-6100 ER - TY - RPRT A1 - Ocloo, Valentina E. A1 - Fügenschuh, Armin A1 - Pamen, Olivier M. ED - Fügenschuh, Armin T1 - A new mathematical model for a 3D container packing problem N2 - Wir betrachten das Problem der Einzelcontainerpackung eines Unternehmens, das seine Kunden bedienen muss, indem es zuerst die Produkte in Kartons legt und diese dann in einen Container lädt. Für dieses Problem entwickeln und lösen wir ein lineares gemischt-ganzzahliges Modell. Unser Modell berücksichtigt geometrische Randbedingungen, beispielsweise Überlappungsverbote, Orientierungs-Bedingungen und Randbedingungen für die relative Positionierung der Kartons. Wir betrachten auch die Erweiterung des Modells durch die Integration der Schwerpunktsabweichung der Packung vom Containermittelpunkt. Das Modell wurde an einer großen Anzahl von realen Instanzen getestet, die bis zu 41 Kartons enthalten. In den meisten Fällen wurden optimale Lösungen erzielt bzw. nah-optimale Lösungen mit beweisbar kleiner Optimalitätslücke. N2 - We address the single container packing problem of a company that has to serve its customers by first placing the products in boxes and then loading the boxes into a container. We approach the problem by developing and solving mixed-integer linear models. Our models consider geometric constraints that feature non-overlapping constraints, box orientation constraints, dimensionality constraints, relative packing position constraints, and linearity constraints. We also develop an extension of the models by integrating load balance and the deviation of the center of gravity. We tested the models on a broad set of real instances involving up to 41 boxes and obtained optimal solutions in most cases and very small gaps when optimality could not be proven. T3 - Cottbus Mathematical Preprints - 12, 2020 KW - Container packing problem KW - Mixed-integer programming KW - Box orientation KW - Non-overlapping KW - Center of gravity deviation KW - Optimierungsproblem KW - Container KW - Lineare Optimierung KW - Logistik Y1 - 2020 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:co1-opus4-50880 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 -