Joint Applied Mathematics and Statistics Seminar 12.5

Date: 12.05.2016, Thursday
Time: 12:30-14:00
Place: Room M2, Quantum
Speaker: Teemu Linkosaari

THREE-DIMENSIONAL BIN PACKING PROBLEM WITH A STABILITY REJECTION CRITERION

Abstract:
Packing problems play an important role in transportation and supply chain management. This study aims to solve a practical three-dimensional bin packing problem, where significantly different sized boxes are to be packed on a pallet. Without the benefit of supporting walls, it is critical to ensure that the boxes are supported and remain stable. Thus, there are two goals: solution compactness and stability. This problem is a part of the task of minimizing the number of pallets needed.

First, we use an existing bin packing algorithm based on packing indices, which converts an arbitrary list of boxes to a packing solution. The method is extended to be able to pack boxes from four corners instead of only one corner. Moreover, a particular method to check the stability of placed boxes is devised. In addition, it was discovered that a grouping of boxes with same dimensions can make the search space a bit smaller.

Second, a genetic algorithm is used to find a suitable permutation for the packing procedure. To further improve the solution quality, we utilize an existing global search framework combined with the concept of an evolutionary gradient.

The efficiency of the proposed method is tested and verified in an industrial setting. Two orientations are allowed: boxes are rotated around the vertical axis only. Volume utilization is maximized under the rejection stability criterion: i.e., we discard solutions if any packed box turns out to be unstable. Solutions obtained are more stable and packable than in previous studies.

Everybody interested are very welcome!