2D Bin Packing Problem Solver

This online calculator tries to solve an offline two-dimensional (2D) bin packing problem using Maximal Rectangles heuristic algorithm

This page exists due to the efforts of the following people:

Timur

Timur

Created: 2020-03-07 16:59:18, Last updated: 2023-01-04 16:57:31
Creative Commons Attribution/Share-Alike License 3.0 (Unported)

This content is licensed under Creative Commons Attribution/Share-Alike License 3.0 (Unported). That means you may freely redistribute or modify this content under the same license conditions and must attribute the original author by placing a hyperlink from your site to this work https://planetcalc.com/8634/. Also, please do not modify any references to the original work (if any) contained in this content.

This online calculator should help you answer questions like how many slabs are needed if you fit a series of smaller rectangles of various length and width (LxW) dimensions into larger rectangles with fixed length and width (LxW) dimensions.

For example, you are a countertop maker and need to figure out how many slabs of a certain size you need to order for a job. Thus, the amount of material needed should be broken down into a series of small rectangles (see this request).

Below you should enter the dimensions of the master slab in Length x Width format, then dimensions of rectangular pieces and their quantity, in Length x Width x Quantity format, one type of rectangles per line.

In fact, this is a Two-Dimensional Rectangle Bin Packing problem. The calculator will try to find the best layout it can, but it does not guarantee the optimal solution. For science details, refer to the theory section below the calculator.

PLANETCALC, 2D Bin Packing Problem Solver

2D Bin Packing Problem Solver

Bin Dimensions

Rectangles to Pack

Bins required
 
The file is very large. Browser slowdown may occur during loading and creation.
The file is very large. Browser slowdown may occur during loading and creation.
The file is very large. Browser slowdown may occur during loading and creation.

Two-Dimensional Rectangle Bin Packing

Ok, so here we deal with the Two-Dimensional Rectangle Bin Packing problem. In any bin packing problem, you are given some containers (in our case, the container is a 2D rectangular region). A set of objects (again, in our case, these are smaller rectangles) should be packed into one or more containers. The goal usually is to pack all objects using as few containers as possible.

If the set of objects to be packed is known beforehand, the problem is called 'offline' as opposed to the 'online' problem, where objects appear one by one. So, here we need to deal with the offline 2D rectangle bin packing problem.

This is one of the classical problems in combinatorial optimization and is proven to be NP-hard. So, we can only approximate the optimal solution with heuristic algorithms.

This particular implementation of 2D bin packing problem solver relies on Maximal Rectangles Algorithms. This heuristic is an extension of the Guillotine Split heuristic and shows excellent results for offline packing1

The idea of the Maximal Rectangles heuristic is to keep track of all maximal free rectangular spaces, which are still available after placing an object into the container (see picture below)

Keep track of overlapping rectangles
Keep track of overlapping rectangles

There are also different rules for choosing which rectangle to place into which bin. Here we use the global approach, which means that on each step, we compute 'score' for each remaining rectangle and each remaining free space and choose the combination which gives us the best score. As for particular placement rule, this implementation actually checks four of them and then picks the rule which produces the best result (i.e., uses a minimum amount of bins).

The placement rules are:

  1. Bottom-Left - the y-coordinate of the top side of the rectangle should be the smallest. In the case of a tie, the one with the smallest x-coordinate value is used.
  2. Best Short Side Fit - the free space area should have the minimum length of the shorter leftover side.
  3. Best Long Side Fit - the free space area should have the minimum length of the longer leftover side.
  4. Best Area Fit - the free space area should be the smallest in the area to place the next rectangle into. In case of a tie, the Best Short Side Fit rule is used.
    Update: another heuristics is added to solve the edge case from the comments
  5. Greedy Best Long Side Fit - the same as Best Long Side Fit, but if an item fits perfectly along any side of free space (no side length wasted), this placement is preferred.

  1. A Thousand Ways to Pack the Bin - A Practical Approach to Two-Dimensional Rectangle Bin Packing by Jukka Jylänki 

URL copied to clipboard
PLANETCALC, 2D Bin Packing Problem Solver

Comments