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 BoxStacks solver, items are placed freely in 3D space — they are not restricted to vertical stacks and do not need to share a footprint.

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
Item types
- 3D rotations (up to 6 orientations per item)
- Weight
Bin types
- Maximum weight

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 weight of the item
- column WEIGHT
- default value: 0
The allowed orientations, encoded as a bitmask
- column ROTATIONS
- default value: 1 (default orientation only)
- See Rotations below

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 maximum total weight allowed in a bin of this type
- column MAXIMUM_WEIGHT
- default value: no limit

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

Basic example¶

Inputs:

items.csv¶

X,Y,Z,ROTATIONS,COPIES
20,15,10,1,15

bins.csv¶

X,Y,Z
100,30,20

parameters.csv¶

NAME,VALUE
objective,bin-packing-with-leftovers

Solve:

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

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

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

Instance
--------
Objective:             BinPackingWithLeftovers
Number of item types:  1
Number of items:       15
Number of bin types:   1
Number of bins:        1
Number of defects:     0
Total item volume:     45000
Total item profit:     45000
Largest item profit:   3000
Total item weight:     0
Largest item copies:   15
Total bin volume:      60000
Total bin weight:      inf
Largest bin cost:      3000

        Time       Waste   Waste (%)                         Comment
        ----       -----   ---------                         -------
       0.000       15000       25.00                  TS g 0 d X q 1

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

Solution
--------
Number of items:   15 / 15 (100%)
Item volume:       45000 / 45000 (100%)
Item weight:       0 / 0 (-nan%)
Item profit:       45000 / 45000 (100%)
Number of stacks:  0
Stack area:        0
Number of bins:    1 / 1 (100%)
Bin volume:        60000 / 60000 (100%)
Bin area:          3000 / 3000 (100%)
Bin weight:        inf / inf (-nan%)
Bin cost:          3000
Waste:             15000
Waste (%):         25
Full waste:        15000
Full waste (%):    25
Volume load:       0.75
Area load:         0
Weight load:       0
X max:             100
Y max:             30
Z max:             20

Visualize:

python3 scripts/visualize_box.py solution.csv

Rotations¶

The six possible 3D orientations of a box are:

Rotation id	X direction	Y direction	Z direction (vertical)
0	x	y	z
1	y	x	z
2	z	y	x
3	y	z	x
4	x	z	y
5	z	x	y

The ROTATIONS column is a bitmask: bit k (value 2^k) is set if rotation k is allowed. Common values:

1 (= 2^0): only the default orientation
3 (= 2^0 + 2^1): Z face always on top; both XY rotations allowed
15 (= 2^0 + 2^1 + 2^2 + 2^3): Y face cannot be on top
51 (= 2^0 + 2^1 + 2^4 + 2^5): X face cannot be on top
63 (= all 6 bits): all six orientations allowed

Maximum weight¶

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

The weight of an item type is specified via the WEIGHT column in the item CSV file. The maximum weight of a bin type is specified via the MAXIMUM_WEIGHT column in the bin CSV file. Items are assigned a weight via the WEIGHT column in the item CSV file.

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