A reduction approach for solving the rectangle packing area minimization problem
AbstractIn the rectangle packing area minimization problem (RPAMP) we are given a set of rectangles with known dimensions. We have to determine an arrangement of all rectangles, without overlapping, inside an enveloping rectangle of minimum area. The paper presents a generic approach for solving the RPAMP that is based on two algorithms, one for the 2D Knapsack Problem (KP), and the other for the 2D Strip Packing Problem (SPP). In this way, solving an instance of the RPAMP is reduced to solving multiple SPP and KP instances. A fast constructive heuristic is used as SPP algorithm while the KP algorithm is instantiated by a tree search method and a genetic algorithm alternatively. All these SPP and KP methods have been published previously. Finally, the best variants of the resulting RPAMP heuristics are combined within one procedure. The guillotine cutting condition is always observed as an additional constraint. The approach was tested on 15 well-known RPAMP instances (above all MCNC and GSRC instances) and new best solutions were obtained for 10 instances. The computational effort remains acceptable. Moreover, 24 new benchmark instances are introduced and promising results are reported.
Download InfoIf you experience problems downloading a file, check if you have the proper application to view it first. In case of further problems read the IDEAS help page. Note that these files are not on the IDEAS site. Please be patient as the files may be large.
As the access to this document is restricted, you may want to look for a different version under "Related research" (further below) or search for a different version of it.
Bibliographic InfoArticle provided by Elsevier in its journal European Journal of Operational Research.
Volume (Year): 224 (2013)
Issue (Month): 3 ()
Contact details of provider:
Web page: http://www.elsevier.com/locate/eor
Packing; Rectangle packing area minimization problem; Floor planning; Open dimension problem; MCNC; GSRC;
Please report citation or reference errors to , or , if you are the registered author of the cited work, log in to your RePEc Author Service profile, click on "citations" and make appropriate adjustments.:
- Bortfeldt, Andreas & Mack, Daniel, 2007. "A heuristic for the three-dimensional strip packing problem," European Journal of Operational Research, Elsevier, vol. 183(3), pages 1267-1279, December.
- Beasley, J. E., 2004. "A population heuristic for constrained two-dimensional non-guillotine cutting," European Journal of Operational Research, Elsevier, vol. 156(3), pages 601-627, August.
- Baldacci, Roberto & Boschetti, Marco A., 2007. "A cutting-plane approach for the two-dimensional orthogonal non-guillotine cutting problem," European Journal of Operational Research, Elsevier, vol. 183(3), pages 1136-1149, December.
- Hadjiconstantinou, Eleni & Iori, Manuel, 2007. "A hybrid genetic algorithm for the two-dimensional single large object placement problem," European Journal of Operational Research, Elsevier, vol. 183(3), pages 1150-1166, December.
- Wang, Pearl Y. & Valenzela, Christine L., 2001. "Data set generation for rectangular placement problems," European Journal of Operational Research, Elsevier, vol. 134(2), pages 378-391, October.
- Allen, S.D. & Burke, E.K. & Kendall, G., 2011. "A hybrid placement strategy for the three-dimensional strip packing problem," European Journal of Operational Research, Elsevier, vol. 209(3), pages 219-227, March.
- Leung, Stephen C.H. & Zhang, Defu & Sim, Kwang Mong, 2011. "A two-stage intelligent search algorithm for the two-dimensional strip packing problem," European Journal of Operational Research, Elsevier, vol. 215(1), pages 57-69, November.
- Imahori, S. & Yagiura, M. & Ibaraki, T., 2005. "Improved local search algorithms for the rectangle packing problem with general spatial costs," European Journal of Operational Research, Elsevier, vol. 167(1), pages 48-67, November.
- Bortfeldt, Andreas & Gehring, Hermann, 2001. "A hybrid genetic algorithm for the container loading problem," European Journal of Operational Research, Elsevier, vol. 131(1), pages 143-161, May.
- Wu, Yu-Liang & Huang, Wenqi & Lau, Siu-chung & Wong, C. K. & Young, Gilbert H., 2002. "An effective quasi-human based heuristic for solving the rectangle packing problem," European Journal of Operational Research, Elsevier, vol. 141(2), pages 341-358, September.
- Wascher, Gerhard & Hau[ss]ner, Heike & Schumann, Holger, 2007. "An improved typology of cutting and packing problems," European Journal of Operational Research, Elsevier, vol. 183(3), pages 1109-1130, December.
For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: (Zhang, Lei).
If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.
If references are entirely missing, you can add them using this form.
If the full references list an item that is present in RePEc, but the system did not link to it, you can help with this form.
If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your profile, as there may be some citations waiting for confirmation.
Please note that corrections may take a couple of weeks to filter through the various RePEc services.