theme | title | titleTemplate | background | class | highlighter | lineNumbers | colorSchema | drawings | download | |
---|---|---|---|---|---|---|---|---|---|---|
seriph |
3D-BPP |
%s - Slides |
text-center |
prism |
false |
light |
|
true |
Artificial Intelligence in Industry - Final Project
University of Bologna - Academic Year 2020/21
Leonardo Calbi, Lorenzo Cellini, Alessio Falai
- We are given a set of
rectangular-shaped items, each characterized by width , depth and height - We are given a number of identical 3D containers (bins) having width
, depth and height - The three-dimensional bin-packing problem (3D-BPP) consists in orthogonally packing all the items into the minimum number of bins
- Items may not be rotated
- We have unlimited bins
at our disposal - All input data are positive integers satisfying
-
, where - Continuous lower bound: measures the overall liquid volume
- Worst-case performance ratio of
- Time complexity:
-
- Obtained by reduction to the one-dimensional case
- Worst-case performance arbitrarily bad
- Time complexity:
-
- Explicitly takes into account the three dimensions of the items and dominates
- Worst-case performance ratio of
- Time complexity:
- Explicitly takes into account the three dimensions of the items and dominates
Misplaced \hline
$$
\begin{array} {|l|l|l|}\hline
\textbf{Characteristic} & \textbf{Distribution} & \textbf{Parameters} \ \hline
\text{Depth/width ratio } R_{DW} & \text{Normal} & (0.695,0.118) \\
\text{Height/width ratio } R_{HW} & \text{Lognormal} & (-0.654,0.453) \\
\text{Repetition } F & \text{Lognormal} & (0.544,0.658) \\
\text{Volume } V & \text{Lognormal} & (2.568,0.705) \\
\text{Weight } L & \text{Lognormal} & (2,2) \ \hline
\end{array}
$$
- Volumes:
- Widths:
- Depths:
- Heights:
- A superitem is a collection of individual items that are compactly stacked together
- Building procedure
- Single: composed of a unique item
-
Horizontal: composed of items having the exact same dimensions
- Possibility to restrict their generation (2D, 2W, 4 or none)
-
Vertical: composed of items s.t. the ones on top have an area support of at least
- Maximum
stacked superitems (either single or horizontal)
- Maximum
- A layer is defined as a two-dimensional arrangement of items within the horizontal boundaries of a bin with no superitems stacked on top of each other
- Superitems are placed relative to layers and layers are placed relative to bins
::right::
- (5): ensure that every item is included in a layer
- (6): define the height of layer
- (7): redundant valid cuts that force the area of a layer to fit within the area of a bin
- (8): enforce at least one relative positioning relationship between each pair of items in a layer
- (9) and (10): ensure that there is at most one spatial relationship between items
and along each of the width and depth dimensions - (11) and (12): non-overlapping constraints
- (13) and (14): ensure that items are placed within the boundaries of the bin
::right::
MAXRECTS
is a procedural algorithm for solving the 2D bin packing problem, based on an extension of theGUILLOTINE
split rule- Height groups: divide the whole pool of superitems into groups having heights within a given tolerance
MAXRECTS
is used to generate layers- Run multiple strategies (Bottom-Left, Best Area Fit, Best Short Side Fit and Best Long Side Fit) and select the most dense layers
- Warm start: single item layers vs
MAXRECTS
- Each iteration builds only a single layer and adds it to the whole pool
- Stopping criterion: maximum iterations or convergence (non-negative reduced costs)
- Optimality: no branch-and-price scheme
-
RMP
selects the best layers so far -
represents the linear relaxation of the integrality constraint -
are the dual variables corresponding to constraints (18) - The master problem is solved using
BOP
(it only contains boolean variables), while the reduced one is solved withGLOP
(linear program)
-
SP
selects items and positions them in a new layer -
is the reduced cost of a new layer -
SP
can be solved in the following ways-
MAXRECTS
: solve the whole pricing subproblem heuristically, usingMAXRECTS
to place superitems by biggest duals first -
Placement and no-placement strategy
- No-placement: serves as an item selection mechanism, thus ignoring the expensive placement constraints (MIP or CP)
-
Placement: checks whether there is a feasible placement of the selected items in a layer and places them if possible, otherwise iterates with the no-placement model (MIP or CP or
MAXRECTS
)
-
-
Discard layers by densities (given a minimum density
) -
Discard layers by item coverage
- If at least one item in layer
was already selected more times than , discard - If at least
items in layer are already covered by previously selected layers, discard
- If at least one item in layer
-
Remove duplicated items
- Remove superitems in different layers containing the same item (remove the ones in less dense layers)
- Remove superitems in the same layer containing the same item (remove the ones with less volume)
- Re-arrange layers (using
MAXRECTS
) in which at least one superitem was removed (if)
- Remove empty layers
- Sort layers by densities
- Uncovered items: create new layers filled with items that were not covered in the previous procedures and add them to the layer pool
- Bins building procedure: stack layers on top of each other until a bin is full and open new bins as needed
- Compact bins: let items "fall" to the ground as much as possible, without allowing intersections
- Allow items to be rotated on the 3 axis
- Integrate the branch-and-price scheme into column generation to prove optimality
- Handle weight constraints and bin load capacity
- Improve item support through MP models (as described in the paper)
- Load bins inside containers
python3 -m streamlit run src/dashboard.py
jupyter notebook bpp.ipynb
Bye bye