3d-bin-container-packing

This library does 3D rectangular bin packing; it attempts to match a set of 3D items to one or more in a set of 3D containers. The result can be constrained to a maximum number of containers.

Projects using this library will benefit from:

• short and predictable calculation time,
• fairly good use of container space,
• brute-force support for low number of boxes (ideal for small orders)

with

• friendly API
• customizable packagers

Bugs, feature suggestions and help requests can be filed with the issue-tracker.

Obtain

The project is implemented in Java and built using Maven. The project is available on the central Maven repository.

For the previous version, see the 3.x branch.

Maven coordinates

Add

<3d-bin-container-packing.version>4.0.0</3d-bin-container-packing.version>

and

<dependency>
    <groupId>com.github.skjolber.3d-bin-container-packing</groupId>
    <artifactId>core</artifactId>
    <version>${3d-bin-container-packing.version}</version>
</dependency>

or

Gradle coordinates

For

ext {
  containerBinPackingVersion = '4.0.0'
}

add

api("com.github.skjolber.3d-bin-container-packing:core:${containerBinPackingVersion}")

Usage

The units of measure is out-of-scope, be they cm, mm or inches.

Obtain a Packager instance, then then compose your container and product list:

List<BoxItem> products = new ArrayList<>();

products.add(new BoxItem(Box.newBuilder().withId("Shoes").withSize(6, 10, 2).withRotate3D().withWeight(25).build(), 1));
products.add(new BoxItem(Box.newBuilder().withId("Pants").withSize(4, 10, 1).withRotate3D().withWeight(25).build(), 1));
products.add(new BoxItem(Box.newBuilder().withId("Hat").withSize(4, 10, 2).withRotate3D().withWeight(50).build(), 1));

// add a single container type
Container container = Container.newBuilder()
    .withDescription("1")
    .withSize(10, 10, 3)
    .withEmptyWeight(1)
    .withMaxLoadWeight(100)
    .build();
    
// with unlimited number of containers available
List<ContainerItem> containerItems = ContainerItem
    .newListBuilder()
    .withContainer(container)
    .build();

Pack all in a single container:

PackagerResult result = packager
    .newResultBuilder()
    .withContainerItems(containerItems)
    .withBoxItems(products)
    .build();

if(result.isSuccess()) {
    Container match = result.get(0);
    
    // ...
}

Use a maximum number of containers:

int maxContainers = ...; // maximum number of containers which can be used

PackagerResult result = packager
    .newResultBuilder()
    .withContainerItems(containerItems)
    .withBoxItems(products)
    .withMaxContainerCount(maxContainers)
    .build();

Note that all packager instances are thread-safe.

Plain packager

A simple packager

PlainPackager packager = PlainPackager
    .newBuilder()
    .build();

Largest Area Fit First (LAFF) packager

A packager using the LAFF algorithm

LargestAreaFitFirstPackager packager = LargestAreaFitFirstPackager
    .newBuilder()
    .build();

Brute-force packager

For a low number of packages (like <= 6) the brute force packager might be a good fit.

Packager packager = BruteForcePackager
    .newBuilder()
    .build();

See also the ParallelBoxItemBruteForcePackager and FastBruteForcePackager packagers.

Using a deadline is recommended whenever brute-forcing in a real-time application.

Algorithm details

Largest Area Fit First algorithm

The implementation is based on this paper, and is not a traditional bin packing problem solver.

The box which covers the largest ground area of the container is placed first; its height becomes the level height. Boxes which fill the full remaining height take priority. Subsequent boxes are stacked in the remaining space in at the same level, the boxes with the greatest volume first. If box height is lower than level height, the algorithm attempts to place some there as well.

When no more boxes fit in a level, the level is incremented and the process repeated. Boxes are rotated, containers not.

• LargestAreaFitFirstPackager stacks in 3D within each level
• FastLargestAreaFitFirstPackager stacks in 2D within each level

The algorithm runs reasonably fast, usually in milliseconds. Some customization is possible.

