Extended local search algorithm based on nonlinear programming for two-dimensional irregular strip packing problem

This paper presents an extended local search algorithm (ELS) for the irregular strip packing problem. It adopts two neighborhoods, swapping two given polygons in a placement and placing one polygon into a new position. The local search algorithm is used to minimize the overlap on the basis of the ne...

Full description

Saved in:
Bibliographic Details
Published in:Computers & operations research 2012-03, Vol.39 (3), p.678-686
Main Authors: Leung, Stephen C.H., Lin, Yangbin, Zhang, Defu
Format: Article
Language:English
Subjects:
Algorithms
Applied sciences
Exact sciences and technology
Flows in networks. Combinatorial problems
Irregular strip packing problem
Local search
Mathematical problems
Nesting
Nonlinear programming
Operational research and scientific management
Operational research. Management science
Operations research
Packing problem
Placing
Polygons
Search algorithms
Strip
Studies
Tabu search
Unconstrained nonlinear programming
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:This paper presents an extended local search algorithm (ELS) for the irregular strip packing problem. It adopts two neighborhoods, swapping two given polygons in a placement and placing one polygon into a new position. The local search algorithm is used to minimize the overlap on the basis of the neighborhoods mentioned above and the unconstrained nonlinear programming model is adopted to further minimize the overlap during the search process. Moreover, the tabu search algorithm is used to avoid local minima, and a compact algorithm is presented to improve the result. The results of standard test instances indicate that when compared with other existing algorithms, the presented algorithm does not only show some signs of competitive power but also updates several best known results.
ISSN:0305-0548
1873-765X
0305-0548
DOI:10.1016/j.cor.2011.05.025