Bin-packing problems with load balancing and stability constraints

The Bin-Packing Problem (BPP) is one of the most investigated and applicable combinatorial optimization problems. The problem consists of packing objects of different sizes into a finite number of similar bins, such that the number of used bins is minimized. Applications of the bin-packing problem apper in a wide range of disciplines, including transportation and logistics, computer science, engineering, economics and manufacturing. The problem is well-known to be N P-hard and difficult to solve in practice, especially when dealing with the multi-dimensional cases. Closely connected to the BPP is the Container Loading Problem (CLP), which addresses the optimization of a spacial arrangement of cargo inside a container or transportation vehicle, with the objective to maximize the value of the cargo loaded or the volume utilization. The CLP focuses on a single container, and has been extended in the literature to handle a variety of different constraints arising from real-world problems. Consider for example the problem of arranging items into an aircraft cargo area such that the barycenter of the loaded plane is as close as possible to an ideal point given by the aircraft’s
specifications. The position of the barycenter has an impact on the flight performance in terms of safety and efficiency, and even a minor displacement from the ideal barycenter can lead to a high increase of fuel consumption [1]. Similar considerations apply when loading trucks and container ships. The aim of this work is to integrate realistic constraints related to e.g. load balancing, cargo stability and weight limits, in the multi-dimensional BPP. The BPP poses additional
challenges compared to the CLP due to the supplementary objective of minimizing the number of bins. In particular, in section 2 we discuss how to integrate bin-packing and load balancing of items. The problem has only been considered in the literature in simplified versions, e.g. balancing a single bin or introducing a feasible region for the barycenter. In section 3 we generalize the problem to handle cargo stability and weight constraints.