ASR-0003 Packing Problem

Andi Lamprecht ·2026-05-11· 2 min read· Accepted

Packing Problem

Summary

As part of the delivery api, there is a need to run cart validation. A core function of cart validation is determining if all the items in the cart will fit in the delivery box. This problem is known as the Packing Problem or the Knapsack Problem (read more here: https://en.wikipedia.org/wiki/Bin_packing_problem). Since this problem is NP-hard we must use an approximation algorithm to solve it.

Requirements

1. Accuracy - must accurately report whether or not a given set of items can fit into one or more boxes
2. Speed - must not add undue time to any incoming requests. Target is < 100ms for known cases
3. Maintainability - must be understandable and maintainable by future developers
4. Extensibility - must be able to handle future use cased (estimating the number of boxes and chaning box size)

Proposal

Utilize this libray (https://github.com/gedex/bp3d) which implements this paper (https://github.com/Janet-19/3d-bin-packing-problem/blob/master/Reference/erick_dube_507-034.pdf)

The implementation meets all four of our criteria:

1. Accuracy - algorithm is unit tested and working for multiple scenarios
2. Speed - algorithm is highly performant and has been benchmarked to show runtime of 35089 nanoseconds (35ms) per pack average for known box size an 100 small items
3. Maintainability - algorithm is well commented and straightforward to reason about
4. Extensibility - algorithm allows for custom box sized and knowing which items did not fit for future box need caclulations

Alternatives

utilize https://developers.google.com/optimization/pack/bin_packing
doesn’t support item rotation
doesn’t support height, width, depth

utilize bin packing as a service solution (https://www.3dbinpacking.com/en/)
has a cost per call (https://www.3dbinpacking.com/en/pricing)