3d-bin-container-packing: packing boxes into containers in Java

Matching items to containers, optionally with a container budget

The library's own description is precise about scope. It does 3D rectangular bin packing; it attempts to match a set of 3D items to one or more in a set of 3D containers, and the result can be constrained to a maximum number of containers.

That last clause is what makes it useful for logistics rather than for a puzzle. Packing an unlimited number of containers is easy, because you can always open another one. The interesting question is how few containers you need, or how much of the volume you can use with a fixed fleet of containers, and that is what the maximum container count expresses.

The README lists three properties a user benefits from. Short and predictable calculation time. Fairly good use of container space. And brute-force support for a low number of boxes, described as ideal for small orders. The project also describes its API as friendly and its packagers as customizable.

The scope boundary is worth stating as well. The units of measure are out-of-scope, be they cm, mm or inches, which is a sensible refusal, since a packing problem does not care about the unit as long as it is consistent. But everything else is rectangular. There is no cylinder, no irregular shape and no rotation outside the axes.

Bugs, feature suggestions and help requests can be filed on the issue tracker, and there is a FEATURES.md that gives a capability overview including which packager supports which feature, generated from the conformance tests, along with known limitations and non-goals. That file is the fastest way to see whether the library does what you need.

Three packagers, and the one you pick depends on the item count

The packagers differ in how they search, and the README is candid about which is for which situation.

The plain packager places the box with the biggest volume first. That is the greedy baseline, and it is fast and predictable because it makes one decision per item.

The Largest Area Fit First packager fills the container level by level, starting each level with the box which covers the largest ground area. A faster variant, FastLargestAreaFitFirstPackager, stacks in 2D within each level. Both are built through the same builder shape:

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

The brute-force packager is the third, and the README scopes it tightly: for a low number of packages, like six or fewer, the brute-force packager might be a good fit. There are also ParallelBruteForcePackager and FastBruteForcePackager variants for the same family.

The point of the split is that exact search does not scale. Six boxes is the range where you can afford to enumerate placements and know you have the answer, and above that the search space is the problem. So the choice of packager is really a choice about how much optimality you need against how many items you have, and the README gives you three points on that curve rather than one algorithm that is good at everything.

A deadline is what makes brute force usable in a request path

If you run a brute-force packager without a bound, the search runs until it finishes, and for a real-time application that is a request that never returns. The README's advice is direct: using a deadline is recommended whenever brute-forcing in a real-time application.

The deadline is set on the result builder, in milliseconds from now, and there is a variant that takes an absolute timestamp:

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

PackagerResult result = packager
    .newResultBuilder()
    .withContainerItems(containerItems)
    .withBoxItems(products)
    .withInterruptDuration(1000) // milliseconds from now; or withInterruptDeadline(System.currentTimeMillis() + 1000)
    .build();

Two things are worth understanding about this API. The deadline is a property of the result builder rather than of the packager, which means one packager instance can be reused across calls with different budgets. And it is an interrupt, not a timeout that throws, so the packager returns with whatever it had found when the clock ran out, which is what you want for a request handler that must answer.

The VirtualBoxPackager shows the same idea in a more elaborate form, with an interrupt duration of 1000 alongside limits on layouts, refinements and delegate boxes.

Load constraints let a box refuse what sits on it

Packing is not only about volume. A carton of glass cannot carry a tonne of steel on top, and a real packing system needs to express that. The load constraints section is where the library handles it.

The builder methods are all on the box:

Box box = Box.newBuilder()
    .withSize(400, 300, 200)
    .withWeight(12)
    .withRotate3D()
    .withMaxLoadWeight(50)          // total weight resting on the box, through all levels above
    .withMaxLoadPressure(0.001)     // weight per area unit
    .withMaxLoadBoxCount(4)         // boxes stacked on top
    .build();

Three separate limits, and they are not the same thing. The maximum load weight is a total, and the comment is explicit that it counts through all levels above, so the constraint is about the column rather than the immediate neighbour. The maximum load pressure is a weight per area unit, which is what catches a heavy item on a small footprint. The maximum load box count is a simple count of boxes on top.

There is a fourth, withMaxLoadIdenticalBoxCount(count), which only allows boxes of the same type on top, for the case where the contents are incompatible with anything else. The README notes that the packagers detect the constraints and enforce them, which is the important part: the constraint is a property of the box rather than a rule you have to reimplement in your own scoring logic.

Rotations are opt-in per box through withRotate3D, and the weight and the empty weight of the container are separate, with withMaxLoadWeight on the container bounding the total.

