4

我正在尝试使用约束逻辑编程 (CLP) 在 (Swi-)Prolog 中为 NP-hard 2D Variable Size Bin Packing Problem (2DVSBPP) 找到一种算法。

问题可以这样解释：一些订购的产品需要尽可能高效地包装到一些盒子（箱）中。产品有一些给定的宽度和长度（正方形或矩形，例如 2x3）。有四种不同尺寸的箱子，每种都有给托运人的特定成本（例如，5x5 箱子 4 美元，5x7 箱子 5 美元）。目标是最小化盒子的总成本。

一段时间以来，我一直在寻找这个问题的答案，并阅读了许多其他语言的论文和类似示例。但是，我找不到任何可行的解决方案。我特别为如何处理未知数量的 Boxes (bins) 而苦苦挣扎。

为了能够找到解决这个问题的方法，我尝试了一个类似的问题，但真的不知道如何处理可变数量的盒子。下面的代码可以选择最便宜的盒子来装所有的产品，只要一个盒子就可以装下它们。从我们需要多个盒子的那一刻起，程序就失败了。

盒子和产品：

:- use_module(library(clpfd)).
:- use_module(library(clpr)).
:- expects_dialect(sicstus).


%% These are the possible productsizes that could need packing
% product (id, width, length)
product(1, 2, 2). 
product(2, 1, 2). 
product(2, 2, 1). % repeating product n2 because it can lay horizontal or vertical
product(3, 1, 3). 
product(3, 3, 1). % idem
product(4, 3, 3). % is square so does not need it
product(5, 2, 3). 
product(5, 3, 2). % iden
product(6, 4, 2). 
product(6, 2, 4). % idem

% because it can lay virtically or horizontally in a box
product_either_way(Number, Width, Length) :-
    product(Number, Width, Length).
product_either_way(Number, Width, Length) :-
    product(Number, Length, Width).


%% These are the so called bins from the 2DVSBPP problem
%% There are 4 sizes, but there is an unlimited supply
% box(Width, Length, Cost)
box(4,4,4).
box(4,6,6).
box(5,5,7).
box(9,9,9).

约束：

area_box_pos_combined(W_total*H_total,prod(N),X+Y,f(X,Width,Y,Height)) :-
    product_either_way(N, Width, Height), % Getting the width and height (length) of a product
    % Constraint: the product should 'fit' inside the choosen box
    % thus limiting its coordinates (XY)
    X #>= 1,
    X #=< W_total-Width+1,
    Y #>= 1,
    Y #=< H_total-Height+1.

positions_vars([],[]).
positions_vars([X+Y|XYs],[X,Y|Zs]) :-
    positions_vars(XYs,Zs).

area_boxes_positions_(ProductList,Ps,Zs) :-
    box(W, H, Cost), % finding a suitable box with a W & H
    %% minimize(Cost),
    maplist(area_box_pos_combined(W*H),ProductList,Ps,Cs), % Setting up constraints for each product
    disjoint2(Cs), % making sure they dont overlap with other product inside the box
    positions_vars(Ps,Zs).

一个可能的查询要求包装 4 种产品（编号 2、1、3 和 5）

area_boxes_positions_([prod(2),prod(1),prod(3),prod(5)],Positions,Zs),
labeling([ffc],Zs).

Gives the following as output, one possible way to pack the products:
Positions = [3+1, 1+1, 4+1, 1+3],
Zs = [3, 1, 1, 1, 4, 1, 1, 3] .

但是，当我们的订单中有更多产品无法放入一个盒子时，我该如何建模多个盒子？

非常感谢任何帮助或示例！

4

2 回答 2

6

我特别为如何处理未知数量的盒子（箱子）而苦苦挣扎。

你可以为盒子的数量设置一个上限：对于 N 个不可分割的元素，你永远不需要超过 N 个盒子。此外，我们可以定义一种特殊的“未使用”类型的盒子，其大小为 0，但成本为 0。然后我们可以要求一个解决方案，将项目分配到恰好N 个（或任何其他数量的）盒子，其中一些可以保持未使用。

