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

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

0.00 Avg rating0 Votes
Article ID: iaor20117151
Volume: 39
Issue: 3
Start Page Number: 678
End Page Number: 686
Publication Date: Mar 2012
Journal: Computers and Operations Research
Authors: , ,
Keywords: heuristics: local search, graphs, programming: nonlinear
Abstract:

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.

Reviews

Required fields are marked *. Your email address will not be published.