Skip to content

Files

Latest commit

c0cae16 · Sep 16, 2021

History

History
268 lines (197 loc) · 8.16 KB

slides.md

File metadata and controls

268 lines (197 loc) · 8.16 KB
theme title titleTemplate background class highlighter lineNumbers colorSchema drawings download
seriph
3D-BPP
%s - Slides
text-center
prism
false
light
persist
true
<style> p { opacity: 1.0 !important; } </style>

3D Bin Packing

Artificial Intelligence in Industry - Final Project
University of Bologna - Academic Year 2020/21

Leonardo Calbi, Lorenzo Cellini, Alessio Falai

3D-BPP

Problem definition

  • We are given a set of n rectangular-shaped items, each characterized by width w j , depth d j and height h j
  • We are given a number of identical 3D containers (bins) having width W , depth D and height H
  • The three-dimensional bin-packing problem (3D-BPP) consists in orthogonally packing all the items into the minimum number of bins

Assumptions

  • Items may not be rotated
  • We have unlimited bins b 1 , b 2 , at our disposal
  • All input data are positive integers satisfying w j W , d j D , h j H

Lower bounds

  1. L 0 = j = 1 n v j B , where v j = w j × d h × h j
    • Continuous lower bound: measures the overall liquid volume
    • Worst-case performance ratio of 1 8
    • Time complexity: O ( n )
  2. L 1 = max L 1 W H , L 1 W D , L 1 H D
    • Obtained by reduction to the one-dimensional case
    • Worst-case performance arbitrarily bad
    • Time complexity: O ( n )
  3. L 2 = max L 2 W H , L 2 W D , L 2 H D
    • Explicitly takes into account the three dimensions of the items and dominates L 1
    • Worst-case performance ratio of 2 3
    • Time complexity: O ( n 2 )

Dataset

Distributions

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}
$$

Reasoning

  1. Volumes: V L N ( μ , σ 2 ) , μ = j = 1 N log v j N , σ 2 = j = 1 N ( log v j μ ) 2 N , N = 166407 , j C 1 , C 5
  2. Widths: W = ( V R D W × R H W ) 1 3
  3. Depths: D = W × R D W
  4. Heights: H = W × R H W

Superitems

  • A superitem is a collection of individual items that are compactly stacked together
  • Building procedure
    1. Single: composed of a unique item
    2. Horizontal: composed of items having the exact same dimensions
      • Possibility to restrict their generation (2D, 2W, 4 or none)
    3. Vertical: composed of items s.t. the ones on top have an area support of at least 70
      • Maximum M stacked superitems (either single or horizontal)

Layers

  • 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

Workflow


layout: two-cols

Baseline

::right::

Constraints

  • (5): ensure that every item is included in a layer
  • (6): define the height of layer l
  • (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 i and j 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

layout: two-cols

MAXRECTS

::right::

Details

  • MAXRECTS is a procedural algorithm for solving the 2D bin packing problem, based on an extension of the GUILLOTINE 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

Column generation

  • 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

  • RMP selects the best layers so far
  • α l 0 represents the linear relaxation of the integrality constraint α l 0 , 1
  • λ 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 with GLOP (linear program)

SP

  • SP selects items and positions them in a new layer
  • o l i s λ i f s i z s l is the reduced cost of a new layer l
  • SP can be solved in the following ways
    • MAXRECTS: solve the whole pricing subproblem heuristically, using MAXRECTS to place superitems by biggest duals first
    • Placement and no-placement strategy
      1. No-placement: serves as an item selection mechanism, thus ignoring the expensive placement constraints (MIP or CP)
      2. 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)

Layer filtering

  1. Discard layers by densities (given a minimum density d m )
  2. Discard layers by item coverage
    • If at least one item in layer l was already selected more times than M a , discard l
    • If at least M s items in layer l are already covered by previously selected layers, discard l
  3. 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 d l > d m )
  4. Remove empty layers
  5. Sort layers by densities

Bin packing

  1. Uncovered items: create new layers filled with items that were not covered in the previous procedures and add them to the layer pool
  2. Bins building procedure: stack layers on top of each other until a bin is full and open new bins as needed
  3. Compact bins: let items "fall" to the ground as much as possible, without allowing intersections

Future improvements

  • 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

layout: center

Demo

python3 -m streamlit run src/dashboard.py
jupyter notebook bpp.ipynb

layout: end

Bye bye