Solver Max - Warehouse space for free: Exogenous enumeration

27 March 2024

Warehouse shelves

We conclude our project to improve the efficiency of a pallet warehouse by redesigning the warehouse's racks and shelves.

In part 2 of this article series, we linearized our warehouse racks and shelves design model with the hope of making it easier to solve at the full scale we need. It didn't work. Model 2 is even slower than the non-linear Model 1 we built in part 1.

In this article, we simplify our modelling by taking some of the variables out of the model and making them exogenous inputs. We enumerate all possible combinations of those exogenous inputs, then solve the simplified model for each combination. Hopefully, this time, our model will be solvable at the scale we need.

Download the models

The models described in this series of articles are built in Python using the Pyomo library.

The files are available on GitHub.

Situation

The situation is described in the first part of this series: Warehouse space for free: Non-linear model.

Model 3 design

Simplify the modelling

We think the main problem with Models 1 and 2 is that they have too many moving parts. The non-linear Model 1 works well for small and intermediate size data sets, but not for the full data set size we need. The linearized Model 2 has worse performance at all scales. Neither model finds an optimal solution, or even a good solution, with the full data set. Perhaps simplifying the model will help?

Models 1 and 2 do the following:

Decide the number of shelves per rack.
Decide the height of each shelf such that each rack is exactly 6.0m high.
Determine the number of racks needed.
Pack the pallets into the racks and shelves.

We make some observations about the first two requirements:

Realistically, the number of shelves per rack is an integer from 6 to 9, inclusive. This is a very small set of possibilities.
Given the number of shelves per rack, there is a limited number of shelf size combinations that sum to exactly 6.0m (including the gaps between shelves). Again, this is likely to be a manageably small set of possibilities.

So, we can take the first two decisions (number of shelves per rack and the height of each shelf) out of the model, making them exogenous data. To do that, we need to enumerate all possible rack/shelf designs – that is, combinations of shelf heights given the number of shelves per rack, such that the racks are the required height. Then we can solve each combination separately. Our model then just needs to decide how many racks are needed to pack all the pallets, given a specified rack and shelf design.

This approach assumes, firstly, that there is a reasonable number of possible designs and, secondly, that the simplified model solves in a reasonable time. We'll need to implement the model before we'll know if the solve time is reasonable.

Enumeration criteria

We start with enumerating the possible rack/shelf designs.

There are 5 shelves in the current rack design. To improve the efficiency of the design, we must have more shelves per rack. But the more shelves per rack, the more space is consumed by the gap between shelves (which includes the shelf itself and the vertical height needed for manoeuvring the pallets into and out of a shelf).

That is, the current design has 5 shelves of height 10 decimetres. Including 5 gaps of 2 decimetres, the total rack height is 5 * 10 + 5 * 2 = 60 decimetres. We can't have 4 shelves of 10 decimetres and a fifth shelf of a different height, as the rack would not be 60 decimetres high. Therefore, we can have, at most, 3 shelves of 10 decimetres high each with the other shelves being smaller. We also know that each shelf must have storage space at least 2 decimetres high, as that is the smallest pallet height.

In summary, the enumerated designs must meet the following criteria:

Have between 6 and 9 shelves per rack.
Up to 3 shelves that are 10 decimetres high.
Minimum shelf storage height of 2 decimetres.
Gap of 2 decimetres between shelves.
Total rack height equals 60 decimetres.

Enumerated designs

We wrote a simple program to enumerate all possible shelf designs that meet the criteria. The designs are listed in an Excel file. The first few lines are shown in Figure 1, where the first row is the number of shelves, and the other rows are shelf heights in decimetres.

Ignoring designs that have the same shelf sizes in a different order, it turns out that there are only 158 possible designs that meet the criteria. This is good, as it isn't too large a number. Figure 2 shows the number of shelf designs for each number of shelves per rack.

Figure 2. Shelf designs

Model 3 formulation

Having removed decisions about the number of shelves per rack and the shelve sizes, the simplified formulation for Model 3 is shown in Figure 3.

Compared with Models 1 and 2, we've removed a couple of variables and several constraints. This model is much simpler than Models 1 and 2, with fewer moving parts. It is also linear, which should help too.

