The two-dimensional bin packing problem (2BPP) is an NP-Hard problem which has been subject of research in combinatorial optimization for quite some time now.
2BPP is concerned with packing two-dimensional items in two-dimensional bins. The version of the 2BPP that we considered here is referred to as rectangular bin packing problem since the bins and the items are rectangular.
The one-dimensional bin packing problem, which is a special case of 2BPP, was one of the problem chosen in the CHeSC-2011 challenge for cross-domain search techniques.
There are several data structures proposed to track the free spaces in the bins after packing items such as the shelf data structure. In this implementation we used the maximal space data structure which is the most efficient for such a problem. Please read this paper for further information.
The placement (the exact location of the item) of the items inside the bin is determined by a packing heuristic that selects an appropriate free maximal space to place the item in. Three packing heuristics are implemented which are
- Best area fit.
- Touching perimeter.
- Distance to the front-top-right corner.
The benchmark dataset is grouped into 10 classes. Each class is subdivided into 5 categories. Each category contains 10 instances of sizes 20, 40, 60, 80 or 100. In total, there are 500 instances. Most of the instances from categories (60 and above) are not solved optimally. Therefore, there is a room for improvement.
You can download the dataset from here.
You can easily use my implementation as explained below
# Create an instance of the two-dimensional bin packing problem seeded with 12345
problem = RectPacking(12345)
# Read the problem instance file
problem.loadInstance(filename)
# The problem file consists of 50 instances. We need to define which instance we are solving
problem.setInstanceID(0)
# Create an initial solution
solution = problem.initializeSolution()
# Check if the solution is feasible (valid)
if not solution.isFeasible():
raise RuntimeError("Infeasible solution")
print("Number of bins (using best area fit heuristic) = ", solution.getNumberOfBins())The above example create a solution in which the items are packed using the default packing heuristic which is best area fit. To pack the items using other packing heuristics do the following:
# Create an instance of the two-dimensional bin packing problem seeded with 12345
problem = RectPacking(12345)
# Read the problem instance file
problem.loadInstance(filename)
# The problem file consists of 50 instances. We need to define which instance we are solving
problem.setInstanceID(0)
# Create an empty solution (does not have bins)
solution = problem.getEmptySolution()
# Get the items to be packed
queue = problem.getPackingQueue()
# You can shuffle or sort it
random.shuffle(queue) # assuming you imported `random` library
solution.pack(queue, RectPacking.PackingHeuristic.TouchingPerimeter);
# Check if the solution is feasible (valid)
if not solution.isFeasible():
raise RuntimeError("Infeasible solution")
print("Number of bins (using touching perimeter heuristic) = ", solution.getNumberOfBins())If you prefer Java, I have a Java implementation over here. It is faster than the Python implementation.