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

Main Article Content

Duarte Nuno Gonçalves Ferreira

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.

Downloads

Download data is not yet available.

Article Details

Author Biography

Duarte Nuno Gonçalves Ferreira, Universidade do Porto

Departamento de Engenharia e Gestão Industrial
Faculdade de Engenharia
Universidade do Porto
Rua Dr. Roberto Frias
4200-465 PORTO
Portugal