Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

The effect of benchmark data characteristics during empirical strip packing heuristic performance evaluation

  • Regular Article
  • Published:
OR Spectrum Aims and scope Submit manuscript

Abstract

In this paper, we consider the two-dimensional strip packing problem in which a fixed set of items has to be packed into a single object of unlimited height with the aim of minimising the packing height. A new, systematic way of comparing the relative performances of packing algorithms is proposed. A large set of strip packing benchmark instances from various repositories in the literature is clustered into different classes of test problems based on their underlying features. We compare a representative sample of existing strip packing heuristics in terms of solution quality in respect of the clustered data. The effectiveness of the designs of the different algorithms is contrasted for each of the data categories. It is found that the aspects of the test problems affect the solution qualities and relative rankings achieved by the various packing algorithms, but that no single heuristic is superior in respect of all the data categories.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7

Similar content being viewed by others

Notes

  1. The larger the data set, the larger the value of d should be chosen.

References

  • Aggarwal CC, Reddy CK (2013) Data clustering: algorithms and applications. CRC Press, New York (NY)

    Google Scholar 

  • Alvarez-Valdes R, Parreno F, Tamarit JM (2005) A grasp algorithm for constrained two-dimensional non-guillotine cutting problems. J Oper Res Soc 56:414–425

    Google Scholar 

  • Alvarez-Valdés R, Parreño F, Tamarit JM (2008) Reactive grasp for the strip-packing problem. Comput Oper Res 35:1065–1083

    Google Scholar 

  • Babu AR, Babu NR (1999) Effective nesting of rectangular parts in multiple rectangular sheets using genetic and heuristic algorithms. Int J Prod Res 37:1625–1643

    Google Scholar 

  • Bach FR, Jordan MI (2004) Learning spectral clustering. In: Advances in neural information processing systems, pp 305–312

  • Baker BS, Coffman EG Jr, Rivest RL (1980) Orthogonal packings in two dimensions. SIAM J Comput 9:846–855

    Google Scholar 

  • Beasley J (1985a) Algorithms for unconstrained two-dimensional guillotine cutting. J Oper Res Soc 36:297–306

    Google Scholar 

  • Beasley J (1985b) An exact two-dimensional non-guillotine cutting tree search procedure. Oper Res 33:49–64

    Google Scholar 

  • Belov G, Scheithauer G, Mukhacheva E (2008) One-dimensional heuristics adapted for two-dimensional rectangular strip packing. J Oper Res Soc 59:823–832

    Google Scholar 

  • Bengtsson B (1982) Packing rectangular pieces—a heuristic approach. Comput J 25:353–357

    Google Scholar 

  • Berkey J, Wang P (1987) Two-dimensional finite bin-packing algorithms. J Oper Res Soc 38:423–429

    Google Scholar 

  • Bologna ORG (2017) Library of instances. http://or.dei.unibo.it/library/two-dimensional-bin-packing-problem

  • Bortfeldt A (2006) A genetic algorithm for the two-dimensional strip packing problem with rectangular pieces. Eur J Oper Res 172:814–837

    Google Scholar 

  • Bortfeldt A, Gehring H (2006) New large benchmark instances for the two-dimensional strip packing problem with rectangular pieces. In: Annual Hawaii International Conference on System Sciences 39, p 30). Kauai (HI)

  • Burke E, Kendall G, Whitwell G (2004) A new placement heuristic for the orthogonal stock-cutting problem. Oper Res 52:655–671

    Google Scholar 

  • Burke EK, Kendall G (1999) Applying simulated annealing and the no fit polygon to the nesting problem. In: World Manufacturing Congress, pp 27–30. Durham

  • Burke EK, Kendall G, Whitwell G (2009) A simulated annealing enhancement of the best-fit heuristic for the orthogonal stock-cutting problem. INFORMS J Comput 21:505–516

    Google Scholar 

  • Calinski T, Harabasz J (1974) A dendrite method for cluster analysis. Commun Stat-Theory Methods 3:1–27

  • Charrad M, Ghazzali N, Boiteau V, Niknafs A, Charrad MM (2014) Package nbclust. J Stat Softw 61:1–36

    Google Scholar 

  • Chazelle B (1983) The bottom-left bin-packing heuristic: an efficient implementation. Comput IEEE Trans Comput 100:697–707

    Google Scholar 

  • Chen Z, Chen J (2018) An effective corner increment-based algorithm for the two-dimensional strip packing problem. IEEE Access 6:72906–72924

    Google Scholar 

  • Christofides N, Whitlock C (1977) An algorithm for two-dimensional cutting problems. Oper Res 25:30–44

    Google Scholar 

  • Dagli C, Poshyanonda P (1997) New approaches to nesting rectangular patterns. J Intell Manuf 8:177–190

    Google Scholar 

  • Davies DL, Bouldin DW (1979) A cluster separation measure. In: IEEE transactions on pattern analysis and machine intelligence, pp 224–227

  • Dunn JC (1974) Well-separated clusters and optimal fuzzy partitions. J Cybern 4:95–104

    Google Scholar 

  • Elbatta MT, Ashour WM (2013) A dynamic method for discovering density varied clusters. Int J Signal Process Image Process Pattern Recognit 6:123–134

    Google Scholar 

  • ESICUP (2015) Datasets 2d-rectangular. http://paginas.fe.up.pt/~esicup/datasets?category_id=3

  • Ester M, Kriegel H-P, Sander J, Xu X, et al (1996) A density-based algorithm for discovering clusters in large spatial databases with noise. In: \(2^{nd}\) International Conference on Knowledge Discovery and Data Mining 34, pp 226–231. Portland (OR)

  • Ferreira EP, Oliveira JF (2005) Algorithm based on graphs for the non-guillotinable two-dimensional packing problem. In: Proceedings of the \(2^{nd}\) ESICUP Meeting, Southampton (p. none)

  • Halkidi M, Batistakis Y, Vazirgiannis M (2000) Quality scheme assessment in the clustering process. In: Principles of Data Mining and Knowledge Discovery. Springer, Berlin, pp 265–276

  • Halkidi M, Batistakis Y, Vazirgiannis M (2001) On clustering validation techniques. J Intell Inf Syst 17:107–145

    Google Scholar 

  • Halkidi M, Vazirgiannis M (2001) Clustering validity assessment: finding the optimal partitioning of a data set. In: International conference on data mining, pp 187–194. San Jose (CA)

  • Hifi M (1998) Exact algorithms for the guillotine strip cutting and packing problem. Comput Oper Res 25:925–940

    Google Scholar 

  • Hifi M (1999) The strip cutting and packing problem: incremental substrip algorithms-based heuristics. Pesquisa Oper 19:169–188

    Google Scholar 

  • Hifi M (2004) Library of instances. ftp://cermsem.univ-paris1.fr/pub/CERMSEM/hifi/Strip-cutting/

  • Hopper E, Turton B (2001) An empirical investigation of meta-heuristic and heuristic algorithms for a 2d packing problem. Eur J Oper Res 128:34–57

    Google Scholar 

  • Hopper E, Turton B (2002) Problem generators for rectangular packing problems. Stud Inf Univ 2:123–136

    Google Scholar 

  • Hwang SM, Kao CY, Horng JT (1994) On solving rectangle bin packing problems using genetic algorithms. In: Proceedings of IEEE international conference on systems, man, and cybernetics, pp 1583–1590. San Antonio (TX)

  • Imahori S, Yagiura M (2010a) The best-fit heuristic for the rectangular strip packing problem: an efficient implementation and the worst-case approximation ratio. Comput Oper Res 37:325–333

    Google Scholar 

  • Imahori S, Yagiura M (2010b) Cutting and packing, test instances “strip packing problem”. http://www-or.amp.i.kyoto-u.ac.jp/~imahori/packing/instance.html

  • Jain AK, Dubes RC (1988) Algorithms for clustering data. Prentice-Hall, Upper Saddle River (NJ)

    Google Scholar 

  • Jain AK, Murty MN, Flynn PJ (1999) Data clustering: a review. ACM Comput Surv CSUR 31:264–323

    Google Scholar 

  • Jakobs S (1996) On genetic algorithms for the packing of polygons. Eur J Oper Res 88:165–181

    Google Scholar 

  • Karami A, Johansson R (2014) Choosing dbscan parameters automatically using differential evolution. Int J Comput Appl 91:1–11

    Google Scholar 

  • Kaufman L, Rousseeuw PJ (2009) Finding groups in data: an introduction to cluster analysis, vol 344. Wiley, New York (NY)

    Google Scholar 

  • Kotsiantis S, Kanellopoulos D, Pintelas P (2006) Data preprocessing for supervised leaning. Int J Comput Sci 1:111–117

    Google Scholar 

  • Kröger B (1995) Guillotineable bin packing: a genetic approach. Eur J Oper Res 84:645–661

    Google Scholar 

  • Leung S, Zhang D (2011) A fast layer-based heuristic for non-guillotine strip packing. Expert Syst Appl 38:13032–13042

    Google Scholar 

  • Leung SC, Zhang D, Sim KM (2011) A two-stage intelligent search algorithm for the two-dimensional strip packing problem. Eur J Oper Res 215:57–69

    Google Scholar 

  • Lijun W, Wenbin Z (2011) Skyline heuristic for the 2d rectangular packing and strip packing problems, under “data sets”. https://www.computational-logistics.org/orlib/topic/2D%20Strip%20Packing/index.html

  • Liu D, Teng H (1999) An improved bl-algorithm for genetic algorithm of the orthogonal packing of rectangles. Eur J Oper Res 112:413–420

    Google Scholar 

  • Lodi A, Martello S, Vigo D (1999) Heuristic and metaheuristic approaches for a class of two-dimensional bin packing problems. INFORMS J Comput 11:345–357

    Google Scholar 

  • Martello S, Monaci M, Vigo D (2003) An exact approach to the strip-packing problem. INFORMS J Comput 15:310–319

    Google Scholar 

  • Martello S, Vigo D (1998) Exact solution of the two-dimensional finite bin packing problem. Manag Sci 44:388–399

    Google Scholar 

  • Milligan GW, Cooper MC (1985) An examination of procedures for determining the number of clusters in a data set. Psychometrika 50:159–179

    Google Scholar 

  • Murtagh F (1983) A survey of recent advances in hierarchical clustering algorithms. Comput J 26:354–359

    Google Scholar 

  • Ntene N (2007) An algorithmic approach to the 2D oriented strip packing problem. Phd dissertation Stellenbosch University, Stellenbosch

  • Ortmann FG (2010) Heuristics for offline rectangular packing problems. Phd dissertation Stellenbosch University, Stellenbosch

  • Rakotonirainy RG, Van Vuuren JH (2020) Improved metaheuristic for the two-dimensional strip packing problem. Appl Soft Comput. https://doi.org/10.1016/j.asoc.2020.106268

    Article  Google Scholar 

  • Rousseeuw PJ (1987) Silhouettes: a graphical aid to the interpretation and validation of cluster analysis. J Comput Appl Math 20:53–65

    Google Scholar 

  • Sawant K (2014) Adaptive methods for determining dbscan parameters. Int J Innov Sci Eng Technol 1:329–334

    Google Scholar 

  • Tibshirani R, Walther G, Hastie T (2001) Estimating the number of clusters in a data set via the gap statistic. J R Stat Soc Ser B Stat Methodol 63:411–423

    Google Scholar 

  • Valenzuela CL, Wang PY (2001) Heuristics for large strip packing problems with guillotine patterns: An empirical study. In: Metaheuristics International Conference 4, pp 417–421. Porto

  • Van Vuuren JH, Ortmann FG (2010) Benchmarks. http://www.vuuren.co.za/main.php

  • Van Vuuren JH, Rakotonirainy RG (2018) Benchmarks. http://www.vuuren.co.za/main.php

  • Von Luxburg U (2007) A tutorial on spectral clustering. Stat Comput 17:395–416

    Google Scholar 

  • Wang PY, Valenzuela CL (2001) Data set generation for rectangular placement problems. Eur J Oper Res 134:378–391

    Google Scholar 

  • Wei L, Hu Q, Leung SC, Zhang N (2017) An improved skyline based heuristic for the 2d strip packing problem and its efficient implementation. Comput Oper Res 80:113–127

    Google Scholar 

  • Wei L, Oon W-C, Zhu W, Lim A (2011) A skyline heuristic for the 2d rectangular packing and strip packing problems. Eur J Oper Res 215:337–346

    Google Scholar 

  • Wei L, Qin H, Cheang B, Xu X (2016) An efficient intelligent search algorithm for the two-dimensional rectangular strip packing problem. Int Trans Oper Res 23:65–92

    Google Scholar 

  • Xu R, Wunsch D (2005) Survey of clustering algorithms. IEEE Trans Neural Netw 16:645–678

    Google Scholar 

  • Zelnik-Manor L, Perona P (2005) Self-tuning spectral clustering. In: Advances in Neural Information Processing Systems, pp 1601–1608. Vancouver

  • Zhang D, Kang Y, Deng A (2006) A new heuristic recursive algorithm for the strip rectangular packing problem. Comput Oper Res 33:2209–2217

    Google Scholar 

  • Zhang D-F, Sheng-Da C, Yan-Juan L (2007) An improved heuristic recursive strategy based on genetic algorithm for the strip rectangular packing problem. Acta Autom Sin 33:911–916

    Google Scholar 

Download references

Acknowledgements

This work was financially supported by the Deutscher Akademischer Austauschdienst German Academic Exchange Service (DAAD) in the form of a bursary for the first author.

Author information

Authors and Affiliations

  1. Stellenbosch Unit for Operations Research in Engineering, Department of Industrial Engineering, Stellenbosch University, Private Bag X1, Matieland, 7602, South Africa

    Rosephine G. Rakotonirainy & Jan H. van Vuuren

  2. Department of Statistical Sciences, University of Cape Town, Rondebosch, 7701, South Africa

    Rosephine G. Rakotonirainy

Authors
  1. Rosephine G. Rakotonirainy
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Jan H. van Vuuren
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Rosephine G. Rakotonirainy.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Rakotonirainy, R.G., van Vuuren, J.H. The effect of benchmark data characteristics during empirical strip packing heuristic performance evaluation. OR Spectrum 43, 467–495 (2021). https://doi.org/10.1007/s00291-021-00619-y

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00291-021-00619-y

Keywords

Search

Navigation