Проблема с изменяемой упаковкой бункера с Prolog (CLP)

Question

Я пытаюсь найти алгоритм для NP-жесткой проблемы упаковки двухмерных бункеров переменного размера (2DVSBPP) в (Swi-) Prolog с использованием логических ограничений c Программирование (CLP).

Проблема могла быть Объясняется это так: некоторые заказанные продукты необходимо максимально эффективно упаковать в некоторые коробки (ящики). У товаров есть заданная ширина и длина (квадраты или прямоугольники, например, 2x3). Существует четыре различных размера ящиков, каждая из которых имеет определенную стоимость для отправителя (например, 4 доллара за ящик 5x5, 5 долларов за ящик 5x7). Цель состоит в том, чтобы минимизировать общую стоимость коробок .

Я уже давно искал ответ на эту проблему и читал множество статей и подобных примеров на других языках . Однако я не могу найти никакого рабочего решения. Я особенно борюсь с тем, как обрабатывать неизвестное количество ящиков (ящиков) .

Чтобы найти решение этой проблемы, я попытался приспособить аналогичную задачу , но на самом деле понятия не имею, как обрабатывать переменное количество ящиков. Следующий код позволяет выбрать самую дешевую коробку, подходящую для всех продуктов длиной , так как для их всех требуется только одна коробка . С того момента, как нам нужно несколько ящиков, программа просто не работает.

Ящики и продукты:

:- 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] .

Но как смоделировать несколько коробок, если у нас будет заказ с большим количеством продуктов, которые не поместятся в одну коробку?

Любая помощь или примеры приветствуются!

Answer 1

Я особенно борюсь с тем, как обрабатывать неизвестное количество ящиков (ящиков).

Вы можете установить верхнюю границу количества ящиков: для N неделимых элементов вы никогда не потребуется больше N коробок. Кроме того, мы можем определить специальный «неиспользованный» вид коробки с нулевым размером, но нулевой стоимостью. Затем мы можем запросить решение с присвоением элементов ровно N (или любого другого количества) ящиков, некоторые из которых могут остаться неиспользованными.

Вот описание одного box, связывающий его вид, размер и стоимость с использованием дизъюнктивных и конъюнктивных ограничений:

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). Причина этого в том, что мы захотим проиндексировать эти списки переменных FD, используя element/3. Этот предикат нельзя использовать для индексации в списки других терминов.

Обращаясь к продуктам, вот FD-версия вашего дизъюнктивного product_either_way предиката:

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).

Здесь мы используем списки Widths и Lengths переменных FD. Номер выбранного блока сам по себе является переменной 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 (размер 9х9) стоимостью 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|...] .

Первое найденное решение использует три коробки, а остальные три оставлены неиспользованными. Можно go дешевле?

?- 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|...] .

Это действительно требует ff или 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/2 для ограничения Kinds, мы можем полностью удалить предварительную маркировку Kinds, чтобы получить хорошее ускорение! Я уверен, что есть еще кое-что, но для прототипа я думаю, что это достаточно разумно.

Спасибо за эту интересную задачу!

Answer 2

• 1000 . В конце концов, ширина и высота - это свойства, которые вы не можете произвольно менять местами в реальном мире, и вы уже создали предикат, который позаботится об этом, поэтому я начал удалять такие дубликаты.

Во-вторых, цель разделения / 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,[]).

По правде говоря, библиотека (clpfd) используется просто как товар, но в сочетании с возможностями поиска (чистого) Prolog дает нам короткое и декларативное решение.

См. специфика c документация библиотеки ( clpBNR ) для лучшего подхода.