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.
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)
- 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.
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.
- 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.
- 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.
- What could be the results if we apply it to stackable pallets?
- What could be the results if we apply it to bulk cartons?
 Python 2D rectangle packing library (rectpack), Github Documentation, Link