The key parts of the formulation are:

Equation (1). The objective function is to minimize the number of racks needed to store the pallets. This is the same as for Model 1, though the number of shelves is now an input rather than a variable.
Equation (2). Each pallet must be allocated to a shelf that is at least the height of the pallet. The shelf heights are now inputs rather than variables.
Equation (3). Each pallet must be allocated to exactly one shelf.
Equation (4). For each shelf, the allocation must be within the number of available slots.

Figure 3. Model 3 formulation

\begin{alignat}{1} &\text{Objective}\\ &\quad \text{Minimize} \quad Objective \quad &= &\quad \text{WeightRacks} \times Racks \\&&&\quad + \ \text{WeightShelves} \times \text{NumShelves} \tag{1} \\ \\ &\text{Subject to} \\ &\quad \text{Pallets}_{p} \quad &\le &\quad \sum_{s=1}^{n} \text{ShelfHeights}_{s} \times Allocation_{p, s} \quad &\forall \ p \in P \tag{2} \\ &\quad \sum_{s=1}^{n} Allocation_{p, s} \quad &= &\quad 1 \quad &\forall \ p \in P \tag{3} \\ &\quad \sum_{p=1}^{m} Allocation_{p, s} \quad &\le &\quad \text{PalletsPerShelf} \times Racks \quad &\forall \ s \in S \tag{4} \\ \\ &\text{Variables} \\ &\quad Racks \quad &= &\quad \text{Number of racks, positive integer} \tag{5} \\ &\quad Allocation_{p, s} \quad &= &\quad \text{Allocation of pallets to shelves, binary} \quad &\forall \ p \in P, \forall \ s \in S \tag{6} \\ \\ &\text{Data} \\ & \quad \text{WeightRacks} \quad &= &\quad \text{Objective weight for number of racks} \tag{7} \\ & \quad \text{WeightShelves} \quad &= &\quad \text{Objective weight for number of shelves} \tag{8} \\ & \quad \text{NumShelves} \quad &= &\quad \text{Number of shelves in a rack} \tag{9} \\ & \quad \text{Pallets}_{p} \quad &= &\quad \text{Height of each pallet} \quad &\forall \ p \in P \tag{10} \\ & \quad \text{PalletsPerShelf} \quad &= &\quad \text{Number of pallets on each shelf} \tag{11} \\ & \quad \text{ShelfHeights}_{s} \quad &= &\quad \text{Height of each shelf} \quad &\forall \ s \in S \tag{12} \\ \\ &\text{Sets} \\ & \quad P && \quad \text{Pallet} \tag{13} \\ & \quad S && \quad \text{Shelf} \tag{14} \\ \\ &\text{Dimensions} \\ & \quad m && \quad \text{Number of pallets} \tag{15} \\ & \quad n && \quad \text{Number of shelves} \tag{16} \\ \end{alignat}

Model 3 implementation

The essence of Model 3 is that we iterate over the 158 designs, solving each design for the minimum number of racks needed to store all the pallets.

The code for this iterative approach is straightforward. We simply wrap a loop around the process we used for Model 2, though using Model 3's formulation, print each solution, and note the best solution found so far. At the end of the process, we print the best solution found.

For example, using the intermediate test data with 2,000 pallets, part of Model 3's output is shown in Figure 4.

Figure 4. Model 3 test with 2,000 pallets

Case   1, shelves =  10,  10,  10,   9,   7,   2,   0,   0,   0, obj =    90.6 *
Case   2, shelves =  10,  10,  10,   9,   6,   3,   0,   0,   0, obj =    84.6 *
Case   3, shelves =  10,  10,  10,   9,   5,   4,   0,   0,   0, obj =    84.6
Case   4, shelves =  10,  10,  10,   9,   3,   2,   2,   0,   0, obj =    97.7
Case   5, shelves =  10,  10,  10,   8,   8,   2,   0,   0,   0, obj =    90.6
...
Case 158, shelves =  10,  10,   4,   3,   3,   3,   3,   3,   3, obj =   160.9

Best objective =    74.7
Case  82, shelves =  10,  10,   8,   6,   5,   4,   3,   0,   0, obj =    74.7

