Downloads: 476

Files in This Item:
File Description SizeFormat 
j.disopt.2009.04.002.pdf257.12 kBAdobe PDFView/Open
Title: An iterated local search algorithm based on nonlinear programming for the irregular strip packing problem
Authors: Imamichi, Takashi
Yagiura, Mutsunori
Nagamochi, Hiroshi  kyouindb  KAKEN_id
Author's alias: 今道, 貴司
Keywords: Irregular strip packing problem
Iterated local search
No-fit polygon
Unconstrained nonlinear programming
Issue Date: Nov-2009
Publisher: Elsevier
Journal title: Discrete Optimization
Volume: 6
Issue: 4
Start page: 345
End page: 361
Abstract: The irregular strip packing problem is a combinatorial optimization problem that requires to place a given set of two-dimensional polygons within a rectangular container so that no polygon overlaps with other polygons or protrudes from the container, where each polygon is not necessarily convex. The container has a fixed width, while its length can change so that all polygons are placed in it. The objective is to find a layout of the set of polygons that minimizes the length of the container. We propose an algorithm that separates overlapping polygons based on nonlinear programming, and an algorithm that swaps two polygons in a layout so as to find their new positions in the layout with the least overlap. We incorporate these algorithms as components into an iterated local search algorithm for the overlap minimization problem and then develop an algorithm for the irregular strip packing problem using the iterated local search algorithm. Computational comparisons on representative instances disclose that our algorithm is competitive with other existing algorithms. Moreover, our algorithm updates several best known results.
Rights: c 2009 Elsevier B.V. All rights reserved.
This is not the published version. Please cite only the published version. この論文は出版社版でありません。引用の際には出版社版をご確認ご利用ください。
URI: http://hdl.handle.net/2433/85223
DOI(Published Version): 10.1016/j.disopt.2009.04.002
Appears in Collections:Journal Articles

Show full item record

Export to RefWorks


Export Format: 


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.