×

zbMATH — the first resource for mathematics

An efficient intelligent search algorithm for the two-dimensional rectangular strip packing problem. (English) Zbl 1338.90357
Summary: In this paper, we present an efficient intelligent search algorithm for the two-dimensional rectangular strip packing problem. This algorithm involves three stages, namely greedy selection, local improvement, and randomized improvement. The greedy selection stage provides a good initial solution for the local improvement stage, which then tries to improve the solution by a deterministic local search. The randomized improvement stage employs a simple randomized local search process, which does not need any control parameter. Each of these three stages uses a heuristic approach to construct solutions based on an improved scoring rule and the least-waste-first strategy. Extensive experiments show that, to the best of our knowledge, our proposed algorithm performs slightly better than all previously published metaheuristics for most of the benchmark instances.

MSC:
90C27 Combinatorial optimization
90C59 Approximation methods and heuristics in mathematical programming
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Alvarez-Valdes, Reactive GRASP for the strip packing problem, Computers and Operations Research 35 (4) pp 1065– (2008) · Zbl 1179.90269 · doi:10.1016/j.cor.2006.07.004
[2] Alvarez-Valdes, A branch and bound algorithm for the strip packing problem, OR Spectrum 31 (2) pp 431– (2009) · Zbl 1160.90696 · doi:10.1007/s00291-008-0128-5
[3] Baker, Orthogonal packings in two dimensions, SIAM Journal on Computing 9 (4) pp 808– (1980) · Zbl 0447.68080 · doi:10.1137/0209064
[4] Beasley, Algorithms for unconstrained two-dimensional guillotine cutting, Journal of the Operational Research Society 36 (4) pp 297– (1985a) · Zbl 0589.90040 · doi:10.1057/jors.1985.51
[5] Beasley, An exact two-dimensional non-guillotine cutting tree search procedure, Operations Research 33 (1) pp 49– (1985b) · Zbl 0569.90038 · doi:10.1287/opre.33.1.49
[6] Belov, One-dimensional heuristics adapted for two-dimensional rectangular strip packing, Journal of the Operational Research Society 59 (6) pp 823– (2008) · Zbl 1153.90444 · doi:10.1057/palgrave.jors.2602393
[7] Bengtsson, Packing rectangular pieces-a heuristic approach, The Computer Journal 25 (3) pp 253– (1982) · doi:10.1093/comjnl/25.3.353
[8] Berkey, Two-dimensional finite bin packing algorithms, Journal of the Operational Research Society 38 (5) pp 423– (1987) · Zbl 0611.90079 · doi:10.1057/jors.1987.70
[9] Bortfeldt, A genetic algorithm for the two-dimensional strip packing problem with rectangular pieces, European Journal of Operational Research 172 (3) pp 814– (2006) · Zbl 1111.90094 · doi:10.1016/j.ejor.2004.11.016
[10] Bortfeldt , A. Gehring , H. 2006 New large benchmark instances for the two-dimensional strip packing problem with rectangular pieces
[11] Bortfeldt, Constraints in container loading-a state-of-the-art review, European Journal of Operational Research 229 (1) pp 1– (2013) · Zbl 1317.90172 · doi:10.1016/j.ejor.2012.12.006
[12] Burke, A squeaky wheel optimisation methodology for two-dimensional strip packing, Computers & Operations Research 38 (7) pp 1035– (2011) · Zbl 1205.90240 · doi:10.1016/j.cor.2010.10.005
[13] Burke, A new placement heuristic for the orthogonal stock-cutting problem, Operations Research 52 (4) pp 655– (2004) · Zbl 1165.90690 · doi:10.1287/opre.1040.0109
[14] Burke, A simulated annealing enhancement of the best-fit heuristic for the orthogonal stock cutting problem, INFORMS Journal on Computing 21 (3) pp 505– (2009) · Zbl 1243.90254 · doi:10.1287/ijoc.1080.0306
[15] Chazelle, The bottom-left bin packing heuristic: an efficient implementation, IEEE Transaction on Computers 32 (8) pp 697– (1983) · Zbl 0526.68065 · doi:10.1109/TC.1983.1676307
[16] Che, The multiple container loading cost minimization problem, European Journal of Operational Research 214 (3) pp 501– (2011) · Zbl 1226.90085 · doi:10.1016/j.ejor.2011.04.017
[17] Christofides, An algorithm for two-dimensional cutting problems, Operations Research 25 (1) pp 30– (1977) · Zbl 0369.90059 · doi:10.1287/opre.25.1.30
[18] Dowsland, Packing problems, European Journal of Operational Research 56 (1) pp 2– (1992) · Zbl 0825.90355 · doi:10.1016/0377-2217(92)90288-K
[19] Dyckhoff, A typology of cutting and packing problems, European Journal of Operational Research 44 (2) pp 145– (1990) · Zbl 0684.90076 · doi:10.1016/0377-2217(90)90350-K
[20] Garey, Computers and Intractability (1979)
[21] He, An efficient deterministic heuristic for two-dimensional rectangular packing, Computers & Operations Research 39 (7) pp 1355– (2012) · Zbl 1251.90321 · doi:10.1016/j.cor.2011.08.005
[22] Hopper , E. 2000 Two-dimensional packing utilising evolutionary algorithms and other meta-heuristic methods
[23] Hopper, An empirical investigation of meta-heuristic and heuristic algorithms for a 2D packing problem, European Journal of Operational Research 128 (1) pp 34– (2001) · Zbl 0982.90044 · doi:10.1016/S0377-2217(99)00357-4
[24] Imahori, The best-fit heuristic for the rectangular strip packing problem: an efficient implementation and the worst-case approximation ratio, Computers & Operations Research 37 (2) pp 325– (2010) · Zbl 1175.90429 · doi:10.1016/j.cor.2009.05.008
[25] Kenmochi, Exact algorithms for the two-dimensional strip packing problem with and without rotations, European Journal of Operational Research 198 (1) pp 73– (2009) · Zbl 1163.90803 · doi:10.1016/j.ejor.2008.08.020
[26] Leung, A fast layer-based heuristic for non-guillotine strip packing, Expert Systems with Applications 38 (10) pp 13032– (2011) · doi:10.1016/j.eswa.2011.04.105
[27] Leung, A two-stage intelligent search algorithm for the two-dimensional strip packing problem, European Journal of Operational Research 215 (1) pp 57– (2011) · Zbl 06035073 · doi:10.1016/j.ejor.2011.06.002
[28] Lodi, Two-dimensional packing problems: a survey, European Journal of Operational Research 141 (2) pp 241– (2002) · Zbl 1081.90576 · doi:10.1016/S0377-2217(02)00123-6
[29] Lodi, Heuristic and metaheuristic approaches for a class of two-dimensional bin packing problems, INFORMS Journal on Computing 11 (4) pp 345– (1999) · Zbl 1034.90500 · doi:10.1287/ijoc.11.4.345
[30] Martello, Exact solution of the two-dimensional finite bin packing problem, Management Science 44 (3) pp 388– (1998) · Zbl 0989.90114 · doi:10.1287/mnsc.44.3.388
[31] Paquay, A mixed integer programming formulation for the three-dimensional bin packing problem deriving from an air cargo application, International Transactions in Operational Research 23 (1-2) pp 185– (2014) · Zbl 1338.90350
[32] Pedroso, Recursive circle packing problems, International Transactions in Operational Research 23 (1-2) pp 353– (2014)
[33] Pinto , E. Oliveira , J.F. 2005 Algorithm based on graphs for the non-guillotinable two-dimensional packing problem
[34] Valenzuela , C.L. Wang , P.Y. 2001 Heuristics for large strip packing problems with guillotine patterns: an empirical study
[35] Verstichel, An improved best-fit heuristic for the orthogonal strip packing problem, International Transactions in Operational Research 20 (5) pp 711– (2013) · Zbl 1274.90330 · doi:10.1111/itor.12030
[36] W√§scher, An improved typology of cutting and packing problems, European Journal of Operational Research 183 (3) pp 1109– (2007) · Zbl 1278.90347 · doi:10.1016/j.ejor.2005.12.047
[37] Wei, A skyline heuristic for the 2D rectangular packing and strip packing problems, European Journal of Operational Research 215 (2) pp 337– (2011) · Zbl 1237.90213
[38] Wei, A reference length approach for the 3D strip packing problem, European Journal of Operational Research 220 (1) pp 37– (2012) · Zbl 1253.90142 · doi:10.1016/j.ejor.2012.01.039
[39] Wei, A goal-driven approach to the 2D bin packing and variable-sized bin packing problems, European Journal of Operational Research 224 (1) pp 110– (2013) · Zbl 1292.90174 · doi:10.1016/j.ejor.2012.08.005
[40] Wei, A least wasted first heuristic algorithm for the rectangular packing problem, Computers & Operations Research 36 (5) pp 1608– (2009) · Zbl 1179.90174 · doi:10.1016/j.cor.2008.03.004
[41] Yang, A simple randomized algorithm for two-dimensional strip packing, Computers & Operations Research 40 (1) pp 1– (2013) · Zbl 1349.90726 · doi:10.1016/j.cor.2012.05.001
[42] Zhang, An improved heuristic recursive strategy for genetic algorithm of the orthogonal packing of rectangles, Acta Automatica Sinica 33 (9) pp 911– (2007) · Zbl 1164.90430 · doi:10.1360/aas-007-0911
[43] Zhang, A new heuristic recursive algorithm for the strip rectangular packing problem, Computers & Operations Research 33 (8) pp 2209– (2006) · Zbl 1086.90068 · doi:10.1016/j.cor.2005.01.009
[44] Zhang, meta-heuristic algorithm for the strip rectangular packing problem, Advances in Natural Computation, LNCS 3612 pp 1235– (2005) · doi:10.1007/11539902_157
[45] Zhu, A new iterative-doubling Greedy-Lookahead algorithm for the single container loading problem, European Journal of Operational Research 222 (3) pp 408– (2012) · Zbl 1253.90015 · doi:10.1016/j.ejor.2012.04.036
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.