A two-stage intelligent search algorithm for the two-dimensional strip packing problem
Research output: Journal Publications and Reviews › RGC 21 - Publication in refereed journal › peer-review
Author(s)
Related Research Unit(s)
Detail(s)
Original language | English |
---|---|
Pages (from-to) | 57-69 |
Journal / Publication | European Journal of Operational Research |
Volume | 215 |
Issue number | 1 |
Publication status | Published - 16 Nov 2011 |
Link(s)
Abstract
This paper presents a two-stage intelligent search algorithm for a two-dimensional strip packing problem without guillotine constraint. In the first stage, a heuristic algorithm is proposed, which is based on a simple scoring rule that selects one rectangle from all rectangles to be packed, for a given space. In the second stage, a local search and a simulated annealing algorithm are combined to improve solutions of the problem. In particular, a multi-start strategy is designed to enhance the search capability of the simulated annealing algorithm. Extensive computational experiments on a wide range of benchmark problems from zero-waste to non-zero-waste instances are implemented. Computational results obtained in less than 60 seconds of computation time show that the proposed algorithm outperforms the supposedly excellent algorithms reported recently, on average. It performs particularly better for large instances. © 2011 Elsevier B.V. All rights reserved.
Research Area(s)
- Heuristic search, Packing problem, Simulated annealing
Citation Format(s)
A two-stage intelligent search algorithm for the two-dimensional strip packing problem. / Leung, Stephen C.H.; Zhang, Defu; Sim, Kwang Mong.
In: European Journal of Operational Research, Vol. 215, No. 1, 16.11.2011, p. 57-69.
In: European Journal of Operational Research, Vol. 215, No. 1, 16.11.2011, p. 57-69.
Research output: Journal Publications and Reviews › RGC 21 - Publication in refereed journal › peer-review