For this test data, using Model 3, Gurobi solves the cases to optimality in around 1 second each, for a total run time of less than 2 minutes for all 158 cases. This is very promising, because Gurobi took almost 8 hours to solve the same data to optimality using Model 2.

The best solution for 2,000 pallets is 74.7, meaning that we need 74 racks, each with 7 shelves. This is the same solution found by Models 1 and 2. The key difference is that running all enumerated cases through Model 3 is more than 200 times faster than running Model 2 once.

Model 3 solutions

Solution for full data set

We can now apply Model 3 to the full data set of 20,000 pallets. It takes Gurobi half an hour to run all 158 design cases. For comparison, the HiGHS solver takes over 3 hours.

The result is that the best design has 733 racks, with 7 shelves of heights 10, 10, 8, 6, 5, 4, 3 decimetres (with a 2 decimetre gap per shelf, the total rack height is the required 60 decimetres, 6.0m). Since we input an enumeration of all possible rack designs, this is an optimal solution to our original problem.

Figure 5 summarizes the results for the three data sets, using Model 3.

Figure 5. Solutions for Model 3

Observations about the optimal solution

Model 3 scales much better than Models 1 and 2, so the run time for the full data set is vastly better. Importantly, unlike Models 1 and 2, we get an optimal solution for Model 3 in a reasonable time.

Model 3 tells us that, using the optimal design of 7 shelves per rack, we need 733 racks to pack the 20,000 pallets. This is a 26.7% reduction, compared with the 1,000 racks needed for the current design.

The best design from Model 3 for 20,000 pallets is the same as the design found for the test data of 2,000 pallets. This is a coincidence. Although the best design for the sample of 2,000 pallets will be a good solution for the full data of 20,000 pallets, there is no guarantee that it will be optimal.

In the 158 enumerated designs, there is only one solution that uses 733 racks. There are four different designs that require 745 racks. Having those "next best" designs is useful, in case one of them is preferable for reasons the model doesn't know about.

Note that 733 racks * 7 shelves per rack * 4 pallet slots per shelf = 20,524 slots. Therefore, we have more shelf space than is needed for our 20,000 pallets. The surplus shelves provide some storage flexibility. Having more slots than necessary is useful, in case the distribution of pallets to be stored at any given time differs from the data we used to determine the optimal design.

Overall, the new design improves storage efficiency by 40%. That is, each rack can store 28 pallets (7 shelves * 4 slots per shelf), rather than the current design of 20 pallets (5 shelves * 4 slots per shelf).

We also note that, in theory, it might be possible that 7 shelves per rack could produce a solution that requires as few as 715 racks (that is, 715 * 7 * 4 = 20,020 slots). However, our specific distribution of pallet sizes makes it impossible to use fewer than 733 racks.

Finally, if we allow more than one rack design, then it is possible that we could further reduce the number of racks. However, the potential gain is relatively small, at around 1% to 2%.

The new rack design requires changes in warehouse management

The rack design with 7 shelves reduces the number of slots where a specific pallet may be stored. For example, with the current design, a 1.0m high pallet can be stored in any of the 20,000 slots on the 1,000 racks. With the optimal solution of 733 racks, only 5,864 slots (= 733 racks * 2 shelves per rack * 4 slots per shelf) are high enough to store a 1.0m pallet.

This reduction in available slots for each pallet size is OK because, for example, we have only 4,406 pallets that are 1.0m high. But some of the 1.0m high slots may be used to store smaller pallets, so the positioning of pallets on shelves of appropriate size will need to be carefully managed. In particular, the warehouse staff will need to ensure that they use the smallest slot that fits a given pallet. Currently, after unloading product from a pallet, the pallet is generally placed back in the same slot. With the new design, pallets may need to be stored in a different slot that is better suited to its new size, rather than occupying a slot that is larger than necessary.

Recommendation

We finally have an optimal solution for the full data set. Consequently, we make a recommendation to change the rack design to have 7 shelves of sizes 10, 10, 8, 6, 5, 4, 3 decimetres. This design requires 733 racks (a decrease on 26.6%). With the number of racks reduced from 1,000 to 733, floor space can be made available for other purposes.

