Bin Packing

April 21, 2023

TLDR; A journey to create a simple bin packing strategy that minimizes the quantity of bins used, finds the smallest bin for packed item(s), and adds bins until all items are packed.

Requirements

To accurately calculate shipping costs for Brown Hockey customers, I needed a bin packing algorithm that could take a list of products, and determine an efficient, human executable, packing solution given a set of fixed box sizes. Preferrably this algorithm would be written in TypeScript or JavaScript, so I could easily drop it into the website code base. Many of the solutions I found on NPM were old, defunct, unmaintained, and/or did not have test coverage. The one package that stood out in the JavaScript pile was BinPackingJS.

BinPackingJS had good test coverage, it supported 2D and 3D bin packing, it wasn't too old (last updated two years ago), it had a number of maintainers, decent weekly usage, and a few stale pull-requests. It was the best solution I could find in JavaScript and I hoped it would work for my needs.

Close, but not quite

At first glance, the package passed all of my simple bin packing tests, but more complex test cases highlighted its short-comings. The package appeared to lack the ability to minimize the quantity of bins used, it seldom found the smallest bin for an item, and if more bins were needed it didn't add them.

describe('Packer', () => {
  test('No bins to pack', () => { … })
  test('No items to pack', () => { … })
  test('Item does not fit in bin', () => { … })
  test('Item fits in bin', () => { … })
  test('Rotated item fits in bin', () => { … })
  test('Multiple items fit in bin', () => { … })
  test('Too many items, no bins added', () => { … })
  test('Bin ids do NOT need to be unique', () => { … })
  test('Item exceeds max weight for bin', () => { … })
  test('Many items exceed max weight for box', () => { … })

  test('Does not minimize bins used', () => {
    const item1 = { id: 'abc', width: 20, height: 30, depth: 10, weight: 1 }
    const item2 = { id: 'def', width: 20, height: 20, depth: 10, weight: 1 }

    const bin1 = { id: '123', width: 20, height: 30, depth: 10, maxWeight: 10, volume: 6000 }
    const bin2 = { id: '456', width: 20, height: 20, depth: 10, maxWeight: 10, volume: 4000 }
    const bin3 = { id: '789', width: 20, height: 30, depth: 20, maxWeight: 10, volume: 12000 }
    
    const bins: Bin[] = [bin1, bin2, bin3]
    const items: Item[] = [item1, item2]
    const results = pack(bins, items)

    const expected = {
      manifest: [
        { id: bin2.id, items: [item2.id], remainingVolume: 0 },
        { id: bin1.id, items: [item1.id], remainingVolume: 0 },
        // Ideal solution: { id: bin3.id, items: [item1.id, item2.id] },
      ],
      unfitItemIds: []
    }
    expect(results).toEqual(expected)
  })
})

While testing the package, I started to realize I was probably not using the package in the way the original authors had intended. I needed a bin packing solution that minimized bins used, found the smallest bin for the packed item(s), and added bins until all items were packed. As it was, the package wouldn't meet those needs.

Leveraging Strengths

I have been spoiled with the quantity and quality of packages available these days, and instead of initially deciding to work with the package as-is, I opted to continue searching for alternative solutions. Once again, I came up empty handed. I could see that other people were running into similar issues as me, and alternative packages were popping up, but none solved any of my problems, or they were lacking essentials to be trustworthy enough to use in production. BinPackingJS was still the best solution for the language I was working in.

I reluctantly decided to try and modify the behaviour of the package. I encapsulated the package to protect my project from any unexpected package changes. I kept the original unit tests I wrote, added simple value types, and charged forward with hope that I could improve the bin packing results. The first iteration simply added more bins if there wasn't enough. It was very crude, but it solved a bin test I had.

