An Optimization Algorithm based on No-fit Polygon Method and Hybrid Heuristic Strategy for Irregular Nesting Problem

详细信息    查看官网全文

• 英文论文题名：An Optimization Algorithm based on No-fit Polygon Method and Hybrid Heuristic Strategy for Irregular Nesting Problem
• 论文作者：Jiang-jiang Xu ; Xin-sheng Wu ; Hai-ming Liu ; Mei Zhang
• 英文论文作者：Jiang-jiang Xu ; Xin-sheng Wu ; Hai-ming Liu ; Mei Zhang ; School of Automation Science and Engineering ; South China University of Technology
• 年：2017
• 作者机构：School of Automation Science and Engineering,South China University of Technology;
• 英文论文关键词：Irregular nesting ; No-fit polygon ; Hybrid heuristic strategy ; Optimization algorithm
• 会议召开时间：2017-07-26
• 会议录名称：第36届中国控制会议论文集（B）
• 英文会议录名称：Proceedings of the 36th Chinese Control Conference（B）
• 语种：英文
• 分类号：TP301.6
• 学会代码：KZLL
• 会议名称：第36届中国控制会议
• 会议地点：中国辽宁大连
• 主办单位：中国自动化学会控制理论专业委员会
• 学会名称：中国自动化学会控制理论专业委员会
• 页数：6
• 文件大小：355k
• 原文格式：D
• 会议级别：全国

摘要

For the irregular nesting problem widely existing in modern manufacturing industry, this paper makes a research on it and presents an optimization algorithm based on no-fit polygon(NFP) method and hybrid heuristic strategy to solve it. The proposed algorithm first uses the composition method of trace line segment to calculate no-fit polygons(NFPs) between every two pieces in piece set, and extracts the candidate placement points for a candidate piece to be placed by using generated NFPs in combination with internal no-fit polygon(INFP) between the piece and the material plate. Then, the algorithm designs and applies three hybrid heuristic strategies to evaluate all candidate pieces and choose the best piece to place next and determine the best placement point for the selected piece. Experimental test has been performed to verify feasibility and effectiveness of the proposed algorithm. The test results show that the algorithm can solve the irregular nesting problem effectively, and improve the utilization of material to a certain extent.
For the irregular nesting problem widely existing in modern manufacturing industry, this paper makes a research on it and presents an optimization algorithm based on no-fit polygon(NFP) method and hybrid heuristic strategy to solve it. The proposed algorithm first uses the composition method of trace line segment to calculate no-fit polygons(NFPs) between every two pieces in piece set, and extracts the candidate placement points for a candidate piece to be placed by using generated NFPs in combination with internal no-fit polygon(INFP) between the piece and the material plate. Then, the algorithm designs and applies three hybrid heuristic strategies to evaluate all candidate pieces and choose the best piece to place next and determine the best placement point for the selected piece. Experimental test has been performed to verify feasibility and effectiveness of the proposed algorithm. The test results show that the algorithm can solve the irregular nesting problem effectively, and improve the utilization of material to a certain extent.

引文

[1]X.L.Jin,The research of the two-dimensional irregular shape problem.Shandong University of Science and Technology,2003.
    [2]L.Hong,Y.Wand,A rapid decoding algorithm of irregular parts packing,Journal of Computer-aided Design&Computer Graphics,17(11):2465-2470,2005.
    [3]E.K.Burke,R.S.R.Hellier,G.Kendall,et al,Complete and robust no-fit polygon generation for the irregular stock cutting problem,European Journal of Operational Research,179(1):27-49,2007.
    [4]Oliveira J F,Gomes A M,Ferreira J S,TOPOS–A new constructive algorithm for nesting problems,OR Spectrum,22(2):263-284,2000.
    [5]Egeblad,Jens,Pisinger,et al,Heuristic approaches for the two-and three-dimensional knapsack packing problem,Computers&Operations Research,36(4):1026-1049,2009.
    [6]J.Egeblada,B.K.Nielsen,A.Odgaarda,Fast neighborhood search for two-and three-dimensional nesting problems,European Journal of Operational Research,183(3):1249-1266,2007.
    [7]A.M.Gomes,J.F.Oliveira,Solving irregular strip packing problems by hybridising simulated annealing and linear programming,European Journal of Operational Research,171(3):811-829,2006.
    [8]R.C.J.Art,An approach to the two dimensional irregular cutting stock problem.Massachusetts Institute of Technology,1966.
    [9]A.Mahadevan,Optimization in computer aided pattern packing.North Carolina State University,1984.
    [10]V.Milenkovic,K.Daniels,Z.Li,Placement and compaction of nonconvex polygons for clothing manufacture,in Proceedings of the 4th Canadian Conference on Computational Geometry,2000:236-243.
    [11]P.K.GHOSH,An algebra of polygons through the notion of negative shapes,Vision Graphics Image Process.Image Understanding,54(1):119-144,1991.
    [12]H.Y.Liu,Y.J.He,J.A.Bennell,The irregular nesting problem:a new approach for no-fit polygon calculation,Journal of the Operational Research Society,58(9):1235-1245,2007.