For the recommended design to work in practice, we need to have a reasonable number of empty slots. The proposed design has a capacity of 20,524 slots (a 2.6% increase over the current warehouse capacity of 20,000 pallets). This additional capacity will alleviate the current over-capacity issue.

Final decision

Given the information gained from the modelling, the Warehouse Manager makes a decision. Rather than implementing the minimal design of 733 racks, the Warehouse Manager chooses to have 850 racks (15% decrease relative to the current 1,000 racks). This gives a total of 850 * 7 * 4 = 23,800 slots (19% increase), compared with 20,000 slots currently. Note that this split of 15% fewer racks and 19% more slots is equivalent to a 40% increase in efficiency: (1 + 19%) / 85% - 1 = +40%.

The Warehouse Manager explains this decision as follows:

Having 850 racks of the recommended design is a 19% increase in capacity, relieving the current over-capacity issue and allowing for some additional growth, so the Warehouse Manager is happy.
All pallets, and then some, can be stored on the racks, rather than pallets being stored in the Dispatch area – where they are a hazard. Consequently, the Health & Safety Manager is happy.
The 15% decrease in the number of racks releases floor space to expand the area for handling inward and outward products, so the Packaging & Delivery Manager is happy.
A larger warehouse is not needed, and the rack/shelving changes are relatively cheap, so the business owner is happy.

It is possible that the optimal solution of 733 racks is not the best solution for a warehouse of 850 racks, as that is a different situation. But the difference, if any, is unlikely to be material.

In any case, from our point of view, the project has been delivery successfully. Our modelling has been used to inform a decision that leads to better outcomes – which is the purpose of modelling. So, we're happy too.

Lessons from this modelling

There are several lessons that we can learn from this modelling of a warehouse's racks and shelves:

If a model takes more than a few seconds to solve, then use a toy data set during development. While building and testing a model, you'll likely run it many times. Fast models save a lot of time during development. For this project, most of the model development was done using a 1% sample of the data.
Solve times can increase rapidly as data size increases. A model that is easy to solve at a small scale can become impossible to solve at a larger scale. Progressively scaling up the data size can provide insights into solve time behaviour. That was certainly the situation here, where we had difficulty solving the full data set, even with a commercial solver.
Try to avoid doing too much in a model. Models 1 and 2 don't work well because they have too many moving parts.
Simplifying a model can improve performance by a massive amount. Model 3 is more than 200 times faster than Model 2, even though both models are linear.
Taking some variables out of the model can be helpful. For example, explicitly enumerating a reasonably small number of variable combinations can be better than leaving the solver to figure it out.
There is only a small incremental gain from solving the full 20,000 pallet data set compared with the intermediate 2,000 pallet data set. That is, 733 racks compared with 740 (74 optimal solution from Model 2, scaled up to be comparable). In this case, the effort required to implement Model 3, once we had Model 2, was also small, so the effort was worthwhile. But sometimes we may just have to accept an approximate solution based on a sample of data.
The decision maker might be trying to solve more than one problem at a time, considering aspects of the situation that are outside the scope of the model. For example, in this situation, dealing with health and safety issues and increasing the size of the inward and outward handling area.
Remember that the purpose of modelling is to inform decision making. The resulting decision may not be exactly what the model is designed to do. Even so, the goal should be to make the modelling useful.

Conclusion

In this article, we simplify our model by converting some variables into exogenous inputs. We enumerate the combinations of the exogenous inputs and solve each case independently.

The result is a great performance improvement. For the full data, we were unable to find good solutions with Models 1 and 2 even after 8 hours of run time. But with Model 3, we find an optimal solution for the full data in under an hour.

The new rack and shelf design is 40% more efficient than our current design, which is a substantial gain. The Warehouse Manager decides to use the new design in a layout that increases capacity by 19% while reducing floor space usage by 15%. This is a great result, so everyone is happy with the new design.

As a followup, we've implemented a version of this model that runs the cases in parallel rather than serially. See 10 times faster, running cases in parallel.

If you would like to know more about this model, or you want help with your own models, then please contact us.

Warehouse space for free: Exogenous enumeration