function pack(availableBins: Bin[], items: Item[], unlimitedBins: boolean): PackingResult {
  const itemCount = items.length
  const binCount = unlimitedBins ? (itemCount > 1 ? itemCount : 1) : 1

  const makeBin = (bin: Bin) => new PackBin(bin.id, bin.width, bin.height, bin.depth, bin.maxWeight)
  const makeItem = (item: Bin) => new PackItem(item.id, item.width, item.height, item.depth, item.weight)

  const internalBins = availableBins.flatMap(bin => Array.from({ length: binCount }, () => makeBin(bin)))
  const internalItems = items.map(makeItem)

  const packer = new Packer()
  internalBins.forEach(bin => packer.addBin(bin))
  internalItems.forEach(item => packer.addItem(item))
  packer.pack()

  const unfitItemIds: string[] = packer.unfitItems.map((item: any) => item.name)
  const manifest: BinManifest[] = internalBins
    .filter(bin => bin.items.length > 0)
    .map(bin => ({ id: bin.name, items: bin.items.map((i: any) => i.name) }))

  return { manifest, unfitItemIds }
}

This ugly first attempt gave me the confidence to push forward. It did not thoroughly solve the "add more bins" problem, but it was a stepping stone to solving other problems. The code quickly exploded out of control, as I wrote a lot of unnecessary code, while attempting to wrap my head around this problem. I moved the packing strategies from the BinPackingJS wrapper into their own file to keep things simple. As I wildly explored the solutions my brain was suggesting, I began to slowly understand the strengths and weaknesses of BinPackingJS.

BinPackingJS is really good at finding a packing solution for one bin and many items.

The package handles rotating and limiting the weight of items for the bin really well. It was good at packing one bin and multiple items, or at least good enough for my needs. Building around the idea of "one bin at a time" felt like the next logical step.

Better fit

Optimizating bin sizes was important to get the best shipping costs for Brown Hockey customers. The BinPackingJS package would often put items in bins that were excessively large. I began by brainstorming and visualizing the steps I might take to pack a bin (corrugated box) in front of me. Such as:

Grab a bin
Put item in bin: Is item too big? Is bin too big?
Try another bin size

This exercise coupled with my basic understanding of BinPackingJS' strengths helped me to focus on iteratively packing one bin. I cobbled together a recursive solution of finding smaller bins for the packed items. My conditional logic was flawed in the smaller bin comparison, but I didn't notice it until much later.

function tryPackingBox(binSizes: Bin[], items: Item[], previousResult?: PackingResult): PackingResult {
  if (items.length === 0) {
    return { manifest: [], unfitItemIds: [] }
  } else if (binSizes.length === 0) {
    return { manifest: [], unfitItemIds: items.map(item => item.id) }
  } else {
    return packBox(binSizes, items)
  }
}

function packBox(binSizes: Bin[], items: Item[]): PackingResult {
  const currentBin = binSizes[0]
  const smallerBins = binSizes.slice(1)
  const hasSmallerBoxes = smallerBins.length > 0
  const result = pack([currentBin], items)
  return hasSmallerBoxes ? findSmallerBox(smallerBins, items, result) : result
}

function findSmallerBox(binSizes: Bin[], items: Item[], previousResult: PackingResult): PackingResult {
  const alternateResult = tryPackingBox(binSizes, items)
  const smallerBoxIsBetter = alternateResult.manifest.length >= previousResult.manifest.length
    && alternateResult.unfitItemIds.length <= previousResult.unfitItemIds.length
  return smallerBoxIsBetter ? alternateResult : previousResult
}

Early versions of this code stopped at the first smaller bin found. I quickly realized that in some cases an irregular shaped bin could often fit fewer items than a smaller bin. For example, a long skinny rectangle could be the largest volume but it might only fit certain items. The code was changed to traverse down the entire list of bin sizes.

Irregular box shape and standard box shape

Add more bins

At this point in the project I wanted to cleanup my original attempt at packing multiple boxes. It was ugly and unnecessary.

/** The maximum boxes needed equals the quantity of items */
function tryPackingBoxes(binSizes: Bin[], items: Item[]): PackingResult {
  const unfitItemIds = items.map(item => item.id)
  const initialResult: PackingResult = { manifest: [], unfitItemIds }
  return items.reduce(result => packNextBox(binSizes, items, result), initialResult)
}

function packNextBox(binSizes: Bin[], items: Item[], previousResult: PackingResult) {
  const finishedPacking = previousResult.unfitItemIds.length === 0

  const packMore = () => {
    const unpackedItems = getItems(items, previousResult.unfitItemIds)
    const result = tryPackingBox(binSizes, unpackedItems)

    return {
      manifest: [...previousResult.manifest, ...result.manifest],
      unfitItemIds: result.unfitItemIds,
    }
  }

  if (finishedPacking) {
    return previousResult
  } else {
    return packMore()
  }
}

