Containers Loading Optimization with Python

How can we use heuristic algorithms to find the right strategy to load a maximum number of pallets in a sea container?

Article originally published on Medium.

With the recent surge in shipping prices due to container shortage, the price of a container from Shanghai to North Europe went from $2,000 in November to a peak of $12,000, and optimizing your container loading became a priority.

Scenario
You are Logistics Manager in an International Fashion Apparel Retailer and you want to ship 200 containers from Yangshan Port (Shanghai, PRC) to Le Havre Port (Le Havre, France).

• Retail value (USD): your goods’ retail value is 225,000$ per container
• Profit Margin (%): based on pre-crisis shipping cost your profit margin is 8.5%
• Shipping Costs — Previous (%): 100 x 2,000 / 225,000 = 0.88 (%)
• Shipping Costs — Current (%): 100 x 12,000 / 225,000 = 5.33 (%)

Your Finance Team is putting huge pressure on Logistics Operations because 4.45 % of profit is lost because of shipping costs. As you have limited influence on the market price, your only solution is to improve your loading capacity to save space.

💌 New articles straight in your inbox for free: Newsletter

I. Problem Statement

You have received pallets from your plants and suppliers in China ready to be shipped to France.

You have two types of pallets:

• European Pallets: Dimensions 80 (cm) x 120 (cm)

• North American pallets: Dimensions 100 (cm) x 120 (cm)

You can use two types of containers

• Dry container 20': Inner Length (5,9 m), Inner Width (2,35 m), Inner Height (2,39 m)
• Dry container 40': Inner Length (12,03 m), Inner Width (2,35 m), Inner Height (2,39 m)

Constraints

• European pallets and American can be mixed
• 20' or 40' containers are available
• No Pallet Stacking (put a pallet above another pallet)
• The loading strategy must be performed in real life (using a counter-balance truck)

Objective: Load a maximum number of pallets per container

II. Two-Dimensional knapsack problem applied to pallet loading

1. Two-Dimensional knapsack problem

Given a set of rectangular pieces and a rectangular container, the two-dimensional knapsack problem (2D-KP) consists of orthogonally packing a subset of the pieces within the container such that the sum of the values of the packed pieces is maximized.

2. Adapt it to our problem

If we consider that

• Pallets cannot be stacked
• Pallets have to be orthogonally packed to respect the loading constraints
• Pallets Height is always lower than the internal height of your containers

We can transform our 3D problem into a 2D knapsack problem and directly apply this algorithm to find an optimal solution.

3. Results

Scenario: You need to load in a 40' Container

• 20 European Pallets 80 x 120 (cm)
• 4 North American Pallets 100 x 120 (cm)

Tentative 1: The Intuitive solution

Comment: Your forklift driver tried to fit a number maximum of European pallets and find some space for the 4 North American Pallets.

Results: 20/20 Euro Pallets loaded, 2/4 American pallets loaded. You need another container for the two remaining pallets.

Tentative 2: The Optimization Algorithm Result

Comment: On the left, you have the solution based on the algorithm output.

Results: 20/20 Euro Pallets loaded, 4/4 American pallets loaded. You don’t need another container.

Conclusion

• The optimized solution can fit 100% of pallets. It’s based on non-intuitive placement that cannot be found without trying many combinations.
• Our filling rate is increased and pallets are more “packed”.

In the next part, we’ll see how we can implement a model to get this solution.

Edit: You can find a Youtube version of this article with animations in the link below.

III. Build your model

To keep this article concise, we will not build the algorithm from scratch but use a python library rectpack.

1. Initialize model and set parameters

• bx, by: we add 5 cm buffer on the x-axis and y-axis to ensure that we do not damage the pallets
• bins20, bins40: container dimensions by type

2. Build your Optimization Model

• bins: the list of available containers (e.g. bins = [bin20, bin40] means that you have 1 container 20' et 1 container 40')
• all_rects: list of all rectangles that could be included in the bins with their coordinates ready to be plot
• all_pals: the list of pallets that could be loaded in the containers listed in bins

3. Plot your result

• color: black for 80x120, red for 100 x120

Now you have everything to share your loading plan with your forklift driver :)

III. Conclusion & Next Steps

We increased the pallet loading rate in both examples vs. the intuitive approach.
This solution was based on a simple scenario of pallets that cannot be stacked.

Questions

• What could be the results if we apply it to stackable pallets?
• What could be the results if we apply it to bulk cartons?

About Me

Let’s connect on Linkedin and Twitter, I am a Supply Chain Engineer that is using data analytics to improve logistics operations and reduce costs.

References

[1] Python 2D rectangle packing library (rectpack), Github Documentation, Link