Rectangular Bin-Packing Problem: a computational evaluation of 4 heuristics algorithms
Article Sidebar
Main Article Content
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
Article Details
Authors who publish with this journal agree to the following terms:
- Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.
- Authors grant the journal the rights to provide the article in all forms and media so the article can be used on the latest technology even after publication and ensure its long-term preservation.
- Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.
- Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work (See The Effect of Open Access).