矩形件排樣算法探討

蘇厚仁　鐘相強(qiáng)

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

【關(guān)鍵詞】排樣；矩形零件；優(yōu)化；算法

【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 引言

排樣優(yōu)化技術(shù)是工業(yè)產(chǎn)品設(shè)計(jì)、制造中如何節(jié)約原材料、優(yōu)化利用資源的重要手段?，F(xiàn)實(shí)零件形狀復(fù)雜，多為不規(guī)則零件，且制造特征和方法各異，如何采用有效的算法實(shí)現(xiàn)最優(yōu)布局、提高原材料的利用率尤為重要[1-3]。文中基于對排樣零件矩形化預(yù)處理提出了矩形動(dòng)態(tài)匹配算法來實(shí)現(xiàn)零件的定位，具有較高的材料利用率。

1 算法簡介

1.1 實(shí)現(xiàn)算法的前提條件

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

（1）多個(gè)矩形零件排放時(shí)的排放次序。

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

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

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

（2）排樣時(shí)，各個(gè)矩形零件之間不得相互重疊。為了滿足任意兩個(gè)矩形零件不重疊放置，須滿足如下數(shù)學(xué)關(guān)系：假設(shè)兩個(gè)矩形分別為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）排樣時(shí)，各個(gè)矩形零件不得超出板材區(qū)域。

1.3 算法實(shí)現(xiàn)過程

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

（1）輸入給定板材件寬度B，確定原點(diǎn)（0，0）；

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

（3）計(jì)算面積Si=ai*bi；

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

（5）讀入第一個(gè)矩形（最大的矩形）A1（xl1，yl1）（xh1，yh1），當(dāng)xh1

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

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

2 零件的矩形化處理

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

3 應(yīng)用實(shí)例

選擇板材寬度1000 mm，長度不限，輸入待排零件39個(gè)?；谏鲜雠艠铀惴?，文中實(shí)現(xiàn)了39個(gè)零件排樣定位并輸出排樣圖。圖4為39個(gè)零件的排樣圖，板材的利用率為89.18%。

4 結(jié)論

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

【參考文獻(xiàn)】

[1]賈志欣，殷國富，羅陽.二維不規(guī)則零件排樣問題的遺傳算法求解[J].計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào)，2002，14（5）：467-470.

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

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

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

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

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

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

[8]羅為.二維不規(guī)則形狀計(jì)算機(jī)自動(dòng)排樣系統(tǒng)的研究與設(shè)計(jì)[J].計(jì)算機(jī)工程，1995，21（6）：3-9.

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

[責(zé)任編輯：楊玉潔]