下面是对单个盒子的描述，使用析取约束和合取约束将其种类、大小和成本联系起来：

kind_width_length_cost(Kind, Width, Length, Cost) :-
    % unused box
    (Kind #= 0 #/\ Width #= 0 #/\ Length #= 0 #/\ Cost #= 0) #\/
    % small box
    (Kind #= 1 #/\ Width #= 4 #/\ Length #= 4 #/\ Cost #= 4) #\/
    % medium box
    (Kind #= 2 #/\ Width #= 4 #/\ Length #= 6 #/\ Cost #= 6) #\/
    % large box
    (Kind #= 3 #/\ Width #= 5 #/\ Length #= 5 #/\ Cost #= 7) #\/
    % X-large box
    (Kind #= 4 #/\ Width #= 9 #/\ Length #= 9 #/\ Cost #= 9),
    % make sure all variables have finite domains, the above disjunction is
    % not enough for the system to infer this
    Kind in 0..4,
    Width in 0..9,
    Length in 0..9,
    Cost in 0..9.

N 个盒子的集合可以表示为一个术语boxes(Numbers, Kinds, Widths, Lengths, Costs)，其中每个其他列表Numbers的[1, 2, ..., N]第I- 个元素是盒子编号的长度/宽度/成本I：

n_boxes(N, boxes(Numbers, Kinds, Widths, Lengths, Costs)) :-
    numlist(1, N, Numbers),
    length(Kinds, N),
    maplist(kind_width_length_cost, Kinds, Widths, Lengths, Costs).

例如，三个框是：

?- n_boxes(3, Boxes).
Boxes = boxes([1, 2, 3], [_G9202, _G9205, _G9208], [_G9211, _G9214, _G9217], [_G9220, _G9223, _G9226], [_G9229, _G9232, _G9235]),
_G9202 in 0..4,
_G9202#=4#<==>_G9257,
_G9202#=3#<==>_G9269,
_G9202#=2#<==>_G9281,
_G9202#=1#<==>_G9293,
_G9202#=0#<==>_G9305,
... a lot more constraints

请注意，这使用包含列表的术语，而不是使用包含术语的列表的更“通常”的表示box(Num, Width, Length, Cost)。这样做的原因是我们希望使用element/3. 此谓词不能用于索引其他术语的列表。

谈到产品，这里是你的析取product_either_way谓词的 FD 版本：

product_either_way_fd(Number, Width, Length) :-
    product_width_length(Number, W, L),
    (Width #= W #/\ Length #= L) #\/ (Width #= L #/\ Length #= W),
    % make sure Width and Length have finite domains
    Width #>= min(W, L),
    Width #=< max(W, L),
    Length #>= min(W, L),
    Length #=< max(W, L).

一个项目的放置用一个box_x_y_w_l包含框的编号、框内的 X 和 Y 坐标以及项目的宽度和长度的术语来表示。放置必须与所选框的尺寸兼容：

product_placement(Widths, Lengths, Number, Placement) :-
    product_either_way_fd(Number, W, L),
    Placement = box_x_y_w_l(_Box, _X, _Y, W, L),
    placement(Widths, Lengths, Placement).

placement(Widths, Lengths, box_x_y_w_l(Box, X, Y, W, L)) :-
    X #>= 0,
    X + W #=< Width,
    Y #>= 0,
    Y + L #=< Length, 
    element(Box, Widths, Width),
    element(Box, Lengths, Length).

这是我们使用 FD 变量的Widths和Lengths列表的地方。所选框的编号本身就是一个 FD 变量，我们使用它作为索引来使用element/3约束查找框的宽度和长度。

现在我们必须对不重叠的展示位置进行建模。放置在不同盒子中的两个项目自动不重叠。对于同一个盒子里的两个项目，我们必须检查它们的坐标和大小。此二元关系必须应用于所有无序项对：

placement_disjoint(box_x_y_w_l(Box1, X1, Y1, W1, L1),
                   box_x_y_w_l(Box2, X2, Y2, W2, L2)) :-
    Box1 #\= Box2 #\/
    (Box1 #= Box2 #/\
     (X1 #>= X2 + W2 #\/ X1 + W1 #< X2) #/\
     (Y1 #>= Y2 + L2 #\/ Y1 + L1 #< Y2)).

alldisjoint([]).   
alldisjoint([Placement | Placements]) :-
    maplist(placement_disjoint(Placement), Placements),
    alldisjoint(Placements).

现在我们准备好将所有东西放在一起。给定一个产品列表和 N 个盒子（其中一些可能未使用），以下谓词计算盒子中放置的约束、使用的盒子的种类、它们的成本和总成本：

placements_(Products, N, Placements, BoxKinds, Costs, Cost) :-
    n_boxes(N, boxes(_BoxNumbers, BoxKinds, Widths, Lengths, Costs)),
    maplist(product_placement(Widths, Lengths), Products, Placements),
    alldisjoint(Placements),
    sum(Costs, #=, Cost).

这构造了一个表示 N 个盒子的术语，计算每个产品的放置约束，确保放置不相交，并设置总成本的计算。就这些！

我正在使用从问题中复制的以下产品。请注意，我已删除具有交换宽度/长度的重复项，因为此交换是product_either_way_fd在需要时完成的。

product_width_length(1, 2, 2).
product_width_length(2, 1, 2).
product_width_length(3, 1, 3).
product_width_length(4, 3, 3).
product_width_length(5, 2, 3).
product_width_length(6, 4, 2).

我们已准备好进行测试。要重现将项目 2、1、3 和 5 放在一个盒子中的示例：

?- placements_([2, 1, 3, 5], 1, Placements, Kinds, Costs, Cost).
Placements = [box_x_y_w_l(1, _G17524, _G17525, _G17526, _G17527), box_x_y_w_l(1, _G17533, _G17534, 2, 2), box_x_y_w_l(1, _G17542, _G17543, _G17544, _G17545), box_x_y_w_l(1, _G17551, _G17552, _G17553, _G17554)],
Kinds = [_G17562],
Costs = [Cost],
_G17524 in 0..8,
_G17524+_G17526#=_G17599,
_G17524+_G17526#=_G17611,
_G17524+_G17526#=_G17623,
...

带标签：

?- placements_([2, 1, 3, 5], 1, Placements, Kinds, Costs, Cost), term_variables(Placements, Variables, [Cost | Costs]), labeling([], Variables).
Placements = [box_x_y_w_l(1, 0, 0, 1, 2), box_x_y_w_l(1, 7, 7, 2, 2), box_x_y_w_l(1, 4, 6, 3, 1), box_x_y_w_l(1, 2, 3, 2, 3)],
Kinds = [4],
Costs = [9],
Cost = 9,
Variables = [0, 0, 1, 2, 7, 7, 4, 6, 3|...] .

（您可能需要仔细检查它的正确性！）所有东西都放在 1 号盒子里，它是种类 4（尺寸 9x9），成本 9。

有没有办法把这些物品装进一个更便宜的盒子里？

?- Cost #< 9, placements_([2, 1, 3, 5], 1, Placements, Kinds, Costs, Cost), term_variables(Placements, Variables, [Cost | Costs]), labeling([], Variables).
false.

现在，将所有产品放入（最多）6 个盒子中怎么样？

?- placements_([1, 2, 3, 4, 5, 6], 6, Placements, Kinds, Costs, Cost), term_variables(Placements, Variables, [Cost | Costs]), labeling([], Variables).
Placements = [box_x_y_w_l(1, 0, 0, 2, 2), box_x_y_w_l(1, 3, 3, 1, 2), box_x_y_w_l(1, 5, 6, 1, 3), box_x_y_w_l(2, 0, 0, 3, 3), box_x_y_w_l(2, 4, 4, 2, 3), box_x_y_w_l(3, 0, 0, 2, 4)],
Kinds = [4, 4, 1, 0, 0, 0],
Costs = [9, 9, 4, 0, 0, 0],
Cost = 22,
Variables = [1, 0, 0, 1, 3, 3, 1, 2, 1|...] .

找到的第一个解决方案使用三个盒子，而其他三个未使用。我们能便宜点吗？

?- Cost #< 22, placements_([1, 2, 3, 4, 5, 6], 6, Placements, Kinds, Costs, Cost), term_variables(Placements, Variables, [Cost | Costs]), labeling([], Variables).
Cost = 21,
Placements = [box_x_y_w_l(1, 0, 0, 2, 2), box_x_y_w_l(1, 3, 3, 1, 2), box_x_y_w_l(1, 5, 6, 1, 3), box_x_y_w_l(2, 0, 0, 3, 3), box_x_y_w_l(3, 0, 0, 2, 3), box_x_y_w_l(4, 0, 0, 2, 4)],
Kinds = [4, 1, 1, 1, 0, 0],
Costs = [9, 4, 4, 4, 0, 0],
Variables = [1, 0, 0, 1, 3, 3, 1, 2, 1|...] .

是的！该解决方案使用更多的盒子，但总体上稍微便宜一些。我们还能做得更好吗？

?- Cost #< 21, placements_([1, 2, 3, 4, 5, 6], 6, Placements, Kinds, Costs, Cost), term_variables(Placements, Variables, [Cost | Costs]), labeling([], Variables).
% ... takes far too long

我们需要更复杂一点。玩弄盒子的数量，很明显可以使用更少的盒子更便宜的解决方案：

?- Cost #< 21, placements_([1, 2, 3, 4, 5, 6], 2, Placements, Kinds, Costs, Cost), term_variables(Placements, Variables, [Cost | Costs]), labeling([], Variables).
Cost = 18,
Placements = [box_x_y_w_l(1, 0, 0, 2, 2), box_x_y_w_l(1, 3, 3, 1, 2), box_x_y_w_l(1, 5, 6, 1, 3), box_x_y_w_l(2, 0, 6, 3, 3), box_x_y_w_l(2, 6, 4, 3, 2), box_x_y_w_l(2, 4, 0, 2, 4)],
Kinds = [4, 4],
Costs = [9, 9],
Variables = [1, 0, 0, 1, 3, 3, 1, 2, 1|...] .

也许首先将搜索定向到标签框类型是有用的，因为该up策略基本上会尝试使用尽可能少的框：

?- Cost #< 21, placements_([1, 2, 3, 4, 5, 6], 6, Placements, Kinds, Costs, Cost), term_variables(Placements, Variables, [Cost | Costs]), time(( labeling([], Kinds), labeling([ff], Variables) )).
% 35,031,786 inferences, 2.585 CPU in 2.585 seconds (100% CPU, 13550491 Lips)
Cost = 15,
Placements = [box_x_y_w_l(5, 2, 4, 2, 2), box_x_y_w_l(6, 8, 7, 1, 2), box_x_y_w_l(6, 5, 6, 3, 1), box_x_y_w_l(6, 2, 3, 3, 3), box_x_y_w_l(6, 0, 0, 2, 3), box_x_y_w_l(5, 0, 0, 2, 4)],
Kinds = [0, 0, 0, 0, 2, 4],
Costs = [0, 0, 0, 0, 6, 9],
Variables = [5, 2, 4, 6, 8, 7, 1, 2, 6|...] .

这确实需要ffor ffc，默认leftmost策略不会在合理的时间范围内返回结果。

我们还能做得更好吗？

?- Cost #< 15, placements_([1, 2, 3, 4, 5, 6], 6, Placements, Kinds, Costs, Cost), term_variables(Placements, Variables, [Cost | Costs]), time(( labeling([], Kinds), labeling([ff], Variables) )).
% 946,355,675 inferences, 69.984 CPU in 69.981 seconds (100% CPU, 13522408 Lips)
false.

不！成本为 15 的解决方案是最优的（但不是唯一的）。

但是，对于这个非常小的问题，我发现 70 秒太慢了。有一些我们可以利用的对称性吗？考虑：

?- Cost #= 15, placements_([1, 2, 3, 4, 5, 6], 6, Placements, Kinds, Costs, Cost), term_variables(Placements, Variables, [Cost | Costs]), time(( labeling([], Kinds), labeling([ff], Variables) )).
% 8,651,030 inferences, 0.611 CPU in 0.611 seconds (100% CPU, 14163879 Lips)
Cost = 15,
Placements = [box_x_y_w_l(5, 2, 4, 2, 2), box_x_y_w_l(6, 8, 7, 1, 2), box_x_y_w_l(6, 5, 6, 3, 1), box_x_y_w_l(6, 2, 3, 3, 3), box_x_y_w_l(6, 0, 0, 2, 3), box_x_y_w_l(5, 0, 0, 2, 4)],
Kinds = [0, 0, 0, 0, 2, 4],
Costs = [0, 0, 0, 0, 6, 9],
Variables = [5, 2, 4, 6, 8, 7, 1, 2, 6|...] .

?- Kinds = [4, 2, 0, 0, 0, 0], Cost #= 15, placements_([1, 2, 3, 4, 5, 6], 6, Placements, Kinds, Costs, Cost), term_variables(Placements, Variables, [Cost | Costs]), time(( labeling([], Kinds), labeling([ff], Variables) )).
% 11,182,689 inferences, 0.790 CPU in 0.790 seconds (100% CPU, 14153341 Lips)
Kinds = [4, 2, 0, 0, 0, 0],
Cost = 15,
Placements = [box_x_y_w_l(1, 7, 7, 2, 2), box_x_y_w_l(1, 6, 5, 1, 2), box_x_y_w_l(2, 3, 3, 1, 3), box_x_y_w_l(2, 0, 0, 3, 3), box_x_y_w_l(1, 4, 2, 2, 3), box_x_y_w_l(1, 0, 0, 4, 2)],
Costs = [9, 6, 0, 0, 0, 0],
Variables = [1, 7, 7, 1, 6, 5, 1, 2, 2|...] .

这些不是相同解决方案的排列，但它们是相同框的排列，因此具有相同的成本。我们不需要考虑他们两个！除了Kinds比一开始更智能地标记之外，我们还可以要求Kinds列表单调递增。这排除了许多冗余解决方案并提供了更快的终止，甚至首先使用更好的解决方案：

?- placements_([1, 2, 3, 4, 5, 6], 6, Placements, Kinds, Costs, Cost), term_variables(Placements, Variables, [Cost | Costs]), chain(Kinds, #=<), time(( labeling([], Kinds), labeling([ff], Variables) )).
% 34,943,765 inferences, 2.865 CPU in 2.865 seconds (100% CPU, 12195550 Lips)
Placements = [box_x_y_w_l(5, 2, 4, 2, 2), box_x_y_w_l(6, 8, 7, 1, 2), box_x_y_w_l(6, 5, 6, 3, 1), box_x_y_w_l(6, 2, 3, 3, 3), box_x_y_w_l(6, 0, 0, 2, 3), box_x_y_w_l(5, 0, 0, 2, 4)],
Kinds = [0, 0, 0, 0, 2, 4],
Costs = [0, 0, 0, 0, 6, 9],
Cost = 15,
Variables = [5, 2, 4, 6, 8, 7, 1, 2, 6|...] .

?- Cost #< 15, placements_([1, 2, 3, 4, 5, 6], 6, Placements, Kinds, Costs, Cost), term_variables(Placements, Variables, [Cost | Costs]), chain(Kinds, #=<), time(( labeling([], Kinds), labeling([ff], Variables) )).
% 31,360,608 inferences, 2.309 CPU in 2.309 seconds (100% CPU, 13581762 Lips)
false.

对于更大的问题规模，更多的调整是可能的，并且可能是必要的。我发现添加bisect最终标签会有所帮助。删除 中的逻辑冗余Box1 #= Box2约束也是如此placement_disjoint/2。最后，考虑到chain/2to restrict的使用Kinds，我们可以完全删除 的初步标签Kinds以获得很好的加速！我敢肯定还有更多，但对于原型，我认为它足够合理。

感谢您提出这个有趣的问题！

于 2020-08-03T14:48:17.947 回答
1

您的部分解决方案中有一些冗余，可能是由于过早优化造成的。

首先，因为你有一个 product_either_way/3，你不应该改变你的输入规范，添加具有相同 id 和尺寸交换的产品。毕竟，宽度和高度是您在现实世界中无法任意交换的属性，并且您已经生成了一个处理此问题的谓词，因此我已经开始删除此类重复项。

其次， disjoint/2 的目的是计算一组矩形的位置，因此您的 area_box_pos_combined/4 和 position_vars/2 几乎没有用。

以下是我将如何解决这个问题。首先，编写一个谓词，给出一个产品列表和一个盒子，将尽可能多的放入其中，并“返回”那些不适合的。例如

fill_box([P|Ps],W,H,Placed,Rs) :-
    (   product(P,W_i,H_i)
    ;   product(P,H_i,W_i)
    ),
    W_p #= W - W_i,
    H_p #= H - H_i,
    X_i in 0..W_p,
    Y_i in 0..H_p,
    U=[p(X_i, W_i, Y_i, H_i)|Placed],
    disjoint2(U),
    fill_box(Ps,W,H,U,Rs).
fill_box(Rs,_,_,_,Rs).

它有点错误，因为它会在它无法放置的第一个产品处停止，但在此之后可能会有更多可放置的产品。但重要的是，鉴于与 CLP(FD) 的关键概念的交互，现在我们可以开始测试它是否有效。disjoint/2 适用于有界变量，因此需要 X_i 和 Y_i 的域声明。

?- fill_box([1,1],4,2,[],R).
R = [] .

?- fill_box([1,1],3,2,[],R).
R = [1] .

现在我们可以提供一个驱动程序，也许就像这样简单

products_placed_cost([],0).
products_placed_cost(Ps,C) :-
    box(W,H,C0),
    fill_box(Ps,W,H,[],Rs),
    Ps\=Rs,
    products_placed_cost(Rs,C1),
    C #= C0+C1.

然后让 Prolog 生成尽可能多的解决方案，只需通过库（solution_sequences）按成本排序：

?- order_by([asc(C)],products_placed_cost([1,1],C)).
C = 4 ;
C = 4 ;
C = 4 ;
C = 4 ;
C = 6 ;
...

但我们不知道生成了哪些展示位置。我们必须添加带回信息的参数。然后

products_placed_cost([],[],0).
products_placed_cost(Ps,[box(W,H,C0,Q)|Qs],C) :-
    box(W,H,C0),
    fill_box(Ps,W,H,[],Rs,Q),
    Ps\=Rs,
    products_placed_cost(Rs,Qs,C1),
    C #= C0+C1.

fill_box([P|Ps],W,H,Placed,Rs,[P|Qs]) :-
    (   product(P,W_i,H_i)
    ;   product(P,H_i,W_i)
    ),
    W_p #= W - W_i,
    H_p #= H - H_i,
    X_i in 0..W_p,
    Y_i in 0..H_p,
    U=[p(X_i, W_i, Y_i, H_i)|Placed],
    disjoint2(U),
    fill_box(Ps,W,H,U,Rs,Qs).
fill_box(Rs,_,_,_,Rs,[]).

确实，library(clpfd) 只是作为商品使用，但与（纯）Prolog 的搜索功能相结合，为我们提供了一个简短且声明性的解决方案。

有关更好的方法，请参阅库 ( clpBNR )的特定文档。

于 2020-08-01T15:02:36.003 回答