Some time ago, my boss came to me and said that the warehouse personnel were having a hard time splitting big orders into many boxes, and then having to manually enter tracking codes into our e-commerce system. This had been happening for more than a year, and had never been mentioned to me, but it was obvious that it was something that could be solved (and it’s actually an interesting problem, yay!).
The company had some criteria for separating the items into distinct boxes (the main one being the weight of the items), so I just had to implement a function that would break each order into multiple packages in order to meet the company’s criteria. Everything was a success, but a few days later a report arrived saying that some orders were being split in too many boxes, and the company could lose money by paying more in shipping costs. Obviously, I went to check my code (which was correct, but could be improved), and, after some research, I came across the problem domain of bin-packing. I was unaware of this algorithm research domain (okay, I did not get my degree on Computer Science, but at university they only talked about ordering algorithms ;), and I was fortunate to find that the algorithm I had implemented was the worst of them (Next Fit)… I rolled up my sleeves, and decided to test the other most common algorithms to see what would work best for our business and bring us the best results.
In this article, I briefly introduce each algorithm, display a sample code in Scala (which I used to prototype), and the final algorithm implementation in PHP 7.2, which is the language we use in this e-commerce project.
Please excuse the quality of my Scala code - I’ve not mastered the language yet, and I opted for a solution with some mutability, since it was just a prototype.
First of all, I created a few classes to represent the itens and the bins. An item has a single property (weight), and a bin has also a single property (maxWeight), which represents the maximum combined weight of all items in a bin.
Then, I defined a list of 23 items with random weights, and the maximum weight of my bins (in this case, 100 units)(since the company is American, they use freedom units, a.k.a. pounds).
Nice. Now to the algorithms.
From Wikipedia, the bin packing problem is defined as:
“In the bin packing problem, objects of different volumes must be packed into a finite number of bins or containers each of volume V in a way that minimizes the number of bins used.”
This problem is NP-Hard, which means that it’s really hard and expensive to find the optimal solution, although some algorithms can produce near-optimal solutions with acceptable complexity.
On this algorithm, if the item fits in the same bin as the previous item, we put it there; if not, we create a new bin and put it in there. It also has a decreasing order variation (Next Fit Decreasing), where we order the items in descending order before packing them.
On this algorithm, we put each item in the first (oldest) bin into which it fits. It also has a decreasing order variation (First Fit Decreasing), where we order the items in descending order before packing them.
On this algorithm, we put each item into the emptiest bin that we have (if there are multiple bins, we put it into the first/oldest one). If the item doesn’t fit into any bin, we create a new one and put it there. It also has a decreasing order variation (Worst Fit Decreasing), where we order the items in descending order before packing them.
There exists other algorithms, and other variations of the aforementioned algorithms, but I have not considered implementing them - they are much more complicated.
Running my Scala worksheet with the items set I created before, I get the following results:
There’s a small difference between the best and the worst performing algorithms (if we ignore complexity), but when we drill it down to real world problems like shipping costs, the numbers start adding up fast and we can see why it’s important to minimize the number of bins.
After finishing the prototype, I choose the First Fit Decreasing algorithm, and I had to implement it for use on our PHP 7.2 codebase. For obvious reasons, I can’t share the original code (which also implements multiple constraints for the bin packing algorithm), therefore, I’m sharing a very similar version of what was implemented.
First, we do have our Item abstraction:
And our Bin abstraction:
Finally, we have our Bin Packing implementation:
Which is used like:
Not as beautiful as my twisted Scala code, but still pretty simple.
The full code is avaiable on GitHub: https://github.com/guhemama/bin-packing
I used to have Disqus enabled on my website, but I have disabled it because of privacy concerns.
If you feel like commenting or asking something, you can still contact me via other means.