Bin Packing Problem using GA, PSO, FA, and IWO

This package solves the Bin Packing Problem in MATLAB with four metaheuristic algorithms: Genetic Algorithm (GA), Particle Swarm Optimization (PSO), Firefly Algorithm (FA) and Invasive Weed Optimization (IWO).

In the Bin Packing Problem, a set of items with known sizes must be packed into bins of equal capacity, and the goal is to use as few bins as possible. It is a classic NP-hard problem. Simple rules such as First Fit Decreasing give good packings quickly, but finding the true minimum is hard for large instances. The problem is a good test case for metaheuristics because a solution is a grouping of items, not a vector of numbers.

The problem

There are $n$ items with sizes $v_1, \dots, v_n$ and bins with capacity $V_{\max}$. Let $y_k = 1$ if bin $k$ is used, and $x_{ik} = 1$ if item $i$ goes into bin $k$. The standard model is

with all $x_{ik}$ and $y_k$ binary. Every item goes into exactly one bin, and the items in a used bin must fit in its capacity.

The sample model in CreateModel.m has 30 items with sizes from 2 to 12 and a bin capacity of 30.

How a solution is decoded into bins

The code does not use the binary variables directly. A solution is a permutation of the numbers 1 to $2n - 1$ (59 numbers for 30 items). The numbers 1 to $n$ are items. The numbers above $n$ are separators. Reading the permutation from left to right, each separator closes the current bin and opens a new one. Empty groups are dropped, so two separators in a row do not create an empty bin.

With $n - 1$ separators, a solution can have between 1 and $n$ bins. This encoding lets the algorithms change both the order of the items and the number of bins with simple moves.

• GA. Each individual is the permutation itself. The GA uses roulette wheel selection, permutation crossover and three mutation moves (swap, reversion and insertion).
• PSO, FA and IWO. These algorithms work with real numbers in $[0, 1]$. BinPackingCost.m sorts the real vector, and the sort order gives the permutation. Mutate.m swaps two values to make small changes.

The cost function

BinPackingCost.m returns the number of bins plus a penalty for overfull bins:

Here $V_k$ is the total size of the items in bin $k$. The penalty is the mean relative violation of the capacity. Its weight is $\alpha = 10n$ in the GA folder and $\alpha = 2n$ in the PSO, FA and IWO folder. A solution with no violation is feasible, and its cost is just the number of bins.

What is in the download

The download has two folders:

• GA version: ga.m with the helper files PermutationCrossover.m, PermutationMutate.m and RouletteWheelSelection.m.
• PSO, FA and IWO version: pso.m, fa.m, iwo.m and Mutate.m.

Each folder also has CreateModel.m, which defines the item sizes and the bin capacity, and BinPackingCost.m, which computes the cost of a solution. The cost combines the number of bins used with a penalty for bins that exceed the capacity. In the second folder, main.m opens a dialog where you choose PSO, FA or IWO.

How to run

Open one of the two folders in MATLAB and run main.m. In the GA folder, main.m starts ga.m directly. The program prints the best cost in every iteration and plots the best cost at the end. To pack your own items, change model.v and model.Vmax in CreateModel.m. The code calls randsample and unifrnd, so it probably needs the Statistics and Machine Learning Toolbox.

Parameters in the code

Check the result

Inspect the decoded bins and verify that every item appears exactly once and no bin exceeds capacity. Report the number of feasible bins separately from the penalized score. The GA and continuous-search folders use different penalty weights, so their raw costs are not directly comparable for infeasible solutions. A simple lower bound is the total item size divided by capacity, rounded up, although that bound need not be attainable.

Applications

Bin packing appears whenever items must be grouped into containers of fixed size:

• Loading trucks, pallets and shipping containers.
• Cutting stock: cutting pieces from standard rolls or bars with little waste.
• Memory allocation and file storage on disks of fixed size.
• Assigning tasks to machines or servers with a fixed time or capacity limit.

Related posts

• Genetic Algorithms in MATLAB
• Particle Swarm Optimization in MATLAB
• Firefly Algorithm in MATLAB
• Invasive Weed Optimization in MATLAB
• Parallel Machine Scheduling using Simulated Annealing, which uses the same separator encoding.

Mostapha Kalami Heris, Bin Packing Problem using GA, PSO, FA, and IWO (YPAP105), Yarpiz, 2015. https://yarpiz.com/bin-packing-problem-ypap105

@misc{yarpiz-ypap105,
  author = {{Mostapha Kalami Heris}},
  title = {{Bin Packing Problem using GA, PSO, FA, and IWO}},
  howpublished = {Yarpiz},
  year = {2015},
  note = {Code YPAP105},
  url = {https://yarpiz.com/bin-packing-problem-ypap105}
}