The inspiration for this blog post lies at an article that I came across on the Dutch technology website tweakers.net. They announced that bol.com, the Dutch equivalent of Amazon, put a new multi-packaging machine into production. This machine is able to package multiple items into a single box and thus would lead to a reduction of packaging material and CO2 production.
In the comment section an interesting discussion started on the difficulty of the problem. It might surprise you at first but packing items into a box is a very hard task for Artificial Intelligence (AI). For those familiar with the term, the problem is NP-hard. This means that we do not have an efficient algorithm that will always find the optimal solution.
In other words, we only know the best solution after trying every possible outcome. If you then also consider every possible way you can pack a set of items into a box there is actually a large amount of options. There are many factors that play a role. For example, not only the order in which you put the items but also the orientation of these items matters.
To calculate the number of possibilities we can use the formula And even think about it if we only consider the order that we put the boxes in there are already n! options. That means that if we want to place seven items in a box we need to consider 7*6*5*4*3*2*1 = 5040 possibilities. Then let’s assume we can orientate each package in 4 different positions. That means we have to multiply that number by 4 giving 20.160 different ways of packaging the items. That is a lot of comparisons to make for just that single online order! And what about different boxes that we can use? That’s right the number of possible solutions that need to be checked is multiplied by the number of boxes that are available!
I think it is clear by now that the number of options to check, explodes as we need to pack more items. The scenario above also has a lot of simplifications. So in the real world we are dealing with even more possibilities and factors that we need to account for.
So how do we still manage to build such a packaging machine? First of all, let’s consider the practicalities. In reality, we don’t require a solution that guarantees we have the optimal packaging plan all the time. First and foremost, we want a machine that can quickly package the items! As long as we can find a possibility that can provide a better and faster packing ability than we humans can do ourselves.
This also holds for other problems in data science and AI, sometimes we must accept that we cannot guarantee the optimal solution because finding it is not practical. Even with modern computing power we may still need hours or days to calculate it. Imagine that the packaging machine takes a day to pack a single clients order just to make sure it is packaged in the best way possible?
Back to blogs