box solver

The box solver solves three-dimensional bin packing problems where items are rectangular parallelepipeds (boxes) that must be packed into rectangular bins without overlapping. Unlike the box-stacks solver, items are placed freely in 3D space — they are not restricted to vertical stacks and do not need to share a footprint.

_images/box.png

These problems occur for example in container loading, truck loading, and warehouse picking.

Features:

  • Objectives:

    • Knapsack

    • Bin packing

    • Bin packing with leftovers

    • Open dimension X

    • Open dimension Y

    • Variable-sized bin packing

  • Select allowed item rotations (among the 6 possible rotations)

  • Maximum weight in bins

Basic usage

The box solver takes as input:

  • an item CSV file; option: --items items.csv

  • a bin CSV file; option: --bins bins.csv

  • optionally a parameter CSV file; option: --parameters parameters.csv

It outputs:

  • a solution CSV file; option: --certificate solution.csv

The item file contains:

  • The X dimension of the item type (mandatory)

    • column X

    • Integer value

  • The Y dimension of the item type (mandatory)

    • column Y

    • Integer value

  • The Z dimension of the item type (mandatory) — the vertical dimension in the default orientation

    • column Z

    • Integer value

  • The number of copies of the item type

    • column COPIES

    • default value: 1

  • The profit of an item of this type (for a knapsack objective)

    • column PROFIT

    • default value: item volume (X * Y * Z)

The bin file contains:

  • The X dimension of the bin type (mandatory)

    • column X

    • Integer value

  • The Y dimension of the bin type (mandatory)

    • column Y

    • Integer value

  • The Z dimension of the bin type (mandatory) — the height of the bin

    • column Z

    • Integer value

  • The number of copies of the bin type

    • column COPIES

    • default value: 1

  • The minimum number of copies that must be used

    • column COPIES_MIN

    • default value: 0

  • The cost of a bin of this type (for a variable-sized bin packing objective)

    • column COST

    • default value: bin volume

The parameter file has two columns: NAME and VALUE. The possible entries are:

  • The objective; name: objective; possible values:

    • knapsack

    • bin-packing

    • bin-packing-with-leftovers

    • open-dimension-x

    • open-dimension-y

    • variable-sized-bin-packing

Inputs:

items.csv
X,Y,Z,COPIES
108,76,30,20
110,43,25,20
92,81,55,20
bins.csv
X,Y,Z
216,173,110
parameters.csv
NAME,VALUE
objective,knapsack

Solve:

packingsolver_box \
        --items items.csv \
        --bins bins.csv \
        --parameters parameters.csv \
        --certificate solution.csv \
        --time-limit 5

=================================
          PackingSolver          
=================================

Problem type
------------
Box

Instance
--------
Objective:             Knapsack
Number of item types:  3
Number of items:       60
Number of bin types:   1
Number of bins:        1
Number of defects:     0
Total item volume:     15487000
Total item profit:     1.5487e+07
Largest item profit:   409860
Total item weight:     0
Largest item copies:   20
Smallest item x:       92
Smallest item y:       43
Smallest item z:       25
Total bin volume:      4110480
Total bin weight:      inf
Largest bin cost:      37368

        Time        Profit   # items                         Comment
        ----        ------   -------                         -------
       0.000        246240         1                  TS g 5 d Z q 1
       0.000        409860         1                  TS g 4 d X q 1
       0.000        492480         2                  TS g 4 d X q 1
       0.001        656100         2                  TS g 4 d X q 1
       0.001        738720         3                  TS g 4 d X q 1
       0.001        902340         3                  TS g 4 d X q 1
       0.001   1.02059e+06         4                  TS g 4 d X q 1
       0.001   1.13884e+06         5                  TS g 4 d X q 1
       0.001   1.25709e+06         6                  TS g 4 d X q 1
       0.001   1.37534e+06         7                  TS g 4 d X q 1
       0.001   1.49359e+06         8                  TS g 4 d X q 1
       0.001   1.57621e+06         9                  TS g 4 d X q 1
       0.001   1.73983e+06         9                  TS g 4 d X q 1
       0.002   1.85808e+06        10                  TS g 4 d X q 1
       0.002   1.97633e+06        11                  TS g 4 d X q 1
       0.002   2.09458e+06        12                  TS g 4 d X q 1
       0.002   2.29554e+06         6                  TS g 5 d Z q 1
       0.002   2.45916e+06         6                  TS g 5 d Z q 1
       0.002    2.7054e+06         7                  TS g 5 d Z q 1
       0.002   2.86902e+06         7                  TS g 5 d Z q 1
       0.002   2.95164e+06         8                  TS g 5 d Z q 1
       0.002   3.11526e+06         8                  TS g 5 d Z q 1
       0.002   3.23351e+06         9                  TS g 5 d Z q 1
       0.002   3.44241e+06        16                  TS g 4 d X q 1
       0.003   3.56066e+06        17                  TS g 4 d X q 2
       0.040    3.5704e+06        16                 TS g 4 d Y q 42

Final statistics
----------------
Time (s):  5.00475

