An efficient intelligent search algorithm for the two‐dimensional rectangular strip packing problem

• DOI: http://doi.org/10.1111/itor.12138
• Date: 01 January 2016
• Author: Brenda Cheang,Lijun Wei,Hu Qin,Xianhao Xu
• Published date: 01 January 2016

Intl. Trans. in Op. Res. 23 (2016) 65–92

DOI: 10.1111/itor.12138

INTERNATIONAL

TRANSACTIONS

IN OPERATIONAL

RESEARCH

An efficient intelligent search algorithm for the

two-dimensional rectangular strip packing problem

Lijun Weia,HuQin

b∗, Brenda Cheangcand Xianhao Xub

aSchool of Information Technology, Jiangxi University of Finance and Economics, Nanchang,Jiangxi 330013, China

bSchool of Management, Huazhong University of Science and Technology, No.1037, Luoyu Road, Wuhan, China

cSchool of Management and Engineering, Nanjing University, Nanjing 210093, China

E-mail: villagerwei@gmail.com [Wei];tigerqin1980@gmail.com [Qin]; brendacheang@yahoo.com [Cheang];

xxhao@mail.hust.edu.cn [Xu]

Received 9 June2013; received in revised form 20 October 2014; accepted 20 October 2014

Abstract

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 providesa 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.

Keywords:packing; heuristic; local search; intelligent search algorithm

1. Introduction

Packing problems are complex combinatorial optimization problems that arise in many industries

related to materials such as metal, textiles, glass, paper, leather, etc. The objective of packing

problems is to allocate multiple items in a large containment region such that wasted space is

minimized or occupied space is maximized. The allocation is subject to a number of constraints

such as no two items overlapin space and all items must be placed orthogonally. This paper addresses

a two-dimensional (2D) strip packing problem(2DSP) where a set of nrectangular pieces (each piece

has height hiand width wi,i=1,...,n) must be packed into a largerrectangular sheet of fixed width

Wand infinite height. The objective is to minimize the occupied height of the sheet subject to some

∗Corresponding author. Tel.: +86 13349921096.

C

2014 The Authors.

International Transactionsin Operational Research C

2014 International Federation of OperationalResearch Societies

Published by John Wiley & Sons Ltd, 9600 Garsington Road, Oxford OX4 2DQ, UK and 350 Main St, Malden, MA02148,

USA.

66 L. Wei et al. / Intl. Trans. in Op. Res. 23 (2016) 65–92

given constraints that depend on needs of different applications. In some applications, the pieces

cannot be rotated, that is, the fixed orientation constraint is required. In other applications, the

guillotine cut constraints (edge-to-edge cuts parallel to the edges of the sheet) have to be complied

with. This paper considers only the fixed orientation constraint, so the problem can be referred to

as the OF subtype according to the typology proposed by Lodi et al. (1999), Bortfeldt (2006), and

W¨

ascher et al. (2007). Generally, RF subtype can be well solved if OF subtype problem is solved

well. For other variants of packing problems, we refer the reader to the papers by Wei et al. (2012,

2013), Che et al. (2011), Zhu and Lim (2012), Bortfeldt and W¨

ascher (2013), Paquay et al. (2014),

and Pedroso et al. (2014).

In this paper,we propose an efficient improved algorithm (IA) that is based on the ISA approach

presented by Leung et al. (2011). This algorithm consists of three stages: greedy selection, local

improvement, and randomized improvement. An efficient heuristic based on an improved scoring

rule is integrated in the three stages. In the first stage, greedy selection provides a good solution for

local improvement. In the second stage, a local search is used to improve the solution. In the third

stage, a simple random local search is implemented to further improve the solutions.

Recently, Yang et al. (2013) also proposed an improved ISA, which they referred to as the simple

random algorithm (SRA). Nevertheless, there are three key differences between the SRA and our

approach: first, there is a greedy selection stage in our approach, whereas the SRA does not have

such stage; second, our improved constructive heuristic is different from thatof the SRA in that the

detailed scoring rule used to select the best-fit (BF) rectangle is different, although both approaches

divide the scoring rule into eight cases; and third, the random local search of our approach is

different from that of the SRA in that our random local search only accepts nonworse solutions,

whereas the SRA accepts worse solutions with some probability.

The merit of our proposed algorithm is that it produces high-quality solutions for most of the

benchmark instances; yet it is elegant in that it does not require anyparameter settings. Thereupon,

this paper contributes to packing research in three ways: (a) the design of the greedy selection, (b)

the improvement of the constructive heuristic proposed by Leung et al. (2011), (c) the extensive

computational experiments that show the efficacy of our algorithm over all previously reported

algorithms (to the best of our knowledge) for most of the benchmark instances.

2. Literat ure review

Although extensive literature can be found in Dyckhoff (1990), Dowsland (1992), Lodi et al. (2002),

and W¨

ascher et al. (2007), we provide a review of the relevant literature concerning the 2DRSPP

here. Indeed, the 2DRSPP is a classical NP-hard problem (Garey and Johnson, 1979), where exact

algorithms are suitable only for small-scale problem instances (Kenmochi et al., 2009; Alvarez-

Valdes et al., 2009). Thus, what ensued was the introduction and application of heuristics and

metaheuristics as optimization techniques to obtain practical and desirable solutions.

In one of the earliest studies on packing problems, Baker et al. (1980) proposed the simple

bottom-left (BL) heuristic, which positions each rectangle sequentially by first pushing it as much

downwards as possible, followed by as much leftwards as possible. Following that, Chazelle (1983)

devised the BL-fill (BLF) heuristic, thereby generalizing the BL concept by placing each rectangle

in its BL-most position. Much later, Burke et al. (2004) presented a BF algorithm where the sheet is

C

2014 The Authors.

International Transactionsin Operational Research C

2014 International Federation of OperationalResearch Societies