An efficient intelligent search algorithm for the two‐dimensional rectangular strip packing problem. (3rd December 2014)

• Record Type: Journal Article
• Authors: Wei, Lijun; Qin, Hu; Cheang, Brenda; Xu, Xianhao
• Is Part Of: International transactions in operational research. Volume 23:Number 1/2(2016:Jan./Mar.)
• Page Start: 65
• Page End: 92
• Publication Date: 2014-12-03
• Subjects: packing -- heuristic -- local search -- intelligent search algorithm; Operations research -- Periodicals; 003
• DOI: 10.1111/itor.12138
• Languages: English
• ISSNs: 0969-6016

Abstract

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