Solution
--------
Number of items:   16 / 60 (26.6667%)
Item volume:       3.5704e+06 / 1.5487e+07 (23.0542%)
Item weight:       0 / 0 (-nan%)
Item profit:       3.5704e+06 / 1.5487e+07 (23.0542%)
Number of stacks:  0
Stack area:        0
Number of bins:    1 / 1 (100%)
Bin volume:        4110480 / 4110480 (100%)
Bin area:          37368 / 37368 (100%)
Bin weight:        inf / inf (-nan%)
Bin cost:          37368
Waste:             516320
Waste (%):         12.6341
Full waste:        540080
Full waste (%):    13.1391
Volume load:       0.868609
Area load:         0
Weight load:       0
X max:             216
Y max:             172
Z max:             110

Visualize:

python3 scripts/visualize_box.py solution.csv
_images/box_example_solution.png

Item rotations

  • The allowed orientations

    • columns ROTATION_XYZ, ROTATION_YXZ, ROTATION_ZYX, ROTATION_YZX, ROTATION_XZY, ROTATION_ZXY

    • 1: this orientation is allowed; 0 or omitted: not allowed

    • default: if none of these columns is set to 1, only ROTATION_XYZ (the default orientation) is used

The six possible 3D orientations of a box are:

Column

X direction

Y direction

Z direction (vertical)

ROTATION_XYZ

x

y

z

ROTATION_YXZ

y

x

z

ROTATION_ZYX

z

y

x

ROTATION_YZX

y

z

x

ROTATION_XZY

x

z

y

ROTATION_ZXY

z

x

y

Each rotation is enabled independently via its own boolean column (1 to allow it, 0 or omitted to disallow it). If none of the ROTATION_* columns is set, only ROTATION_XYZ (the default orientation) is used. Common combinations:

  • Only ROTATION_XYZ: only the default orientation

  • ROTATION_XYZ and ROTATION_YXZ: Z face always on top; both XY rotations allowed

  • ROTATION_XYZ, ROTATION_YXZ, ROTATION_ZYX and ROTATION_YZX: Y face cannot be on top

  • ROTATION_XYZ, ROTATION_YXZ, ROTATION_XZY and ROTATION_ZXY: X face cannot be on top

  • All six columns set to 1: all six orientations allowed

The following example packs a 10×10×6 item and a 10×4×6 item into 10×10×10 bins (bin-packing objective). The first item fills the bottom of a bin exactly, leaving a 10×10×4 gap on top. Without rotation, the second item keeps its 6-high default orientation, which does not fit in that gap, so it needs a second bin. Allowing ROTATION_XZY for the second item lets it be turned on its side (effectively 10×6×4), which fits exactly into the remaining gap, so both items pack into a single bin.

Without rotation

With rotation
items.csv
X,Y,Z,COPIES
10,10,6,1
10,4,6,1
items.csv
X,Y,Z,ROTATION_XYZ,ROTATION_XZY,COPIES
10,10,6,1,0,1
10,4,6,1,1,1
bins.csv
X,Y,Z,COPIES
10,10,10,2
bins.csv
X,Y,Z,COPIES
10,10,10,2
parameters.csv
NAME,VALUE
objective,bin-packing
parameters.csv
NAME,VALUE
objective,bin-packing

packingsolver_box \
        --items items.csv \
        --bins bins.csv \
        --parameters parameters.csv \
        --certificate solution.csv

packingsolver_box \
        --items items.csv \
        --bins bins.csv \
        --parameters parameters.csv \
        --certificate solution.csv

box_rotation_no

box_rotation_yes

Maximum total weight in a bin

Each bin type may have a maximum weight limit: the total weight of items placed in any bin must not exceed its maximum weight.

  • The weight of the item

    • column WEIGHT

    • default value: 0

  • The maximum total weight allowed in a bin of this type

    • column MAXIMUM_WEIGHT

    • default value: no limit

The following example packs 4 items of size 10×10×10 with weight 100 each into 20×20×10 bins. Without a weight limit, all 4 items (total weight 400) fit in a single bin arranged as a 2×2 grid. With MAXIMUM_WEIGHT=200, at most 2 items can share a bin, so 2 bins are required.

Without maximum weight

With maximum weight
items.csv
X,Y,Z,COPIES,WEIGHT
10,10,10,4,100
items.csv
X,Y,Z,COPIES,WEIGHT
10,10,10,4,100
bins.csv
X,Y,Z,COPIES
20,20,10,10
bins.csv
X,Y,Z,COPIES,MAXIMUM_WEIGHT
20,20,10,10,200
parameters.csv
NAME,VALUE
objective,bin-packing
parameters.csv
NAME,VALUE
objective,bin-packing

packingsolver_box \
        --items items.csv \
        --bins bins.csv \
        --parameters parameters.csv \
        --certificate solution.csv

packingsolver_box \
        --items items.csv \
        --bins bins.csv \
        --parameters parameters.csv \
        --certificate solution.csv

box_maximum_weight_no

box_maximum_weight_yes