VRP Variants

The Bin Packing Problem (BPP)

The problem consists of packing a set of items into a number of bins such that the total weight, volume, etc. of each bin does not exceed a maximum value. More precisely, we define a bin packing problem (BPP) as follows:

we are given a finite set of items, each of which has a weight;
there are precedence constraints between items, such that we incur a (possibly infinite) cost when item j follows item i;
an ordered group is an ordered subset of items such that:
- the total weight of the ordered group does not exceed the bin capacity;
- no cost between adjacent items in the group is infinite;
the primary goal is to create a feasible solution with the minimum number of ordered groups;
when two solutions use the same number of ordered groups, the one with the minimum aggregate cost is chosen.

Mathematically, the problem can be formulated as follows: given a finite set of elements $E = {e1, …, en}$ with associated weights $W = {w1, …, wn}$ such that $0 ≤ w_i ≤ w(bin)$ , partition $E$ into $N$ subsets such that the sum of the weights in each part is at most $w(bin)$ and $N$ is minimum.

A typical input for the BPP and its corresponding output are shown in the figures below.

A set of items of different sizes given as input to the bin packing problem — Figure 1: Input for the BPP.

The same items packed into a minimum number of bins — Figure 2: Output of the BPP.

The BPP is the "loading side" of vehicle routing: checking whether the customers assigned to a route can be served by a single vehicle is exactly a bin packing feasibility question, and minimizing the number of vehicles in the CVRP is a bin packing objective. The BPP is NP-hard.