HEURISTICS WITH STOCHASTIC NEIGHBORHOOD STRUCTURES FOR TWO-DIMENSIONAL BIN PACKING AND CUTTING STOCK PROBLEMS

T. M. Chan, Filipe Alvelos, Elsa Silva () and J. M. Valério de Carvalho
Additional contact information
T. M. Chan: Centro de Investigação Algoritmi, Universidade do Minho, 4710-057 Braga, Portugal
Filipe Alvelos: Centro de Investigação Algoritmi, Universidade do Minho, 4710-057 Braga, Portugal;
Elsa Silva: Centro de Investigação Algoritmi, Universidade do Minho, 4710-057 Braga, Portugal
J. M. Valério de Carvalho: Centro de Investigação Algoritmi, Universidade do Minho, 4710-057 Braga, Portugal;

Asia-Pacific Journal of Operational Research (APJOR), 2011, vol. 28, issue 02, 255-278

Abstract: This paper proposes a heuristic with stochastic neighborhood structures (SNS) to solve two-stage and three-stage two-dimensional guillotine bin packing and cutting stock problems. A solution is represented as a sequence of items which are packed into existing or new stacks, shelves or bins according to previously defined criteria. Moreover, SNS comprises three random neighborhood structures based on modifying the current sequence of items. These are called cut-and-paste, split, and swap blocks and are applied one by one in a fixed order to try to improve the quality of the current solution. Both benchmark instances and real-world instances provided by furniture companies were utilized in the computational tests. Particularly, all benchmark instances are bin packing instances (i.e., the demand of each item type is small), and all real-world instances are classified into bin packing instances and cutting stock instances (i.e., the demand of each item type is large). The computational results obtained by the proposed method are compared with lower bounds and with the solutions obtained by a deterministic Variable Neighborhood Descent (VND) meta-heuristic. The SNS provide solutions within a small percentage of the optimal values, and generally make significant improvements in cutting stock instances and slight to moderate improvements in bin packing instances over the VND approach.

Keywords: Two dimensional bin packing and cutting stock problems; 2D rectangular SBSBPP; guillotine cut; local search; stochastic neighborhood structures (search for similar items in EconPapers)
Date: 2011
References: View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://www.worldscientific.com/doi/abs/10.1142/S0217595911003168
Access to full text is restricted to subscribers

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:wsi:apjorx:v:28:y:2011:i:02:n:s0217595911003168

Ordering information: This journal article can be ordered from

DOI: 10.1142/S0217595911003168

Access Statistics for this article

Asia-Pacific Journal of Operational Research (APJOR) is currently edited by Gongyun Zhao

More articles in Asia-Pacific Journal of Operational Research (APJOR) from World Scientific Publishing Co. Pte. Ltd.
Bibliographic data for series maintained by Tai Tone Lim ().