How to #5: 3D Bin Packing
“The rhythm of relations of color and size make the absolute appear in the relativity of time and space” — Piet Mondrian
Optimization and operations research is a complex field. It’s one thing to want to know how to improve a business or process but it is another to put a business problem together using mathematics. Bin packing is a common area of operations research by where a container of items are fit into one or more containers in such a way as to minimize unused space. One dimensional bin packing can be seen as fitting items with the same width but differing heights into one container. This is normally a part of solving a larger problem. Two dimensional bin packing reimagines the first problem in two dimensions usually dealing with the base of an item without the height taken into effect. This is useful for metal cutting to cut an arbitrary amount of items from a sheet of metal. The final is a three dimensional bin packing. This uses both one dimensional and two dimensional bin packing . Items can be grouped into layers by and then the layers fit into an appropriate container.
3D bin packing is an NP hard problem. There could be a trade off or a point where the given results are “good enough” and the problem can bee seen as solved. The sources for the algorithms are from two papers by the same authors [1] and [2]. The first algorithm used is “Height first-Area second”(page quote). The algorithm has two parts:
1. Partition the items into clusters by non-increasing height and then construct optimal bins using a 1D bin packing problem.
2. The items are then re-sorted by non-increasing base area (width by depth) and a second solution is obtained using a 1D bin packing problem.
The optimal solution is then chosen as the minimum bins used for the items between the height sorted and area sorted.
The algorithm in [2] gives a partition percentage of possibly 0.75 which was used in the code. This partition value determines the way that the items are partitioned into clusters. After partitioning the layers are constructed to minimize the amount of layers by implementing a 2D bin problem. The 2D problem is explained in depth by [1] but is as follows:
1. Sort the items by non-increasing height.
2. Place the items with the first at the bottom left corner of the container.
3. Add items sharing an edge as close as possible to the right edge of the container
4. Place the next item on the minimum height item with the right edge touching the right edge of the container.
5. Place items sharing edges consecutively until none can fit or the left edge of the last item touches the left edge of the container with it’s left edge.
6. Alternate placing items left to right and right to left until none can be placed in either direction.
7. Start a new bin if necessary.
As the layers are built in two dimensions the next step is to optimally stack the layers in bins in such a way to minimize the overall amount of bins used. This is done using a simple 1D bin packing problem written with PuLP and Python. The problem is as follows:
The choice was made to print out the layers in folders by each bin. Again both the height and base area are used to complete the problem and the solution with the minimum amount of bins is chosen as a solution. A layer is a 2D representation of the items sorted by width and then put through the Alternating Directions algorithm:
The results can be tailored to a specific situation if needed. A 3D representation would only be needed to visualize the clusters and layers in each bin. Two dimensional was chosen as the layers can be built easier. The labeled layers for each bin are then saved in a pdf which bears the bin number.
Code:
[1] A. Lodi, S. Martello, D. Vigo,
Recent advances on two-dimensional bin packing problems,
Discrete Applied Mathematics,
Volume 123, Issues 1–3,
2002,
[2] A. Lodi , S. Martello, D. Vigoet , Heuristic algorithms for the three-dimensional bin packing problem, European Journal of Operational Research 141 (2002) 410–420, 2000
