Table of Content

1. Two-Dimensional Bin Packing Problem
2. Data Structure
3. Packing Heuristics
4. Dataset
5. Usage
6. Python

Two-Dimensional Bin Packing Problem

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.

Data Structure

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.

Packing Heuristics

The placement (the location) 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.

Please read this paper to understand these packing heuristics.

Dataset

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.

Usage

You can easily use my implementation as explained below

    //Create an instance of the two-dimensional bin packing problem seeded with 12345
    RectPacking problem = new RectPacking(12345);
    //Read the problem instance file
    problem.read(filename);
    //The problem file consists of 50 instances. We need to define which instance we are solving
    problem.setInstance(0);
    //Create an initial solution
    RBPSolution solution = problem.initializeSolution();
    //Check if the solution is feasible (valid)
    if(!solution.isFeasible()){
        throw new RuntimeException("Infeasible solution");
    }
    System.out.println("Number of bins (using best area fit heuristic) = " + solution.getNumberOfBin());

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
    RectPacking problem = new RectPacking(12345);
    //Read the problem instance file
    problem.read(filename);
    //The problem file consists of 50 instances. We need to define which instance we are solving
    problem.setInstance(0);
    // Create an empty solution (does not have bins)
    RectPacking solution = problem.getEmptySolution();
    //Get the items to be packed
    List<Rect> queue = problem.getPackingQueue();
    //You can shuffle or sort it
    Random rng = new Random(123456);
    Collections.shuffle(queue, rng);
    solution.pack(queue, RectPacking.PackingHeuristic.TouchingPerimeter);
    //Check if the solution is feasible (valid)
    if(!solution.isFeasible()){
        throw new RuntimeException("Infeasible solution");
    }
    System.out.println("Number of bins (using touching perimeter heuristic) = " + solution.getNumberOfBin());

Python

If you prefer Python, I have a Python implementation over here. However, it is slower than the Java implementation.