Packaging red boxes in blue boxes to optimize cost is challenging

Question

This is mainly a packaging problem: Suppose that there are 20 red boxes of various sizes r1 to r8 (so multiple of each size may exist), which are supposed to be shipped using blue packaging boxes which are available in 3 sizes b1, b2 and b3.

• Regardless of the weight, the shipping cost of a blue box b1 is cost1, for blue box b2, cost2 and accordingly for blue box b3 is cost3.

• We can use any number of blue boxes from any combination of sizes, however the goal is to minimal the shipping cost. So that means, if we consider placing multiple red boxes (of various sizes may be) in a blue box if they fit. We assume that the biggest red box can easily be fit in the blue box b1 As well the relation between cost1,..cost3 is as follows:

  cost1=2*cost2=3*cost3.

• For simplicity, we can pick arbitrary values to define the dimensions of each red box and same for blue boxes if needed.

Now what would be your approach to solve this problem?

Answer 1

To start you can use a treemap or a kd-tree, you can find an example here: http://www.blackpawn.com/texts/lightmaps/default.html. Maybe you can combine this with a bin-packing algorithm for example first-fit.