Refine
Document Type
- Working paper (3)
- Doctoral thesis (1)
Has Fulltext
- yes (4)
Is part of the Bibliography
- no (4)
Year of publication
- 2020 (4) (remove)
Keywords
- Kürzester-Weg-Problem (2)
- Logistik (2)
- Mixed-integer programming (2)
- Bahnplanung (1)
- Bestandsmanagement (1)
- Box orientation (1)
- Branch-and-Bound (1)
- Branch-and-Bound-Methode (1)
- Branch-and-bound (1)
- Center of gravity deviation (1)
- Container (1)
- Container packing problem (1)
- Ganzzahlige Optimierung (1)
- Gemischt-ganzzahlige Optimierung (1)
- Geographic information system (1)
- Geoinformationssystem (1)
- Geoinformationssysteme (1)
- Graph refinement (1)
- Graphenverfeinerung (1)
- Kürzeste Wege (1)
- Kürzeste Wege Problem mit Zeitfenstern (1)
- Lagermanagement (1)
- Lineare Optimierung (1)
- Logisitcs (1)
- Multi-criteria optimization (Pareto frontier) (1)
- Multikriterielle Optimierung (1)
- Multikriterielle Optimierung (Pareto-Front) (1)
- Non-overlapping (1)
- Operations Research (1)
- Operations research (1)
- Optimal routes (1)
- Optimale Routen (1)
- Optimierungsproblem (1)
- Problem des Handlungsreisenden mit Zeitfenstern (1)
- Scenario generation (1)
- Shortest path problem with time-windows (1)
- Shortest paths (1)
- Stochastische Optimierung (1)
- Szenario-Erzeugung (1)
- Trajectory planning (1)
- Trajektorienplanung (1)
- Travelling salesman problem with time-windows (1)
- Travelling-salesman-Problem (1)
- Two-stage stochastic optimization (1)
- Uncertainty (1)
- Unsicherheit (1)
- Unternehmensforschung (1)
- Warehouse management (1)
- Zweistufige stochastische Optimierung (1)
Institute
- FG Ingenieurmathematik und Numerik der Optimierung (4) (remove)
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.
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.
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.
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.