矩形件排樣算法探討

蘇厚仁　鐘相強

【摘 要】針對二維矩形件優化排樣問題，提出一種新型的算法——矩形動態匹配算法。通過對零件的矩形化預處理，并自動正交排布使零件緊密靠接和定位，從而實現復雜不規則船體零件的矩形化排樣，該算法亦可擴展用于三維空間零件的排樣求解，實例證明其有效性。

【關鍵詞】排樣；矩形零件；優化；算法

【Abstract】For optimal nesting of rectangular parts of a two dimensional problem， a new kind of algorithm is put forward. The rectangular pretreatment and automatically orthogonal configuration make the location of parts more close， the rectangular optimization nesting of complex irregular ship parts is realized， the algorithm can be extended to 3d space parts. Examples show its effectiveness.

【Key words】Parking； Rectangular parts； Optimization； Algorithm

0 引言

排樣優化技術是工業產品設計、制造中如何節約原材料、優化利用資源的重要手段。現實零件形狀復雜，多為不規則零件，且制造特征和方法各異，如何采用有效的算法實現最優布局、提高原材料的利用率尤為重要[1-3]。文中基于對排樣零件矩形化預處理提出了矩形動態匹配算法來實現零件的定位，具有較高的材料利用率。

1 算法簡介

1.1 實現算法的前提條件

將一個矩形零件排放在矩形板材中，需要解決的問題有：

（1）多個矩形零件排放時的排放次序。

（2）矩形零件的排放位置問題。

1.2 入排矩形零件必要約束條件

（1）規定矩形零件僅有橫放、豎放兩個狀態。如圖1所示，A為豎放狀態S，C為橫放狀態H，B為非法放置。采用左下角和右上角兩端點坐標（Xli，Yli）（Xhi，Yhi）描述一個矩形。通過比較Xhi- Xli與Yhi- Yli的大小來確定矩形零件的狀態。

（2）排樣時，各個矩形零件之間不得相互重疊。為了滿足任意兩個矩形零件不重疊放置，須滿足如下數學關系：假設兩個矩形分別為A（xli，yli）（xhi，yhi）；B（xlj，ylj）（xhj，yhj），Max[xli-xhj，xlj-xhi，yli-yhj，ylj-yhi]>=0 i，j=1，2，3…N，i不等于j；

（3）排樣時，各個矩形零件不得超出板材區域。

1.3 算法實現過程

在板材上的定位（排列）具體算法步驟[4-5]：

（1）輸入給定板材件寬度B，確定原點（0，0）；

（2）輸入各矩形零件Xi（ai，bi） i=1，2，3；

（3）計算面積Si=ai*bi；

（4）由大到小排列[Si] （即新數列S1>S2>S3……）；

（5）讀入第一個矩形（最大的矩形）A1（xl1，yl1）（xh1，yh1），當xh1

（6）讀入下一個矩形，檢測板材是否有矩形狀空穴，交叉比較矩形零件與空穴的長寬大小，若滿足空穴條件，矩形零件排入空穴（優先橫放狀態），若不滿足空穴條件，零件靠接這一層第一個矩形零件頂部排入靠近板材左端；

（7）讀入下一個矩形重復上一步驟直到所有矩形零件排完。

2 零件的矩形化處理

零件組合矩形包絡過程根據算法的復雜程度可以通過自動排樣完成，也可以通過人工交互完成，通常采用方法有[6-9]：

3 應用實例

選擇板材寬度1000 mm，長度不限，輸入待排零件39個。基于上述排樣算法，文中實現了39個零件排樣定位并輸出排樣圖。圖4為39個零件的排樣圖，板材的利用率為89.18%。

4 結論

定位算法是求解最佳排樣布局的核心技術，對于不規則零件更是難點。文中采用較為簡單的定位算法，同時對待排零件進行矩形化預處理，大大降低了排樣計算的復雜度，能解決一般矩形件的排樣問題，具有較高的原材料利用率。

【參考文獻】

[1]賈志欣，殷國富，羅陽.二維不規則零件排樣問題的遺傳算法求解[J].計算機輔助設計與圖形學學報，2002，14（5）：467-470.

[2]毛定山，崔先國，李行，等.簡單多邊形集凸包的快速算法[J].工程圖學學報，2007（6）：96-101.

[3]陳端兵，黃文奇.求解矩形packing問題的貪心算法[J].計算機工程，2007，33（4）：160-162.

[4]曾敏，王乘，劉瓊梅.大規模定制板材排樣的多種群蟻群優化算法[J].制造業自動化，2011，33（5）：59-62.

[5]曾鳳華.剩余矩形匹配算法在矩形件排樣中的應用[J].機電工程技術，2006，35（3）：64-65.

[6]李滿江，孟祥旭.矩形件和任意多邊形排樣問題的算法及應用[J].貴州工業大學學報：自然科學版，2002，31（4）：126-130.

[7]岳為，余仁龍，崔永慶，等.鍋爐下料中的非矩形件的排樣優化算法[J].節能技術，1997（2）：44-45.

[8]羅為.二維不規則形狀計算機自動排樣系統的研究與設計[J].計算機工程，1995，21（6）：3-9.

[9]劉虓.基于HAPE的二維不規則零件排樣算法及其性能研究[D].廣州：華南理工大學，2011.

[責任編輯：楊玉潔]