What I learnt whilst tackling the box packing problem for WooCommerce Shipping

Back in January we had several shipping methods for WooCommerce for getting quotes from APIs such as UPS, USPS and FedEx. Because these APIs expected ‘packages’ to quote on, it was necessary for items to be ‘packed’ into packages with a weight and dimensions.

The original extensions attempted to pack items by attempting to stack items to see how many items would fit into a box. This was not well received, and had several flaws:

1. Stacked items left ‘gaps’ in the box
2. Only one box size was supported – the box just grew to envelop all items..
3. ..or was pre-defined which lacked flexibility (any sized item would be shipped in that box)

Both the developer and I looked into solutions and this lead us to read about the BIN packing problem.

The BIN packing problem

If you want an overview of the BIN packing problem, see this wikipedia article. The basic gist of it is:

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 minimises the number of bins used.

Essentially, the problem is trying to pack multiple items into multiple boxes in the optimum way, so they don’t overlap, to reduce the number of boxes needed and to simulate how a human would pack the items.

You can imagine, with all the dimensions involved, and multiple methods in which you can arrange those objects, solving this problem is extremely complex and I’m not ashamed to say is way beyond my skill level. And thats just 2D, when you have a cube its even more difficult.

Admitting defeat and stepping back

After coding many concepts and much research it started to become obvious that this was a massive waste of time and effort.

1. A ‘perfect’ BIN packing algorithm would take too long to build and would be near impossible.
2. It would be very difficult to support.
3. Anomalies would be far too difficult to debug or explain away.
4. It would be extremely difficult to develop in the future should someone else take over.

Once I’d put my foot down and said BIN packing wasn’t a viable solution I went back to the drawing board to create my own simpler solution. These were the facts:

• We needed multiple pre-defined box sizes for maximum flexibility
• We had to check an item fit into a box at the very minimum to prevent erroneous results
• We had to pack all items into boxes before getting a quote
• The system needed to work across all shipping methods

The solution

After looking at whats needed, and understanding that erroneous results could be possible and should be understood I turned to a volume based solution in which:

1. Multiple defined box sizes are ordered by volume
2. Items are also ordered by volume
3. Items are looped, checked if they fit in the smallest box and packed until the box volume is full.
4. If an item doesn’t fit either another box is used, or a larger box is used.
5. If after all boxes are evaluated the item still doesn’t fit, the item is shipped individually.

This gives us an optimum set of packages based on item size and volume.

The code was built into a class which shipping methods can integrate and use pre-quote and this solution is now part of all WooCommerce shipping extensions (by WooThemes) and has been well received with much more accurate results than the original extensions. Job done 🙂

The moral of this story?

Don’t be afraid to stick to a simple, understandable solution. It’s really easy to get sucked into a complex problem which may or may not have a solution, or may require so much time and effort that its not worth it in the end if the end-result just gives a small increase in functionality or accuracy.

Keep it simple stupid.