Refine
Document Type
- Working paper (11)
- Report (6)
Has Fulltext
- yes (17)
Is part of the Bibliography
- no (17)
Language
- English (17)
Keywords
- Ganzzahlige Optimierung (5)
- Gemischt-ganzzahlige Programmierung (5)
- Mixed-integer programming (5)
- Finite-Elemente-Methode (4)
- Mixed-integer linear programming (4)
- Tourenplanung (4)
- Trajectory planning (4)
- Finite element method (3)
- Optimierung (3)
- Partial differential equations (3)
- Rapid Prototyping <Fertigung> (3)
- Trajektorienplanung (3)
- Additive Fertigung (2)
- Additive manufacturing (2)
- Bahnplanung (2)
- Flugkörper (2)
- Gemischt-ganzzahlige lineare Programmierung (2)
- Graph refinement (2)
- Graphenverfeinerung (2)
- Kürzester-Weg-Problem (2)
- Lineare Optimierung (2)
- Logistik (2)
- Mixed-integer nonlinear programming (2)
- Optimierungsproblem (2)
- Partielle Differentialgleichung (2)
- Partielle Differenzialgleichungen (2)
- Travelling-salesman-Problem (2)
- Wärmeleitung (2)
- Additive Draht-Lichtbogen-Fertigung, (1)
- Additive Fertigung mit Drahtlichtbogen (1)
- Bestandsmanagement (1)
- Bi-criteria optimization (1)
- Bikriterielle Optimierung (1)
- Box orientation (1)
- Branch-and-Bound (1)
- Branch-and-Bound-Methode (1)
- Branch-and-bound (1)
- Center of gravity deviation (1)
- Centroidal Voronoi tessellation (1)
- Container (1)
- Container packing problem (1)
- Convection-diffusion equation (1)
- Delivery robots (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)
- Expandierender Graph (1)
- Fertigungsprogrammplanung (1)
- Finite-Volumen-Methode (1)
- Finite-element methods (1)
- Ganzzahlige lineare Optimierung (1)
- Gemischt-ganzzahlige Optimierung (1)
- Gemischt-ganzzahlige nichtlineare Programming (1)
- Geographische Informationssysteme (GIS) (1)
- Geoinformationssystem (1)
- Geometric optimization (1)
- Geometrische Optimierung (1)
- Geschichtete Graphen (1)
- Global optimal control (1)
- Globale Optimalsteuerung (1)
- Graph construction (1)
- Graphen-Aufbau (1)
- Heat conduction (1)
- Heat equation (1)
- Heat transmission (1)
- Heuristics (1)
- Heuristik (1)
- Inhomogene Flotte (1)
- Inhomogeneous Fleet (1)
- Inspection path planning (1)
- Inspektionspfadplanung (1)
- Integer linear programming (1)
- Kleinstdrohnen (1)
- Konvektions-Diffusions-Gleichung (1)
- Konvektions-Diffusionsgleichung (1)
- Kürzeste Wege (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)
- Mehrdepotproblem (1)
- Mehrzieloptimierung (Pareto-Front) (1)
- Micro aerial vehicles (1)
- Mission Planning (1)
- Missionsplanung (1)
- Mixed Integer Linear Programming (1)
- Mixed integer linear programming (1)
- Mobiler Roboter (1)
- Moving targets (1)
- Multi-criteria optimization (Pareto frontier) (1)
- Nichtlineare Optimierung (1)
- Non-overlapping (1)
- Operational Research (1)
- Operations Research (1)
- Operations research (1)
- Optimale Kontrolle (1)
- Partial recharging (1)
- Partielle Differentialgleichungen (1)
- Partielles Aufladen (1)
- Path optimization (1)
- Pfadoptimierung (1)
- Problem des Handlungsreisenden mit Zeitfenstern (1)
- Production planning (1)
- Re-balancing problem (1)
- Routing (1)
- Scenario generation (1)
- Second-order cone programming (1)
- Shortest path (1)
- Shortest path problem with time-windows (1)
- Simulation (1)
- Stochastische Optimierung (1)
- Streckenplanung für elektrische Fahrzeuge (1)
- Szenario-Erzeugung (1)
- Time Windows (1)
- Time-Dependent Airplane Routing (1)
- Time-relaxation (1)
- Topography (1)
- Trajektorie <Mathematik> (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)
- Warehouse management (1)
- Wire arc additive manufacturing (1)
- Wire are additive manufacturing (1)
- Wärmeleitungsgleichung (1)
- Zeitfenster (1)
- Zentrierte Voronoi-Parkettierung (1)
- Zweistufige stochastische Optimierung (1)
Institute
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.
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.
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.
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.
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.
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.
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.
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.
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.