Solving Non-standard Packing Problems by Global Optimization and Heuristics

verfasst von: Giorgio Fasano

Verlag: Springer International Publishing

Buchreihe : SpringerBriefs in Optimization

Enthalten in: Springer Professional "Wirtschaft+Technik" , Springer Professional "Technik" , Springer Professional "Wirtschaft"

Einloggen, um Zugang zu erhalten

Über dieses Buch

This book results from a long-term research effort aimed at tackling complex non-standard packing issues which arise in space engineering. The main research objective is to optimize cargo loading and arrangement, in compliance with a set of stringent rules. Complicated geometrical aspects are also taken into account, in addition to balancing conditions based on attitude control specifications.

Chapter 1 introduces the class of non-standard packing problems studied. Chapter 2 gives a detailed explanation of a general model for the orthogonal packing of tetris-like items in a convex domain. A number of additional conditions are looked at in depth, including the prefixed orientation of subsets of items, the presence of unusable holes, separation planes and structural elements, relative distance bounds as well as static and dynamic balancing requirements. The relative feasibility sub-problem which is a special case that does not have an optimization criterion is discussed in Chapter 3. This setting can be exploited by introducing an ad hoc objective function, aimed at facilitating the finding of integer-feasible solutions. The third chapter also discusses the issue of tightening the general MIP model by introducing valid inequalities. A MIP-based heuristic approach is developed in Chapter 4, where the basic concept of abstract configuration is presented. Chapter 5 is devoted to experimental results relevant to a real-world application framework. Chapter 6 adopts both extensions of the general MIP model and non-linear formulations to tackle two further non-standard packing issues. The final Chapter 7 presents conclusions and provides insights regarding prospective developments (including non-standard scheduling aspects).

Practitioners and researchers interested in advanced optimization model development and solution in the context of logistics, transportation systems, complex structures, manufacturing and electronics will find this book useful. The book can also be used in graduate courses on nonlinear - including global and mixed integer - optimization, as a valuable collection of practically meaningful object packing applications.

Inhaltsverzeichnis

Frontmatter

Chapter 1. Non-standard Packing Problems: A Modelling-Based Approach

Abstract

The general subject of packing objects, exploiting the available volume, as much as possible, has represented, for centuries, or even longer, an extremely tricky task. This issue seems trivial, until one encounters it. The question arose, for instance, when dealing with cannon ball stowage in ancient vessels. It is not surprising at all that it gained the role of the packing issue par excellence, when Hilbert announced his eighteenth problem (to date resolved by computer-assisted proof, e.g. Gray 2000). It concerned the accommodation of equal spheres, attaining the maximum density. This chapter introduces the overall subject of packing.

Giorgio Fasano

Chapter 2. Tetris-like Items

Abstract

The packing of tetris-like items, i.e. clusters of mutually orthogonal rectangular parallelepipeds, inside a given domain, is discussed here. Orthogonal rotations are admitted and additional conditions can be present. An MIP formulation is described at quite a detailed level.

Giorgio Fasano

Chapter 3. Model Reformulations and Tightening

Abstract

The general MIP model, discussed in Chap. 2, is reconsidered hereinafter, investigating some possible reformulations, from different points of view (Sect. 3.1). The objective of enucleating implicit implications and introducing valid inequalities, to tighten the model, is examined next (Sect. 3.2).

Giorgio Fasano

Chapter 4. Heuristic Approaches for Solving the Tetris-like Item Problem in Practice

Abstract

As easily gathered, the general MIP model, conceived to sort out the tetris-like item packing problem (Sect. 2.1), is usually very hard to solve. In this chapter the relevant intrinsic difficulties are examined first (Sect. 4.1). A heuristic philosophy is then emphasized to tackle efficiently the problem, even if just nonproven optimal solutions can, in general, be obtained.

Giorgio Fasano

Chapter 5. Computational Experience and Real-World Context

Abstract

Dealing with non-standard packing problems, and precisely because they are by definition outside the framework of any conventional classification, poses, from the experimental point of view, non-negligible difficulties. Firstly, a remarkable effort is requested to collect, or even generate ex novo, non-trivial instances. They need, actually, to cover an adequate number of scenarios, representative of a sufficiently wide area of real-world applications. Secondly, the elaboration of instances of practical interest is mostly very time consuming. Therefore, an extensive dedicated test campaign is extremely demanding, both in terms of human and computational resources. This chapter provides insights on relevant experimental aspects.

Giorgio Fasano

Chapter 6. Extensions and Mixed-Integer Nonlinear Approaches for Further Applications

Abstract

The modelling approach advocated by this volume is susceptible to possible extensions. One, in particular, deals with the problem of looking into how the free volume of a container, partially loaded with tetris-like items, could be profitably exploited. Virtual items, i.e. (rectangular) parallelepipeds of non-prefixed dimensions, are purposely introduced to ‘suggest’ how to fill the empty volumes. This issue is investigated hereinafter, highlighting a dedicated MIP formulation (Sect. 6.1). The problem of packing simple polygons, with continuous rotation, is further discussed. In Section 6.2 a MINLP mathematical model is introduced. It is aimed at providing good approximate solutions, from a global optimization point of view.

Giorgio Fasano

Chapter 7. Directions for Future Research

Abstract

Although this volume summarizes results derived from more than 2 decades of dedicated research, a number of study directions still remain open. This is mainly due, on one side, to the heuristic nature of the overall point of view adopted that, as such, relies on a huge amount of experimental activity. The modeling philosophy followed is, moreover, subject to a wide range of possible extensions. It is then worth looking into, at least in perspective, further applications and topical formulations. Section 7.1 outlines the experimental aspects, whilst Sect. 7.2 focuses on the modeling ones.

Giorgio Fasano

Erratum to: Chapter 3 Model Reformulations and Tightening

Giorgio Fasano

Backmatter

Titel: Solving Non-standard Packing Problems by Global Optimization and Heuristics
verfasst von: Giorgio Fasano
Verlag: Springer International Publishing
Electronic ISBN: 978-3-319-05005-8
Print ISBN: 978-3-319-05004-1
DOI: https://doi.org/10.1007/978-3-319-05005-8