Crate bin_packer_3d

This crate solves the problem of “fitting smaller boxes inside of a larger box” using a three dimensional fitting algorithm.

The algorithm orthogonally packs the all the items into a minimum number of bins by leveraging a First Fit Decreasing greedy strategy, along with rotational optimizations.

Usage:

    use bin_packer_3d::bin::Bin;
    use bin_packer_3d::item::Item;
    use bin_packer_3d::packing_algorithm::packing_algorithm;

    let deck = Item::new("deck", [2, 8, 12]);
    let die = Item::new("die", [8, 8, 8]);
    let items = vec![deck, deck, die, deck, deck];

    let packed_items = packing_algorithm(Bin::new([8, 8, 12]), &items);
    assert_eq!(packed_items, Ok(vec![vec!["deck", "deck", "deck", "deck"], vec!["die"]]));

Limitations:

This algorithm solves a constrained version of the 3D bin packing problem. As such, we have the following limitations:

• The items we are packing, and the bins that we are packing them into, are limited to cuboid shapes.

• The items we are packing can be rotated in any direction, with the limitation that each edge must be parallel to the corresponding bin edge.

• As an NP-Hard problem, this algorithm does not attempt to find the optimal solution, but instead uses an approximation that runs with a time complexity of O(n^2)

Acknowledgements:

The algorithm leverages a rotational optimization when packing items which are less than half the length of a bin’s side, as proposed in the paper titled “The Three-Dimensional Bin Packing Problem” (Martello, 1997), page 257: https://www.jstor.org/stable/pdf/223143.pdf

Modules

bin

A struct representing the dimensions of the bin, which will be used for packing.

error

Defines an Error type and a Result type, which can be raised from the packing algorithm.

item

A struct representing the items we’ll be packing into the bin.

packing_algorithm

Defines the function that will be used for our packing algorithm.