Finding optimal placement of a 3D object in a partly filled 3D cage [closed]

Question

I am searching for a good optimization technique/algorithm for placing a somewhat arbitrary 3D shape in a cage already filled with 3D shapes.

These 3D shapes will primarily be regular cardboard boxes, but could include pretty much any shape and even soft polybags.

Suppose I was just looking for a way to keep the overall height of the highest package in the cage as low as possible. One possibility would be to discretize the cage, and then check each position, but if I at the same time also allow the package to be oriented/rotated arbitrarily, then that no longer becomes feasible since the number of possible placements would be far too high.

So in this case I need some sort of optimization algorithm that can handle what seems to me like a very discontinuous landscape. Has anyone ever heard of anything like this before? or know of any resources?

My own thinking is to calculate the amount of distance or overlap between the new package and existing packages. Legal placements are then only the placements where the distance is zero in multiple locations (meaning that the new package is touching old packages at at least 2 locations) and the overlap is zero. By formulating it in some way like this, I hope that the problem can be continuous and that I might be able to use a standard solver global/local solver setup.

Answer 1

I am searching for a good optimization technique/algorithm for placing a somewhat arbitrary 3D shape in a cage already filled with 3D shapes.

This is a very challenging bin packing problem.

You have not provided sufficient details to give a concrete answer and, anyway, I recommend against jumping right in and trying to solve this problem starting from a blank page.

I suggest finding the enclosing width, depth, height ( WDH ) object that encloses each of your arbitrarily shaped objects and then using a 3D bin packing algorithm to solve that.

If you find that the solutions you get have too much wasted space because there is too much wasted space inside each WDH approximation, but the solutions are otherwise adequate, then would be the time to look into extending the algorithm to handle various classes of odd shapes.

A good start is always the best fit first algorithm, here is some pseudo code introducing the best fit first bin packing algorithm. The idea here is to fit the largest objects into the smallest spaces, expecting that the smaller objects will later fit into gaps between the larger objects.

- Create a vector of spaces.
- Add the empty bin to the spaces vector
- Sort the items into order of decreasing volume
- Loop over sorted items
   - Loop vector of spaces
      - IF item fits into space ( rotated if necessary and allowed )
        - Add item to space
        - Split space into up to 3 WDH spaces remaining, add to space vector
        - Remove space used from space vector
        - Sort space vector into increasing volume order
        - BREAK from space LOOP
    - END space LOOP
- END item LOOP

For an implementation of this, you might check out https://codeberg.org/JamesBremner/PackEngine For your questions and suggestion on this algorithm, open an issue in that repository

You can find many other algorithms on the internet for 3D packing, from best fit first up to the most complicated algorithms you can imagine.

===========================================

the new package and existing packages.

This suggests that you are NOT looking for the global optimum packing, just the best pack of each item as it arrives. This makes the algorithm less complex, though the results are going to be terrible ;-)

I won't go into details about this here because your question has been closed.