2D箱包装，在容器中有预定义的间隙 [英] 2D bin packing with predefined gaps in container

问题描述

我在将不同大小和数量的矩形对象最佳放置在矩形容器中时遇到问题。该问题可以使用2D装箱算法之一完美解决，但只能在空容器上进行。对我来说，这几乎总是一个案例。我的容器可以在有限的地方放置任何物体。

它会生成类似如下的包装：

等。其中有很多，它们都是毫无意义的，因为这无关紧要（对于主问题的目标值，当考虑整数约束时） 1x3块在哪里，那么包装包含一个1x3件和14个1x1件就很重要。

因此，理想情况下，约束4将由更复杂的东西代替，从而禁止包装 ，但是其他最有效的方法是首先尝试使用high分支。

在此示例中，在添加允许主问题最优的列之后（但仍然是分数，在任何情况下，分支），则目标值为5.5882352941176467。那已经意味着我们知道我们至少需要6个容器，因为这是最优的小数值，证明不能用5来完成，并且分数的容器不是一个选择。

很快找到了一个包含6个容器的解决方案，即

其中三个：

其中一个：

打包所有碎片，再加上1x4碎片和3 x 1x1碎片。

此算法与碎片或容器的形状没有太大关系，除了必须将它们表示为网格上的单元格。容器的整个位置都可能有孔，碎片可能更像俄罗斯方块碎片，甚至有断开的部件。缺点是，所需的展示位置列表会随着容器的大小严重缩放。

I have a problem with optimal placing of rectangular objects with different size and amount in rectangular container. The problem can be perfectly solved with the one of 2D bin packing algorithms but only on empty container. For me it is almost always not a case. My containers can have a restricted places where no object can be placed. Packing example

Surely I am not the first one who encountered this kind of problem and I hope someone already developed a good solution for it. Anything is good: book references, articles, code snippets, etc. Formal algorithms are prefered upon neural networks and this kind of things.

解决方案

One possible way to solve it is with integer linear programming. There are different models but here is a simple one (with a bit of an issue, but you can improve on this if necessary).

Split the problem into a master problem and sub problems, with the master problem looking like this:

minimize sum(p)
s.t.
for all i: sum[j] p[j]*count[j,i] >= n[i]
p[i] >= 0 (and integer, don't add this constraint)

Where:

• p are the decision variables, deciding how many instances to use of a particular "packing" of the available items into the container. There are obviously way too many of these to list in advance, but they can be generated dynamically.
• count[j,i] is the number of times that packing j contains item i.
• n[i] is the number of times we want item i.
• the constraints are >= because packing a couple extra items is OK and it lets us use fewer different packings (otherwise the master problem would need special "deliberately subobtimal" packings to be able to fulfill the constraint).
• the integer constraint shouldn't be added explicitly if you're using a solver, because an integer solution may need columns that were not needed yet in the fractional solution.

Start with a couple of dumb packings for each item so that there definitely is some solution, bad as it may be. You can even just place one item in the container which is trivial to do even without using the solver for the sub problem, but the sub problem has to be solved anyway so you may as well reuse it here.

The sub problem is finding out what packing can be made that would improve the current solution that the master problem has. So take the dual costs of the rows of the master problem C (there are as many as there are different kinds of item) and solve

maximize y.C
s.t.
1) for all i: y[i] <= n[i]
2) for all i: y[i] = sum[j] P[j] if j is a placement of item i
3) for all cells (a,b): sum[j] P[j] (if j covers a,b) <= 1
4) for all existing packings e: e.y <= sum(e) - 1
y >= 0 and integer
P boolean

Where,

• y are implied variables that follow from a choice for P, y[i] is how many times item i occurs in the packing.
• P are the real decision variables, deciding whether or not to use a particular placement of a particular item. There are 62 different item-placements in your example problem, including rotations.
• constraint 1 ensures that a packing can actually be used in an integer solution to the master problem (using too many of an item would doom the corresponding variable to be fractional or zero).
• constraint 2 links y to P
• constraint 3 ensures that the solution is a valid packing, in the sense that items do not overlap each other.
• constraint 4 is necessary to avoid re-creating a column that was already added to the master problem.

Re-creating a column wouldn't happen if the master problem was a regular linear program, but it's an integer program and after branching constraint 4 needed to explicitly prevent re-creation. For example, on the "low" branch (recall this means we took some variable k that had a fractional value f and limited it to be <= ⌊f⌋), the first thing the sub problem tries to do is re-create exactly the same packing that corresponds k, so that it can be added to the master problem to "undo the damage". That is exactly the opposite of what we need though. So re-creating a column must be banned.

Constraint 4 is not a great way to do it, because now what the sub problem will try is generating all equivalent packings, thanks to symmetries. For example, after rounding down the variable of this packing:

It generates equivalent packings like these:

etc. There are a lot of these, and they're all pointless because it doesn't matter (for the objective value of the master problem, when the integer constraint is taken into account) where the 1x3 piece goes, it just matters that the packing contains a 1x3 piece and 14 1x1 pieces.

So ideally constraint 4 would be replaced by something more complicated that bans a packing equivalent to any that have come before, but something else that mostly works is first trying the high branch. At least in this example, that works out just fine.

In this example, after adding the columns that allow the master problem to be optimal (but still fractional, before any branching), the objective value is 5.5882352941176467. That already means that we know we'll need at least 6 containers, because this being the optimal fractional value proves that it cannot be done with 5 and a fractional number of containers is not an option.

A solution with 6 containers is found quickly, namely

Three of these:

One each of these:

Which packs all the pieces plus an extra 1x4 piece and 3 extra 1x1 pieces.

This algorithm does not depend the shape of the pieces or the container much, except that they have to be expressible as cells on a grid. The container can have holes all over the place, the pieces can be more like tetris pieces or even have disconnected parts. A downside is that the list of placements that it needs scales badly with the size of the container.

这篇关于2D箱包装，在容器中有预定义的间隙的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！