A best fit heuristic for the three-dimensional Bin Packing Problem with practical constraints from an air transportation application

This work considers the three-dimensional Multiple Bin Size Bin Packing Problem which consists in packing a set of cuboid boxes into containers of various shapes, while minimising unused space. The aim of the present work is to find good initial solutions in short computational times. In this purpose, a fast best fit heuristic able to manage the different constraints to be met in transportation is developed. The heuristic is split into two distinct phases. The first phase deals with the packing of boxes into identical bins using an extension of the Extreme Points rule. During this phase, the fragility, stability and orientation of the boxes are taken into account, as well as the special shape of the bins and their weight capacity. The second phase considers the multiple types of available bins. If necessary, the best loading pattern identified is enhanced with respect to weight distribution in post processing. After parametrisation, computational experiments are performed on data sets specially designed for this application. The heuristic requires very short computational times to achieve promising results.