Bin-packing algorithms · guh.me - gustavo henrique's personal blog

Some time ago, my boss came to me and said that the warehouse personnel were having a hard time splitting big orders into many boxes, and then having to manually enter tracking codes into our e-commerce system. This had been happening for more than a year, and had never been mentioned to me, but it was obvious that it was something that could be solved (and it’s actually an interesting problem, yay!).

The company had some criteria for separating the items into distinct boxes (the main one being the weight of the items), so I just had to implement a function that would break each order into multiple packages in order to meet the company’s criteria. Everything was a success, but a few days later a report arrived saying that some orders were being split in too many boxes, and the company could lose money by paying more in shipping costs. Obviously, I went to check my code (which was correct, but could be improved), and, after some research, I came across the problem domain of bin-packing. I was unaware of this algorithm research domain (okay, I did not get my degree on Computer Science, but at university they only talked about ordering algorithms ;), and I was fortunate to find that the algorithm I had implemented was the worst of them (Next Fit)… I rolled up my sleeves, and decided to test the other most common algorithms to see what would work best for our business and bring us the best results.

In this article, I briefly introduce each algorithm, display a sample code in Scala (which I used to prototype), and the final algorithm implementation in PHP 7.2, which is the language we use in this e-commerce project.

Please excuse the quality of my Scala code - I’ve not mastered the language yet, and I opted for a solution with some mutability, since it was just a prototype.

Getting started

First of all, I created a few classes to represent the itens and the bins. An item has a single property (weight), and a bin has also a single property (maxWeight), which represents the maximum combined weight of all items in a bin.

import scala.collection.mutable.ListBuffer

case class Item(weight: Int) {
    require(weight > 0, "weight must be a non-negative integer bigger than zero.")
}
case class Bin(maxWeight: Int) {
    require(maxWeight > 0, "maxWeight must be a non-negative integer bigger than zero.")

    protected val items = ListBuffer.empty[Item]

    def isEmpty(): Boolean = items.isEmpty
    def fits(item: Item): Boolean = currentWeight + item.weight <= maxWeight
    def currentWeight(): Int = items.foldLeft(0)((acc, item) => acc + item.weight)
    def remainingWeight(): Int = maxWeight - currentWeight
    def addItem(item: Item): Unit = items += item
    def getItems(): List[Item] = items.toList
    override def toString(): String = s"[${items.map(_.toString).mkString(", ")}]"
}

Then, I defined a list of 23 items with random weights, and the maximum weight of my bins (in this case, 100 units)(since the company is American, they use freedom units, a.k.a. pounds).

val items = List(
    Item(15), Item(55), Item(91),
    Item(56), Item(69), Item(6),
    Item(51), Item(31), Item(18),
    Item(9),  Item(61), Item(63),
    Item(1),  Item(29), Item(38),
    Item(34), Item(14), Item(40),
    Item(33), Item(17), Item(4),
    Item(8),  Item(49)
)

val maxWeight = 100

Nice. Now to the algorithms.

Algorithms

From Wikipedia, the bin packing problem is defined as:

“In the bin packing problem, objects of different volumes must be packed into a finite number of bins or containers each of volume V in a way that minimizes the number of bins used.”

This problem is NP-Hard, which means that it’s really hard and expensive to find the optimal solution, although some algorithms can produce near-optimal solutions with acceptable complexity.

Next fit

On this algorithm, if the item fits in the same bin as the previous item, we put it there; if not, we create a new bin and put it in there. It also has a decreasing order variation (Next Fit Decreasing), where we order the items in descending order before packing them.

def nextFit(items: List[Item]): List[Bin] = {
    val bins = ListBuffer.empty[Bin]
    bins += Bin(maxWeight)

    items.foreach { item =>
        val lastBin = bins.lastOption.get

        if (lastBin.fits(item)) {
            lastBin.addItem(item)
        } else {
            val newBin = Bin(maxWeight)
            newBin.addItem(item)

            bins += newBin
        }
    }

    bins.toList
}

def nextFitDecreasing(items: List[Item]): List[Bin] = {
    nextFit(items.sortWith(_.weight > _.weight))
}

First fit

On this algorithm, we put each item in the first (oldest) bin into which it fits. It also has a decreasing order variation (First Fit Decreasing), where we order the items in descending order before packing them.

def firstFit(items: List[Item]): List[Bin] = {
    val bins = ListBuffer.empty[Bin]
    bins += Bin(maxWeight)

    items.foreach { item =>
        val firstFittingBin = bins
          .find(_.fits(item))
          .getOrElse(Bin(maxWeight))

        // Its a new bin, so we add it to the bins list
        if (firstFittingBin.isEmpty()) {
            bins += firstFittingBin
        }

        firstFittingBin.addItem(item)
    }

    bins.toList
}

def firstFitDecreasing(items: List[Item]): List[Bin] = {
    firstFit(items.sortWith(_.weight > _.weight))
}