Plain algorithm

This algorithm selects the box with the biggest volume, fitting it where it is best supported.

Brute-force algorithm

This algorithm has no logic for selecting the best box or rotation; running through all permutations, for each permutation all rotations:

• BruteForcePackager attempts all box orders, rotations and placement positions.
• FastLargestAreaFitFirstPackager selects all box orders and rotations, selecting the most appropriate placement position.

The complexity of this approach is exponential, and thus there is a limit to the feasible number of boxes which can be packaged within a reasonable time. However, for real-life applications, a healthy part of for example online shopping orders are within its grasp.

The worst case complexity can be estimated using the relevant iterators before packaging is attempted.

The algorithm tries to skip combinations which will obviously not yield a (better) result:

• permutations
  • two or more boxes have the same dimensions
  • permutations which mutated at a previously unreachable index
• fewer rotations
  • two or more sides have the same length
  • rotations which mutated at a previously unreachable index

There is also a parallel version ParallelBruteForcePackager of the brute-force packager, for those wishing to use it on a multi-core system.

Note that the algorithm is recursive on the number of boxes, so do not attempt this with many boxes (it will likely not complete in time anyhow).

Packager customizations

Obstacles within containers

Make the packager account for non-rectangular packaging space, i.e. pillars or other obstacles within containers, by providing the container initial free space (i.e. points).

Packager controls

The packagers (excluding brute force) can be extended to handle specialized needs via various control (plugins) types.

In a nutshell, the controls are stateful objects which are handed various resources from the packagers during construction, and then notified and/or invoked at certain milestones within the packaging process.

Controls must be provided as follows:

• builder factory
  • builder
    • controls

Manifest-controls

Determines which boxes go into which containers, i.e. in which combinations.

A classic example would to be to not package both lighters and dynamite in the same container.

Point-controls

Determines which points are relevant for a specific box.

For example, heavy items might be require only points at ground level or flammable items might be required to be stacked in a certain zone.

Placement-controls

Determines the best placement for a box.

Can consider a range of options, like stability, stacking height, structural integrity and so on; even randomization is possible. Note that these features are not necessarily implemented in the packagers within this project.

Visualizer

There is a simple output visualizer included in this project, based of three.js. This visualizer is currently intended as a tool for developing better algorithms; not as stacking instructions.

Setup

cd visualizer/viewer
npm install

Run

npm start

Note: To "hot reload" the visualizer during development, make your unit tests write directly to a file in the viewer (see the VisualizationTest example).

Get involved

If you have any questions, comments or improvement suggestions, please file an issue or submit a pull-request.

Note on bugs: Please follow shuairan's example and file a test case with a visualization.

License

Apache 2.0. Social media preview by pch.vector on www.freepik.com.

Interesting links

• The Art of Stacking: Challenges Faced While Developing a Packing Algorithm

History

• 4.0.x: Major rewrite. Breaking changes.
  • Support for packaging groups
  • Various ways to control packaging:
    • Manifest controls (box vs box, box vs container)
    • Point controls (points per box)
    • Placement controls (select best box + point)
  • Minor visualizer improvements
• 3.0.11: Use BigInteger to sanity-check max volume / max weight, calculate real remaining max volume.
• 3.0.10: Fix module info, bump dependencies.
• 3.0.9: Fix point support bug which resulted in invalid packaging result
• 3.0.8: Visualization fix
• 3.0.4-3.0.6: Fix issue #689
• 3.0.3: Fix module info
• 3.0.2: Make Plain Packager prefer low z coordinate over supported area.
• 3.0.1: Various performance improvements.
• 3.0.0: Support max number of containers (i.e. per container type). Use builders from now on. Various optimizations.
• 2.1.4: Fix issue #574
• 2.1.3: Fix null-pointer
• 2.1.2: Tidy up, i.e. remove warnings, nuke some dependencies.
• 2.1.1: Improve free space calculation performance
• 2.1.0: Improve brute force iterators, respect deadlines in brute for packagers.