Can you win the stacking challenge? An example of heuristic optimization

I have come across an interesting optimization problem. The task is to stack the items of a given set of boxes of different sizes, weights, and stabilities onto as few pallets as possible. Moreover, there is a multitude of additional conditions that have to be met. To name only a few:

• Each pallet must consist of no more than four non-overlapping stacks, one in each quarter of the pallet.
• The additional weight that can be stacked onto a box is limited. Each box has a specific stacking weight it can carry.
• To ensure transport safety, a pallet must not exceed a certain degree of top-heaviness.
• Some types of boxes are only allowed to be stacked onto one another if a certain order is kept. So, for example, you can stack box A onto box B, but not the other way around.
• The maximum height of each stack is limited and the limit should be exploited wherever possible.

Optimization problems of this kind first of all have to be translated into a mathematical expression. The result of the translation process is a (multivariate) function \(f\left(\boldsymbol{x}\right), \boldsymbol{x}=\left[x_{1}, x_{2},…,x_{n}\right]\). Since all common optimization algorithms calculate the minimum of a function, the function \(f\) must be formulated accordingly. Unfortunately, optimization problems like the one mentioned above usually result in extremely high-dimensional functions that are neither continuous nor unimodal. Therefore, classical, derivative-based optimization algorithms are not very effective at this point. In such cases, so-called heuristic optimization methods represent a good alternative. In a nutshell, heuristic optimization algorithms start out by generating a set of random inputs to the function to be minimized. Depending on the associated outputs, new inputs are generated, which hopefully yield a function output that is lower than the lowest one of the previous iteration. The generation of new inputs is often inspired by phenomena in nature and in particular in the animal world (particle swarm algorithm, genetic algorithm, ant colony algorithm, grey wolf algorithm, etc.) and physics (harmony search, wind-driven optimization, simulated annealing).

The following YouTube video shows how the traveling salesman problem is solved by using the simulated annealing algorithm. In this problem, a list of cities that the traveling salesman should visit is given. At the end of the journey, he has to return to the first city and no other city may be visited twice. The goal is to determine the shortest possible route.


By loading the video, you agree to YouTube’s privacy policy.
Learn more
Load video
Always unblock YouTube

The complexity of such optimization problems usually leads to the circumstance that a global optimum can hardly be found. Therefore, the aim is rather to find a decent solution within a predetermined time period.

To give an example how problems of the above kinds can be tackled, I have made up a little example problem (which is much harder than the traveling salesman problem 🙂 ): the stacking challenge. (Python sourcecode: The stacking challenge ).

The stacking challenge

Five types of boxes are given, blue (0), red (1), yellow (2), green (3) and orange (4) in which the colors will be coded as indices. The vector of existing box types reads: \(B = \left[0, 1, 2, 3, 4\right]\).
We have a certain number of boxes of each type: \(N = \left[5, 10, 7, 9, 10\right]\).
Each box type has a height: \(H = \left[50, 70, 100, 110, 150\right]\).
Each box type has a weight: \(W = \left[50, 80, 30, 10, 100\right]\).
Each box type can carry a certain weight on top: \(T = \left[500, 1000, 2000, 600, 600\right]\).

Some stacking combinations are forbidden and will be coded as vectors. An example: If a red box cannot be stacked onto a blue box, we have \(f=\left[0,1\right]\). If a yellow box cannot be stacked onto a green box, we have \(f=\left[3,2\right]\). The forbidden combinations will be summarized as follows: \(F = \left[f_{1}, f_{2},..\right]\).
For the challenge, the forbidden combinations read: \(F = \left[\left[1, 3\right] (\text{no green on red}), \left[4, 1\right] (\text{no orange on red}), \left[0, 2\right] (\text{no yellow on blue}), \left[3, 0\right] (\text{no blue on green})\right]\).

The challenge: Build a stack as tall as possible, making sure that no box carries too much weight on top and that no forbidden combinations occur. Additionally, at least 10% of the boxes must be red.

Simplified version

We start out by investigating a reduced version of the problem:
\(B = \left[0, 1, 2, 3, 4\right]\)
Number of boxes of each box type: \(N = \left[2, 1, 1, 1, 1\right]\).
Height: \(H = \left[10, 20, 30, 40, 50\right]\).
Weight: \(W = \left[20, 30, 20, 50, 10\right]\).
Weight a box type can carry on top: \(T = \left[30, 20, 40, 40, 50\right]\).
Forbidden combinations: \(F = \left[\left[1, 3\right]\right]\) (no green on red).
Additionally: At least 10% of the boxes must be red.

In order to code this information, we first generate the so-called items vector, which holds all boxes we can choose from, ordered by index type. The items vector reads:
\(\text{Items_vector} = \left[0, 0, 1, 2, 3, 4\right]\), because we have two boxes of the type 0 and one box of each of the remaining types. Putting all constraints aside, a stack consists of an arbitrary subset of the elements of the items vector. Here, of course, the case of taking all elements is also included. Furthermore, the elements of this subset can be ordered in any manner. Here are some example stacks, in which the first element represents the box at the bottom: \(\left[0, 2, 3, 4\right]\) (blue, yellow, green, orange), \(\left[0, 0, 1\right]\) (blue, blue, red), \(\left[0, 0, 4, 3, 2, 1\right]\) (blue, blue, orange, green, yellow, red), \(\left[4\right]\) (orange).

1. Constructing a stack