// Helper method… remove in the future
function getItems(items: Item[], itemIds: string[]): Item[] {
  return items.filter(item => itemIds.includes(item.id))
}

I was feeling very positive about my progress, because most unit tests were passing, except for the last one. It was a contrived example, but it was a packing situation I knew would come up, and if I didn't solve it now, it would plague me later on.

Minimize Bins Used
  ✓ No items (4 ms)
  ✓ No bins (2 ms)
  ✓ No boxes fit (8 ms)
  ✓ Item fits (2 ms)
  ✓ Smallest box for item (47 ms)
  ✓ Item does not fit in first box (2 ms)
  ✓ Many items per box (3 ms)
  ✓ Largest bins are packed first (2 ms)
  ✓ Irregular large volume box holds fewer items than a smaller volume box (1 ms)
  ✓ Not all items fit (3 ms)
  ✓ Minimize bins used (12 ms)
  ✕ Pack multiple boxes (15 ms)

As I dug deeper into the failing test, I realized there was a simpler subset of items and bins in my contrived example that would cause a failing test. It was a subtle packing issue that gave terrible results.

const item1 = { id: 'abc', width: 20, height: 20, depth: 10, weight: 1 }
const item2 = { id: 'def', width: 20, height: 20, depth: 10, weight: 1 }
const item3 = { id: 'hij', width: 40, height: 20, depth: 10, weight: 1 }

const bin1 = { id: '123', width: 20, height: 20, depth: 10, maxWeight: 10, volume: 4000 }
const bin2 = { id: '456', width: 40, height: 20, depth: 10, maxWeight: 10, volume: 8000 }

const bins: Bin[] = [bin1, bin2]
const items: Item[] = [item1, item2, item3]

There was a lot of head scratching at this point, but I was determined to figure it out. I struggled to understand what was wrong with the code. I mentally stepped through line by line, and everything appeared to be doing what I expected. I went through all the code multiple times, and it wasn't until I sat down with a piece of paper to track the output of each packing iteration when I finally saw the glaring issue.

The smallest box comparison wasn't taking into account the volume used, or more specifically how much volume was remaining in the current solution compared to the previous solution. It was only comparing the current and previous bin manifest and unfit item counts. I added a property for bin volume, and modified the comparison for smallest bin:

function findSmallerBox(binSizes: Bin[], items: Item[], previousResult: PackingResult): PackingResult {
  const alternateResult = tryPackingBox(binSizes, items)
  const alternateFitCount = alternateResult.manifest.length
  const alternateUnfitCount = alternateResult.unfitItemIds.length
  const alternateVolume = remainingVolume(alternateResult)

  const previousFitCount = previousResult.manifest.length
  const previousUnfitCount = previousResult.unfitItemIds.length
  const previousVolume = remainingVolume(previousResult)

  /** The alternate box reduces volume, with the same or better manifest counts */
  const reducedVolume = alternateFitCount >= previousFitCount &&
    alternateUnfitCount <= previousUnfitCount &&
    alternateVolume < previousVolume
  
  /** The alternate box has a better manifest count, with the same or reduced volume */
  const improvedManifest = alternateFitCount > previousFitCount &&
    alternateUnfitCount < previousUnfitCount &&
    alternateVolume <= previousVolume

  const smallerBoxIsBetter = reducedVolume || improvedManifest
  
  if (smallerBoxIsBetter) {
    return alternateResult
  } else {
    return previousResult
  }
}

export function remainingVolume(result: PackingResult): number {
  return result.manifest.reduce((result, bin) => result + bin.remainingVolume, 0)
}

… and Voila! Green tests across the board. It was a moment of rejoice and delight for me. I had taken multiple stabs at the bin optimization problem sporadically over a few days and I was getting frustrated with the lack of progress in the last leg of the journey. It was nice to sink my teeth into this problem and see it through to completion. I'm very excited to integrate it into the shipping cost estimator for Brown Hockey

TODO

I have one more bin packing strategy I would like to explore, and then I'll make this solution available to others:

Publish a public repo of the code
Publish my first public package on NPM
Connect with the BinPackingJS crew and chat about contributing, eg. add type definitions, add packing strategies, update documentation