VirtualBoxPackager collapses identical boxes before searching

The virtual box section addresses a case that makes naive packing slow: many copies of the same box.

Virtual box packaging simplifies packaging when there is more than one of the same box. VirtualBoxPackager wraps a packager, packs repeated boxes as filled rectangular assemblies, and expands the result back into the original boxes.

So the search happens over a much smaller problem. If you have forty identical cartons, the packer treats them as one filled rectangular volume, searches over that, and then expands the assembly back into forty placements when it returns. The search space shrinks from the permutations of forty boxes to the placements of a handful of assemblies, which is where the time saving comes from.

The wrapper is constructed with a delegate packager and closed like any other resource:

try (BruteForcePackager delegate = BruteForcePackager.newBuilder().build();
     VirtualBoxPackager packager = new VirtualBoxPackager(delegate)) {
    PackagerResult result = packager.newResultBuilder()
        .withBoxItems(items)
        .withContainerItems(containers)
        .withMaxContainerCount(3)
        .withMaxLayouts(8)
        .withMaxRefinements(4)
        .withMaxDelegateBoxes(20)
        .withInterruptDuration(1000)
        .build();
}

The four limit parameters are the interesting part, because they are all caps on how much work the wrapper will do. The maximum layouts and maximum refinements bound how many candidate arrangements the inner search may consider and how many times it may try to improve one. The maximum delegate boxes caps how many individual boxes are handed to the delegate packager at once, which is the safety valve that stops the assembly trick from producing an inner problem that is itself too large. Together with the interrupt duration, they define a bounded amount of work regardless of the input size.

Builders in, a placement list out, and thread safety for free

The usage section shows the shape of a typical call, and the shape is consistent: build the items, build the containers, then hand both to a result builder.

Items are BoxItem objects wrapping a Box built with a builder, where the builder carries an id, a size, an optional rotation flag and a weight:

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();

The container is then wrapped in a ContainerItem list, which is where the unlimited number of containers comes from, since you build a list of container items rather than a single container.

The result builder takes both lists, plus an optional container count limit:

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

if(result.isSuccess()) {
    Container match = result.get(0);
    
    List<Placement> placements = match.getStack().getPlacements();

The result is a success flag rather than an exception, which fits a problem where failure to fit everything is an ordinary outcome rather than an error. Placements come out as a list, each presumably carrying the box and its position.

One property saves a lot of defensive code. All packager instances are thread-safe, so a single packager can be a shared field rather than something you construct per request, and the deadline on the result builder is what keeps each call bounded.

Two artifacts from Maven, and an optional validators module

The library is published on the central Maven repository under the group id com.github.skjolber.3d-bin-container-packing, with the core artifact and a separate validators artifact:

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

The validators artifact is added separately when needed, and the README recommends adding the optional result validators separately when needed, which suggests they are worth having if you want to assert on the result.

Gradle users get the same coordinates with the api configuration:

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

The version property is set to 5.0.x in both build files. Upgrading from the 4.x line means reading the migration guide, since the previous version lives on a 4.x branch and the jump to 5.0 is a major one.

The repository layout shows how much more there is than the published artifacts. There is an api directory for the public interfaces, core for the implementation, points for the point calculators, validators for the optional checks, a visualizer, a jmh directory for the microbenchmarks, docs for the per-heuristic pages, legacy for the migration guide, skills, and test. The build is Maven with a wrapper, and there are SpotBugs exclusions and an Eclipse formatter configuration.

The point calculators deserve a mention because they are the extension point for custom algorithms. Custom packing algorithms can use PointCalculator.addLast(point, placement) for their final box to avoid calculating unused free space, and the calculator should be cleared or restored before continuing a search. The contract and an example are in the point calculators documentation.

Editorial conclusion

The library fits a Java team solving pallet, container or shipment loading where box dimensions, weights and stacking rules are known and the result has to be reproducible, and it fits a small-order case where exact search is affordable. It is the wrong choice if you need an optimal volume guarantee on large item counts, since the heuristics trade optimality for predictable run time, and the wrong choice if your domain is irregular shapes, since only rectangular items are modelled. Verify first which packager covers the features you need, using FEATURES.md, which is generated from the conformance tests, and read the migration guide before moving from the 4.x branch to 5.0.

Frequently asked questions

Official sources

1. Issues
2. License: Apache-2.0
3. README
4. skjolber/3d-bin-container-packing on GitHub