How Clutter efficiently packs pallets
Recently, Clutter released a feature to present the optimal pallet composition for a given Stock Keeping Unit (SKU) in our internal iOS app for our warehouse team. It enables us to efficiently utilize warehouse and truck space and save time loading items onto pallets. This article will cover our approach to the pallet loading problem and briefly summarize the paper we implemented.
Why we built this
The way we stack our pallets has notable cross-cutting concerns:
Warehouse storage
- Utilizing our warehouse space more efficiently allows us to offer more space to more customers
- Customers want their inventory stored in the most efficient way possible, which helps lower their costs to sell it
Fulfillment
- When fulfilling shipments out of our warehouse, we want to make sure that we’re maximizing the number of items we put on the truck to make sure the whole order is fulfilled
- Minimizing empty space on the truck also reduces the chance of items being damaged while the truck is in motion
- Optimizing the pallet on inbound shipments can potentially reduce the amount of extra labor needed to prepare outbound shipments
- Saving time determining how to load pallets also helps lower costs
A good solution must produce demonstrably optimal results and be easy to understand for the end user, Clutter’s warehouse employees. This led us to the pallet loading problem. With iOS SpriteKit as the visualization tool, we were able to create a solution that meets these success criteria.
What is an optimal pallet arrangement?
Before diving into the solution, we should define what an optimal pallet arrangement is. There are a number of formulations of the pallet loading problem with varying complexity. From optimizing a 3D composition with arbitrary rotations and boxes of different sizes, we pared the problem down to finding the optimal way to arrange the maximum number of identical boxes in a single, flat layer on a pallet. Or in other words, the composition of identical rectangles in a larger rectangle, with 90° rotations. This makes it easy for someone to follow a diagram of the optimal composition and stack to a given height.
Despite these constraints to the problem, determining the optimal composition may not be immediately obvious.
You can try it out for yourself with this realistic example! Given a SKU with dimensions 14” x 6” and a pallet with dimensions 48” x 40” (the size of a standard pallet), determine the composition that will fit the maximum number of that SKU.
Intuitively, we could use a bound determined by the areas of the SKU and pallet to determine the maximum number of boxes we could possibly place, i.e. ⎣(48*40)/(14*6)⎦ = 22. This bound may not always work to find the optimal box count, and still, knowing the optimal box count may not lead directly to an optimal composition.
Did you come up with an optimal composition? A possible solution will be revealed in the following diagram.
Typically, finding the optimal configuration is done through trial-and-error by our warehouse team. Our goal for an implementation was to obviate this trial-and-error process without adding overhead, leading us to do research on the topic.
Research
After surveying papers and libraries, we landed on Solving the Pallet Loading Problem [1] by Martins and Dell (2008), included in a more detailed dissertation Packing in two and three dimensions [2] by Martins (2003).
In the paper, Martins calculated the performance of simple heuristics and found that for problems where the optimal box count is less than or equal to 50, over 99% are solved by four heuristics. To prove this, Martins used previous and proposed new methods to find optimal box count bounds for instances of the pallet loading problem and measured whether the employed heuristics came up with the optimal box count.
Satisfied with the simplicity of implementation, generally low run-time, and performance, we moved forward with implementing those four simple heuristics to generate pallet compositions. The heuristics used to calculate the optimization performance metric were the one-block, three-block, five-block, and hollow-block heuristics.
Algorithm description
To help follow along, this is a cheat sheet for the concepts that were defined in Martins (2003).
Partitions
Partitions are the backbone of the heuristics; each heuristic makes use of them. As defined by Martins (2003), a partition is an ordered pair (n, m) that denotes how many a-length and b-length segments fit across a dimension of a pallet (X or Y). n denotes the number of a-length segments and m denotes the number of b-length segments. There are three sets of partitions defined by Martins: feasible, efficient, and perfect.
Feasible partitions (left) denote the set of partitions such that n*a + m*b ≤ X (Martins 2003).
Efficient partitions (middle) are denoted by the set of partitions such that 0 ≤ X − n*a − m*b < b. Efficient partitions are feasible partitions with the added condition that no more boxes should be able to fit along the dimension (Bischoff and Dowsland 1982, as cited by Martins 2003).
Perfect partitions (right) are denoted by the set of partitions such that n*a + m*b = Y. Perfect partitions are efficient partitions with the added condition that the boxes fill the entire dimension’s length (Dowsland 1984, as cited by Martins 2003).
Heuristics
To get a feel for the heuristics, this article will go over the one-block and three-block heuristics in some depth and briefly describe the five-block and hollow-block heuristics as the heuristics are described in Martins (2003).
The animations were made using the awesome manim (community) [3] library, a fork of Grant Sanderson’s manim library.
Side note: The one-block and three-block heuristics are not required to be implemented to solve over 99% of the instances where the optimal box count is less than or equal to 50, the metric mentioned back in the research section, as the five-block heuristic can create one-block and three-block solutions as part of its solution iterations.
One-Block Heuristic
The one-block heuristic uses one homogenous block to determine the composition. There are two ways the block can be oriented, vertically or horizontally.
The number of boxes in each orientation can be determined by applying efficient partitions across each dimension.
For example, for the PLP instance of (22, 14, 7, 3) (instance taken from Martins 2003), when creating the V-block, we determine how many vertical boxes can be placed across the X dimension by choosing the element in the set of efficient partitions where n = 0. Similarly, across Y, we find the element in the set of efficient partitions where m = 0, corresponding to the number of V-boxes that can be placed across Y. Combining the results of these calculations, we get 7∗2 = 14 boxes.
We run an analogous process for an H-block, with a’s across X and b’s across Y. We find that the V-block configuration is able to place more boxes, so the one-block heuristic determines the V-block configuration as the solution.
Three-Block Heuristic
The three-block heuristic uses up to three blocks to create a composition and employs the simpler two-block heuristic before adding a third block. The two-block heuristic loops through several ways to create two blocks and selects the configuration that can fit the most boxes. The three-block heuristic runs the two-block heuristic and fills any leftover space with the result of the one-block heuristic for each two-block configuration (Martins 2003).
More precisely, the two-block heuristic loops through efficient partitions of X and Y (separately) to determine the size of the two blocks.
For instance, when iterating through efficient partitions across Y, n and m correspond to a V-block with n∗Bx boxes and an H-block with m∗Ax boxes (Martins 2003). Then (within an iteration), in the potential space left over, the one-block heuristic can be used to create a third block. This is illustrated in the following example, with instance (19, 13, 4, 3) (instance taken from Martins 2003):
Where (n, m) = (1, 3) and the two box V-block is filled in by the one-block heuristic.
When iterating through efficient partitions across X, n and m correspond to an H-block with n∗By boxes and a V-block with m∗Ay boxes. An example can be seen in the following animation.
This animation iterates through the configurations the three-block heuristic tries out before reaching the optimal 20 box solution.
Five-Block Heuristic
The five-block heuristic, like the three-block heuristic, is a combination of the four-block heuristic and uses the one-block heuristic to fill the potential empty space (Martins 2003). As cited by Martins (2003), the four-block heuristic was proposed by Steudel (1979) and Smith and de Cani (1980). The five-block heuristic was proposed by Bischoff and Dowsland (1982). The five-block heuristic makes use of efficient partitions.
Hollow-Block Heuristic
Martins (2003) proposed the hollow-block heuristic to fill some gaps left behind by the other simple heuristics. The hollow-block heuristic configuration consists of d diagonal blocks and m main blocks. There are d diagonal blocks that lay along the diagonal and (d-1) main blocks to the sides and (d-1) main blocks above and below a given diagonal block (Martins 2003). The hollow-block heuristic makes use of perfect partitions.
In practice
Occasionally, a SKU has a length that is just over the length of one of our pallet sizes. The strict X (pallet length) ≥ a (box length) rule being broken would show a user that there was no valid composition for that SKU on the pallet they were trying to place it on. For example, a SKU with a length of 48.5” would not have a valid composition for the standard pallet size of 48” x 40”.
Practically, we are able to accommodate some overhang before having to move up to a larger pallet size and would like to show a composition where feasible. To accomplish this, we added rules to determine the dimensions of X and Y, using max(X, a) and max(Y, b), if the dimensions of the box fit within our overhang thresholds.
Conclusion
The heuristics described in Martins (2003) have been employed for a few weeks now and have seen great adoption at our warehouses. Around 90% of reworked pallets on our outbound loads comply with the guidance shown.
This project is one of many optimization problems in the Clutter supply chain. If you are looking to join an amazing team of Ruby developers, check our current openings at Clutter.
Thanks to Brian Girer and John Brophy
References
[1] G. H. Martins and R. F. Dell, “Solving the pallet loading problem,” European Journal of Operational Research, vol. 184, no. 2, pp. 429–440, 2008.
[2] G. H. A. Martins, “Packing in two and three dimensions,” thesis, 2003.
[3] The Manim Community Developers, Manim — Mathematical Animation Framework (Version v0.9.0). 2021.
