You may have seen on this blog post that my fiancé and I found out in February that we could qualify for a mortgage. Well, fast forward two months, and we have purchased our first home! We are very very excited to move in, and we have already started *borrowing* (stealing) furniture from our relatives (hello grandma’s dining table).
But just the other day, while I was working on a report at my desk, it suddenly dawned on me – how on earth am I going to transport all my belongings to a new home? It should be said, I am a bit of a hoarder, and there is an entire wardrobe of art supplies that my parents are keen for me to take with me when I leave. Add to this my excess of fiction books, cuddly toy collection, and piano, and well… you’ve got a lot of things to transport 15 minutes down the road (you heard that right, I am moving a 15 minute drive away from my childhood home).
It turns out that packing problems actually constitute a well-studied area of optimisation. Often, in places like warehouses, the ability to effectively pack items of various sizes into a finite number of containers is vital to the smooth running of operations. Warehouse packing algorithms attempt to solve these kind of problems, by optimising the packing of items in day to day operations.
So what kind of packing problem is this?
The ‘bin packing problem’ is perhaps the most relevant description of my ‘dear lord how will I transport my cuddly toy collection‘ issue. Essentially, it refers to the problem of how best to pack multiple items of various sizes into a finite number of bins (or containers). Like most optimisation problems, it’s all about trying to find the best possible solution out of all the feasible solutions.
What do you think would give the best solution?
I think most people, when asked for the most optimal way to pack all my cuddly toys up, would suggest trying to fit as many cuddly toys as I can into one bin. And this would be a very good suggestion! This is what I love about operational research, you don’t need to know lots of fancy mathematical theory in order to have a good idea about how to solve a problem.
Generally speaking, the best solution for a bin packing problem can be one of two things:
- Packing one container as densely as possible
- Packing all objects into the least amount of packages as possible
Both of these solutions have very clear objectives: minimising cost. In some shipping companies, it is common that items will get charged for the amount of space they take up, rather than the weight. Hence, packing a container very densely is the best option.
Also, clearly reducing the amount of packages used reduces packaging costs.
Computational Complexity
if you’ve come across some form of optimisation problem before, you may have heard the term ‘computational complexity’ being thrown about. The computational complexity of a problem may sound scary, but in actual fact it can just be thought of as how many resources are required to solve the problem (maybe the resources are the time taken, or the data storage required).
When you measure how long a program takes to run when it is given more and more difficult problems (for example, packing 10 cuddly toys, then 20 cuddly toys, then 30 cuddly toys etc) you can plot the times and come up with a function.
In the case that the time taken increases exponentially or factorially (or anything that exceeds what a polynomial can do!) as the difficulty of the problem increases, we say that the problem is not solvable in polynomial time.
The bin packing problem is known as an NP-complete problem. This stands for ‘non-deterministic polynomial time’. This means that it is not solvable in polynomial time. In simplest terms, this kind of just means that if we increase the number of items that need to be packed, even by a little amount, then the problem takes wayyyy longer to solve.
A cool fact about NP-complete problems, is that if anyone could ever solve an NP-Complete problem in polynomial time, then we could solve all NP-complete problems in that way using the same method. This would mean that the entire class of NP-complete problems would cease to exist!
Standard Bin Packing Algorithms
So what are the different types of bin packing algorithms that exist?
Next fit: For this bin packing algorithm, I check if an item fits into the box that I am currently filling. If it does fit – great! I will add it to the box. If it doesn’t, I seal up the current box, ready to be transported to the new house, and I begin filling the next one. A benefit of this algorithm is that I can send the sealed boxes over to the new house one after another, so I am never required to pack more than one box at the same time – this helps save bedroom floor space while I pack!
First fit: For this algorithm, let’s imagine I have four boxes lined up on the floor, ready to be packed. Here, I take an item and I see if it will fit in the first box. If I does, I place it in, whereas if it doesn’t, I move onto the next box. I continue this down the row of four boxes, until I find one that works.
Worst fit: Imagine now that I have partially filled several boxes with items. For this algorithm, I will place my current item into the box with the least amount of items (as though I am trying to even the weight between all the boxes). If I have two equally empty boxes, I’ll put the item in the box that I started to fill first.
The above algorithms are known as online algorithms; they are used when items arrive one at a time, in an unknown order. In these algorithms, we must put the current item into a container before we consider the next item. Each algorithm has an associated runtime complexity, describing how the time taken for the algorithm to run scales with the number of items to be packed n. Ideally, we prefer algorithms with a lower runtime complexity, because this means that the algorithm performs quicker if it has to pack lots of items! But remember, we also want algorithms that give us good approximations to optimal solutions, so which you use depends on the situation.
Other algorithms exist for offline situations, where we have all the items available upfront (like my moving house case!). I won’t cover some of these here, but check out the further reading if you’d like to know more.
So there we have it!
I hope you enjoyed this small introduction to optimisation and bin packing algorithms. In reality, I may not use a bin packing algorithm to help pack my belongings in advance of moving day, but in the world of warehouse management, bin packing algorithms are really important. Many companies use 3D bin packing software to help optimise their operations.
There are several variations on general bin packing problems; for example, the classic optimisation problem known as the Knapsack problem. In the Knapsack problem, we have one bin, and our items are characterised by a value and a weight. Our goal is to maximise the value of the items that can fit into the bin.
If you did enjoy this post, and would like to read more, I’ve listed some great resources for further reading below!
- This Wikipedia post on the bin packing problem gives a great introduction, and goes into some more detail on the algorithms.
- If you’re interested in actually implementing some of these algorithms, I love this Geeks for Geeks post, which describes how to code up all the algorithms discussed in this report in several different languages.
- This post is a great, easy to read description of how bin packing algorithms help warehouse operations.