1D & 2D bin packing

Heuristics for 1D and 2D bin packing

The two-dimensional rectangle bin packing is a classical problem in combinatorial optimization. In this problem, one is given a sequence of rectangles and the task is to pack these items into a minimum number of bins of size (W;H). No two rectangles may intersect or be contained inside one another. This problem has several real-world applications and is proven to be NP-hard by a reduction from the 2-partition problem. A lot of work has been done to develop efficient heuristic algorithms that approximate the optimal solution. The two-dimensional bin packing problem is a generalization of the one-dimensional bin packing problem.

In this web application you can visualize step by step some of the heuristic algorithms with your own data or with random data as the input.

Choose dimension of bin packing

Choose source of data

Set input data

Set height of stripes:
Set size of the bin:
Set size of rectangles:
Set size of the bin:
List of heights of stripes to pack:
Set size of the bin:
List of sizes of rectangles to pack:
Set size of bin:

Choose heuristic

Choose type of algorithm:
Choose type of heuristic:
Choose type of heuristic:
Choose heuristic: Waste map improvement
Choose heuristic: Use Rectangle Merge improvement
Animate step by step

Result

5
This text is displayed if your browser does not support HTML5 Canvas.

About

Video source Bin Packing.

Author: Veronika Černohorská
Email:
Czech technical university in Prague 2015

Based on A Thousand Ways to Pack the Bin - A Practical Approach to Two-Dimensional Rectangle Bin Packing Jukka Jylänki source [PDF]

„Proti hluposti se bojovat musí, ale vyhrát se nedá!“ Jan Werich