Rectangular Bin-Packing Problem: a computational evaluation of 4 heuristics algorithms

Abstract

The Rectangular Bin-packing Problem, also known as The Two-dimensional Bin-packing Problem (2DBPP), is a well-known combinatorial optimization problem which is the problem of orthogonally packing a given set of rectangles into a minimum number of two-dimensional rectangular bins. In this article we benchmark four heuristics: constructive, based on a First Fit Decreasing strategy, local search using a greedy packing First-Fit algorithm, Simulated Annealing with multiple cooling values and Genetic Algorithm. All implementations are written in Python, run using the Pypy environment and the new multiprocessing module. All implementations were tested using the Berkey and Wang and Martelo and Vigo Benchmark Instances.

Keywords

• Optimization
• computer programming
• operational research
• Genetic Algorithm
• Simulated Annealing
• Bin packing problems