Worst fit

On this algorithm, we put each item into the emptiest bin that we have (if there are multiple bins, we put it into the first/oldest one). If the item doesn’t fit into any bin, we create a new one and put it there. It also has a decreasing order variation (Worst Fit Decreasing), where we order the items in descending order before packing them.

def worstFit(items: List[Item]): List[Bin] = {
    val bins = ListBuffer.empty[Bin]
    bins += Bin(maxWeight)

    items.foreach { item =>
        val mostEmptyBin = bins
          .filter(bin => bin.fits(item))
          .sortWith(_.currentWeight < _.currentWeight)
          .headOption
          .getOrElse(Bin(maxWeight))

        // Its a new bin, so we add it to the bins list
        if (mostEmptyBin.isEmpty()) {
            bins += mostEmptyBin
        }

        mostEmptyBin.addItem(item)
    }

    bins.toList
}

def worstFitDecreasing(items: List[Item]): List[Bin] = {
    firstFit(items.sortWith(_.weight > _.weight))
}

There exists other algorithms, and other variations of the aforementioned algorithms, but I have not considered implementing them - they are much more complicated.

Running my Scala worksheet with the items set I created before, I get the following results:

Next fit: 10
Next fit decreasing: 11
First fit: 10
First fit decreasing: 9
Worst fit: 11
Worst fit decreasing: 9

There’s a small difference between the best and the worst performing algorithms (if we ignore complexity), but when we drill it down to real world problems like shipping costs, the numbers start adding up fast and we can see why it’s important to minimize the number of bins.

Final implementation

After finishing the prototype, I choose the First Fit Decreasing algorithm, and I had to implement it for use on our PHP 7.2 codebase. For obvious reasons, I can’t share the original code (which also implements multiple constraints for the bin packing algorithm), therefore, I’m sharing a very similar version of what was implemented.

First, we do have our Item abstraction:

class Item
{
    /**
     * @var int
     */
    protected $weight;

    /**
     * Item constructor.
     *
     * @param int $weight
     */
    public function __construct(int $weight)
    {
        $this->weight = $weight;
    }

    /**
     * Get the weight.
     *
     * @return int
     */
    public function getWeight(): int
    {
        return $this->weight;
    }
}

And our Bin abstraction:

class Bin
{
    /**
     * @var array
     */
    protected $items = [];

    /**
     * @var int
     */
    protected $maximumBinWeight;

    /**
     * Bin constructor.
     *
     * @param int $maximumBinWeight
     */
    public function __construct(int $maximumBinWeight)
    {
        $this->maximumBinWeight = $maximumBinWeight;
    }

    /**
     * Get the packed items.
     *
     * @return array
     */
    public function getItems(): array
    {
        return $this->items;
    }

    /**
     * Adds an item to the bin.
     *
     * @param Item $item
     * @return Bin
     */
    public function addItem(Item $item): Bin
    {
        $this->items[] = $item;

        return $this;
    }

    /**
     * Get the total bin weight.
     *
     * @return int
     */
    public function getTotalWeight() : int
    {
        return array_reduce($this->items, function($acc, $item) {
            return $acc + $item->getWeight();
        }, 0);
    }

    /**
     * Checks if an item fits the bin.
     *
     * @param Item $item
     * @return bool
     */
    public function itemFits(Item $item): bool
    {
        return $item->getWeight() + $this->getTotalWeight() <= $this->maximumBinWeight;
    }
}

Finally, we have our Bin Packing implementation:

class BinPacking
{
    /**
     * @var int
     */
    protected $maximumBinWeight;

    /**
     * BinPacking constructor.
     *
     * @param int $maximumBinWeight
     */
    public function __construct(int $maximumBinWeight)
    {
        $this->maximumBinWeight = $maximumBinWeight;
    }

    /**
     * Packs a list of item into bins.
     *
     * @param array $items
     * @return array
     */
    public function pack(array $items): array
    {
        // Sort in descending order by weight
        usort($items, function($item1, $item2) {
            return $item2->getWeight() - $item1->getWeight();
        });

        // We will use, at most, the same number of items in bins.
        // We will filter out the empty bins at the end
        $bins = [];

        for ($i = 0; $i < count($items); $i++) {
            $bins[$i] = new Bin($this->maximumBinWeight);
        }

        foreach ($items as $item) {
            foreach ($bins as $bin) {
                if ($bin->itemFits($item)) {

                    $bin->addItem($item);
                    break;
                }
            }
        }

        // Remove empty bins
        return array_filter($bins, function($bin) {
            return $bin->getTotalWeight() > 0;
        });
    }
}

Which is used like:

$binPacking = new BinPacking(100);
$binPacking->pack([new Item(5), new Item(20), new Item(49)]);

Not as beautiful as my twisted Scala code, but still pretty simple.

The full code is avaiable on GitHub: https://github.com/guhemama/bin-packing