Treffer: A fast optimization approach for a complex real-life 3D Multiple Bin Size Bin Packing Problem.

We investigate a real-life air cargo loading problem which is a variant of the three-dimensional Variable Size Bin Packing Problem with special bin forms of cuboid and non-cuboid unit load devices (ULDs). Packing is constrained by additional practical restrictions, such as load stability, (non-)stackable items, and weight distribution constraints. To solve the problem, we present an insertion heuristic embedded into a Randomized Greedy Search. The solution space is limited by only considering certain candidate points (so-called extreme points), which are promising positions to load an item. We extend the concept of extreme points proposed in the literature and allow moving extreme points for non-cuboid ULDs. A special sorting of the items, which combines a layered structure and free packing, is suggested. Moreover, we propose dividing the space of each ULD into smaller cells to accelerate the collision, non-floating, and stackability check while loading items. In a computational study, we analyze individual algorithm components and show the effectiveness of our method on adapted real-life instances from the literature. • New variant of a 3D Multiple Bin Size Bin Packing Problem is introduced. • Very fast Randomized Greedy Search based on an insertion heuristic is proposed. • Grid acceleration technique is proposed and evaluated. • Set of extreme points proposed in the literature is extended. • The presented approach outperforms the state of the art approach. [ABSTRACT FROM AUTHOR]

Copyright of European Journal of Operational Research is the property of Elsevier B.V. and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)