To code this, we draw six random numbers between 0 and 1 (or some other range):
\(\text{Rand_vect}=\left[0.65, 0.76, 0.11, 0.52, 0.43, 0.90\right]\).
Now, we compute the indices that sort this vector,
\(\left[2, 4, 3, 0, 1, 5\right]\), and arange the elements of the items vector accordingly:
\(\text{Items_vector_ordered} = \left[1, 3, 2, 0, 0, 4\right]\) (red, green, yellow, blue, blue, orange).
Now we draw another random number between 1 and the the number of boxes which we can choose from, which is 6:
\(\text{Rand_num} = 3.2\). Rounding the number yields \(\text{Rand_num} = 3\).
Therefore, we build our stack from the first 3 elements of the ordered items vector:
\(\text{Stack} = \left[1, 3, 2\right]\). Using these two steps enables us to compute every stack possible. Moreover, the height of a stack is calculated as \(\text{Height} = \text{sum}\left(H\left[\text{Stack}\right]\right)\) which is \(\text{Height} = \text{sum}\left(\left[20, 40, 30\right]\right)=90\) in this example.

2. Avoiding forbidden orderings

At first, it makes sense to take some complexity out of the optimization procedure. In order to achieve this, we do not penalize for forbidden orderings, but we reorder our stack if necessary. As can be seen, the forbidden order \(\left[1, 3\right]\) is part our stack. Therefore, we exchange these two elements and arrive at the reordered stack: \(\text{Stack_reordered} = \left[3, 1, 2\right]\).
Reordering a stack is always possible, as long as no rules exists, so that two elements can never be stacked onto one another (Example: \(F = \left[\left[1, 3\right], \left[3, 1\right]\right]\)).

3. Checking for overweight

Now we check if a box carries excess weight. From the reordered stack, which holds the used box type indices, we can compute the weights used in the stack and the allowed top weights of the used boxes. Because the bottom box does not add top weight to any other box, the first element can be discarded: \(\text{Stack_weights} = W\left[\text{Stack_reordered}\left[1:\text{end}\right]\right] = \left[30, 20\right]\), \(\text{Stack_weights_allowed} = T\left[\text{Stack_reordered}\left[1:\text{end}\right]\right] = \left[20, 40\right]\). The cumulative weights computed from the vector \(\text{Stack_weights}\) are gathered in the vector \(\text{Stack_cumulative_weights} = \left[50, 20\right]\). So, the first box carries a weight of 50, the second a weight of 20 and the third, of course, no weight. Now we calculate \(\text{Precentage_overweight} = \left[\text{Stack_cumulative_weights}/\text{Stack_weights_allowed}-1\right]\) and keep only the results that are greater than 0 \((^{+})\). With these elements, we then compute \(\text{Weights_tester} = \text{mean}\left(\text{Precentage_overweight}^{+}\right)\). If no elements greater than 0 exist, it is \(\text{Weights_tester} = 0\). In the case where a stack has only one element, the whole procedure is skipped and we also have \(\text{Weights_tester} = 0\). In our example case, it is \(\text{Weights_tester} = 1.5\).

4. Checking for the percentage amount of red boxes

To test for the percentage amount of red boxes in our stack, we simply define:
\(\text{color_tester} = 1-\text{number_of_red_boxes_in_stack}/\text{number_of_boxes_in_stack}\). In the worst case, we have \(\text{Color_tester}=1\). As the percentage amount of red boxes approaches 10%, \(\text{Color_tester}\) approaches 0.9. From that point on, we set \(\text{Color_tester}=0\), as we then have fulfilled the minimum requirement. In our case, we have 33.33% of red boxes and so it is \(\text{Color_tester}=0\).

5. Decoupled optimization

Steps 1. – 4. constitute the function \(f\) which has the input variables \(\text{Rand_vect}\) and \(\text{Rand_num}\) as well as the outputs \(\text{Height}, \text{Weights_tester}\) and \(\text{Color_tester}\). We set \(\text{Test}=\text{Weights_tester} + \text{Color_tester}\) and define the overall result-function to be:

\(
\text{Result} =
\begin{cases}
\phantom{-} \text{Test} & \text{if}\ \ \text{Test} > 0 \\
-\text{Height} & \text{else}
\end{cases}
\).

It is very unlikely that the heuristic optimizer will generate a stack in the first iterations that satisfies the complex constraints. The used result-function decouples the constraints from the overall goal of maximizing the stack height. This means that the heuristic optimizer is first forced to satisfy the constraints, regardless of the height of the stack. From the moment the result-function is zero, it is ensured that the constraints are fulfilled. From then on, only the height of the stack plays a role. In this example the result function yields \(
\text{Result}=1.5\), which indicates that the constraints are not fulfilled yet.

Data

Below the data for the actual challenge is repeated:

\(B = \left[0, 1, 2, 3, 4\right]\)
Number of boxes of each box type: \(N = \left[5, 10, 7, 9, 10\right]\).
Height: \(H = \left[50, 70, 100, 110, 150\right]\).
Weight: \(W = \left[50, 80, 30, 10, 100\right]\).
Weight a box type can carry on top: \(T = \left[500, 1000, 2000, 600, 600\right]\).
Forbidden combinations: \(F = \left[\left[1, 3\right] (\text{no green on red}), \left[4, 1\right] (\text{no orange on red}), \left[0, 2\right] (\text{no yellow on blue}), \left[3, 0\right] (\text{no blue on green})\right]\).
Additionally: At least 10% of the boxes must be red.

As optimizer I have chosen the particle swarm algorithm (Python package Pyswarm). The resulting stack satisfies all constraints, has a height of 2770 and a percentage amount of red boxes of 15.38% (computation time approximately one minute). Can you construct a higher stack? If so, let me know. 🙂