Optimizing E-commerce: Solving the Bin Packing?Problem
The Bin Packing Problem (BPP) is a classic optimization problem with applications in a wide range of industries, including commerce, logistics, transportation, manufacturing, and distribution. The objective of the BPP is to pack a set of items into a minimum number of bins, each of fixed capacity, such that the total weight or volume of the packed items does not exceed the capacity of any bin [1][2].
Imagine you have a truck to deliver all the pipes, valves, and fixtures to a construction site. The bin packing problem is how to fit all these items into the truck while minimizing wasted space and ensuring that the weight limit is not exceeded. It’s like Tetris in real life, but instead of colorful blocks, you’re packing items into bins.
Doing this efficiently takes a lot of Math. But is it even worth solving?
Why is this important
An optimal bin packing strategy can save money, improve efficiency and reduce environmental impact in a variety of real-world applications, particularly B2B and B2C hard goods manufacturers and distributors.
Efficient packing and shipping are critical to reducing transportation costs[3] and maximizing profit margins, which is especially important in the highly competitive e-commerce industry. By using BPP algorithms, these businesses can determine the optimal number of boxes required for each shipment of raw materials or bulk products. This will allow an effective way to pack each pallet in the container or truck to minimize unused space and reduce the overall volume of the shipment. This not only reduces transportation costs but also minimizes the environmental impact of shipping by reducing the number of trips required to procure the same number of products.
Moreover, the BPP can help e-commerce businesses streamline their warehouse operations by optimizing the use of storage space. Knowing how to utilize and optimize space to the fullest potential is critical to realizing an efficient and well-balanced warehouse[4]. By using BPP algorithms to pack products into storage bins, businesses can maximize the use of available space, reduce the time required to retrieve products, and minimize the need for additional warehouse space. This can result in significant cost savings, particularly for businesses that operate in densely populated urban areas where space is at a premium.
Furthermore, the BPP can be used to optimize order fulfillment operations in e-commerce businesses by packing multiple orders into a single box or calculating the optimal shipping box sizes. Businesses can reduce the number of shipments required and minimize the time and cost associated with picking and packing individual orders [5]. This can also lead to improved customer satisfaction by reducing the time required for product delivery.
For technical details on how to solve the problem, see my full article in towardsai.com
Where do we use?it
At AAXIS, we deal with the Bin Packing Problem in various situations. Some examples are consignment goods storage, custom truck and rail car packing, and customer shipments. While there are commercial tools available to solve the bin packing problem, some cases warrant implementing a customized and tweaked algorithm.
For consignment goods storage at client warehouse locations, we use a customized Guillotine Algorithm. The algorithm attempts to stack similar items on top of each other to facilitate easy access. Consignment inventory can add breadth and depth to the manufacturer’s market opportunity and increase sales and profits [9].
For custom truck packing shoppers use a visualization tool to add items to a truck and see it filling up. It displays results in real-time, so online shoppers can be confident that they will receive the goods they ordered and that they are fully leveraging the truck that they paid for. The algorithm is designed to be implemented in an ORO Commerce Cloud environment and produces quick graphical results for the shoppers.
A rail car packer application uses a generic version of a Maximal Rectangle Algorithm with special restrictions on proximity placement as chemicals are being transported. In addition, we use a genetic algorithm to optimize the placement further by starting with the above results as an initial population and then iterating over it until better results with less space wastage are found.
A customer shipment packer application uses a fast version of the Shelf Algorithm which tells the order-picking staff how best to place the items in the shipping box, without knowing any other boxes coming down the belt bound to the same location. We use a slight optimization to recommend placing the item on a bottom shelf if the algorithm detects that the space is accessible.
Finally, we use a full Brute-force implementation for Ship container optimization as the contents of the container and their dimensions are known well in advance. Since most of the items on the container are pallets, we can run the simulation offline and store the most optimal solution to be used by the loading crew. While this might seem like an overkill, it’s really worth the effort considering the cost of container shipping and readily available power from cheap cloud computing units.
领英推荐
At AAXIS, we believe that knowing these algorithms in depth helps with understanding the cost vs benefit of picking one algorithm over the other. It is surprising how many developers will simply pick a ready-made app or library to perform this task, without understanding the implications, when there are millions of dollars at stake.
Conclusion
In this short article, we looked at the definition of the Bin Packing Algorithm and why it is crucial for us to solve. The BPP is a critical tool for e-commerce businesses looking to optimize their operations and reduce costs. By using BPP algorithms, businesses can efficiently pack and ship products, optimize warehouse space utilization, and streamline order fulfillment operations. This, in turn, can help businesses remain competitive in the highly competitive e-commerce industry and provide better value to their customers, all while reducing the impact they have on the environment.
Contributors
I would like to thank my colleagues for their contributions to the research that informed this article. Their expertise and insights were invaluable to the project.
Here is the list of the colleagues at AAXIS Digital, in last name alphabetical order:
I would like to acknowledge the contributions of ChatGPT and Bard in rephrasing some of the text in the article to make it easy to follow.
Also thanks to my editor, Megan Polstra, for making the article look and feel professional as always.
References
[1] Jylanki, Jukka (2015), “A Thousand Ways to Pack the Bin — A Practical Approach to Two-Dimensional Rectangle Bin Packing”, https://pds25.egloos.com/pds/201504/21/98/RectangleBinPack.pdf
[2] Various Authors (2023), “Bin packing problem”, Wikipedia, https://en.wikipedia.org/wiki/Bin_packing_problem
[3] Russell, Dawn; Coyle, John J.; Ruamsook, Kusumal; Thomchick, Evelyn A. (2014) “The real impact of high transportation costs”, CSCMP’s Supply Chain Quarterly, https://www.supplychainquarterly.com/articles/838-the-real-impact-of-high-transportation-costs
[4] Engeler, James R. (2021), “Space Optimization in warehouses”, University of Wisconsin, Seminar Paper. https://minds.wisconsin.edu/bitstream/handle/1793/82578/Engeler.%20James.pdf?sequence=1&isAllowed=y
[5] Optioryx (2023), “Choosing The Shipping Box Dimensions That Fit Your Order Profile”, Medium, https://medium.com/@optioryx/choosing-the-shipping-box-dimensions-that-fit-your-order-profile-729a3ea01de7
[6] Moussa, Ahmad (2021), “Rectangle Packing: An Incredibly Difficult Problem”, Gorilla Sun, https://gorillasun.de/blog/rectangle-packing-an-incredibly-difficult-problem
[7] Martello, Silvano; Toth, Paolo (1990), “Bin-packing problem — Knapsack Problems: Algorithms and Computer Implementations”, Chichester, UK: John Wiley and Sons, https://www.or.deis.unibo.it/kp/Chapter8.pdf
[8] Sharma, Prashant (2022), “Knapsack Problem in Python”, Analytics Vidhya, https://www.analyticsvidhya.com/blog/2022/05/knapsack-problem-in-python/
[9] Nicasio, Francesca (2022), “What is Consignment Inventory and How Does It Work?”, Vendhq Blog, https://www.vendhq.com/blog/consignment-inventory/