3
$\begingroup$

I am brain storming the best way to approach the following problem.

Problem: Load 100 given boxes of different types into the fewest number of trucks as possible, with the following details.

  1. 10 types of boxes (types A-J). Boxes have same length and width (2x2) but height can be 2, 4 or 6. Boxes cannot be rotated or tilted.
  2. All trucks are 100x20x20 (lwh)
  3. There’s a list of rules on how to stack boxes (i.e - type H cannot have any box on top of it, type J can only be stacked on top of types A-E, etc)

The best idea that comes to mind is using a form of the assignment problem in LP. Start with the min n number of trucks (total volume of boxes assuming no wasted space). If infeasible with n trucks, then try n+1 until feasible. I am wondering if this is the best approach. It feels a bit off to me since there isn’t really a meaningful objective function. Makes it seem like LP is wasted, but I cannot think of a better solution.

Someone mentioned the bin packing problem, but is there a way to track the location of each box in the bin? I am thinking of treating each bin as a 100x10x10 coordinate grid and then creating a "bin" for each coordinate block, but I feel like this is extremely overcomplicated.

$\endgroup$
2
  • $\begingroup$ Unless I'm missing something, this whole "Each truck has dimensions 100x20x20" parameter doesn't matter at all, and you could replace it with "Each truck can contain 1000 stacks of height 20" $\endgroup$
    – Stef
    Commented Oct 15, 2023 at 8:23
  • $\begingroup$ 500 stacks of height 20 yes. but there are rules to which box can stack on top of which, so you need a way to keep track of whether a box is on top of another. doing a 10x10 grid with 50 stacks of height 2 works to simplify though $\endgroup$
    – J. Doe
    Commented Oct 16, 2023 at 15:37

1 Answer 1

3
$\begingroup$

This is a variant of a three-dimensional bin packing problem.

If all boxes are identical squares, then packing stacks in trucks is trivial. What you just need is to build the least number of stacks. This is a variant of a one-dimensional bin packing problem, where the size of an item is its height and the size of a bin is the truck height.

To solve this one-dimensional bin packing variant, you can try:

  • A mixed-integer linear programming model
  • A column generation based algorithm. The subproblem will be a one-dimensional knapsack variant that should be solvable with dynamic programming or tree search
  • A sequential decomposition: while there remain unpacked items, build a new stack as full as possible. The subproblem is the same one-dimensional knapsack variant as for the column generation based approach.
$\endgroup$
5
  • $\begingroup$ As for the subproblem approaches, is it likely to produce a suboptimal solution because its only looking to pack one bin at a time? So if it packs the first 80 boxes efficiently but then the last 20 boxes cannot be stacked on each other, it ends up creating 20 bins for the last 20 boxes because none of them could stack with each other. One thing I could maybe add is create a "difficulty" variable for each box type based on its stacking limitations, and then have the algorithm prioritize "hard" boxes to be at the bottom. $\endgroup$
    – J. Doe
    Commented Oct 16, 2023 at 15:35
  • $\begingroup$ With MILP, do I need to create an assignment variable for each grid+type combination? So 5000 grid points (each a 2x2x2 cube) times 10 types, so a total of 50,000 assignment variables? and then use those variables to add the rules for stacking logic? or is there an easier way to formulate? $\endgroup$
    – J. Doe
    Commented Oct 16, 2023 at 15:38
  • $\begingroup$ @J.Doe For the MILP, yes. At first glance, I don't see a better formulation. You can decrease the number of grid points by finding a feasible initial solution first. $\endgroup$
    – fontanf
    Commented Oct 16, 2023 at 21:28
  • $\begingroup$ @J.Doe the column generation approach shouldn't be subject to the situation you described. The sequential decomposition, however, might. A classical way to handle this is to increase the profit in the knapsack subproblem of the items which are poorly packed and restart the sequential algorithm. This way, they should be packed earlier. $\endgroup$
    – fontanf
    Commented Oct 16, 2023 at 21:31
  • $\begingroup$ ok that makes sense. thank you for your input, i will try to put something together $\endgroup$
    – J. Doe
    Commented Oct 17, 2023 at 23:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.