基于粗糙集的矩形件優(yōu)化填充排樣方法研究

苗志民，盛步云，蕭 箏，羅 軍

（武漢理工大學(xué)機(jī)電工程學(xué)院&湖北省數(shù)字制造重點(diǎn)實(shí)驗(yàn)室，湖北 武漢 430070）

1 引言

矩形件優(yōu)化填充排樣是在備選的大量工件中選取合適規(guī)格的一系列工件，根據(jù)實(shí)際的工況條件，以最優(yōu)的方式將其填滿空白區(qū)域，獲得最能滿足設(shè)計(jì)意圖的排樣結(jié)果。在實(shí)際工作中，設(shè)計(jì)者基本采用手工試算或憑經(jīng)驗(yàn)的方式進(jìn)行排樣，又需要綜合考慮工件成本、加工與施工難易程度、企業(yè)偏好程度等諸多因素，造成排樣困難、效率低下。目前，國(guó)內(nèi)外學(xué)者在這方面進(jìn)行了廣泛的研究工作。文獻(xiàn)[1]為解決矩形排樣問題，采用不同啟發(fā)式排樣算法進(jìn)行多目標(biāo)優(yōu)化，以求解最優(yōu)布局；文獻(xiàn)[2]針對(duì)矩形填充排樣面積最小化問題，通過約束包絡(luò)矩形的長(zhǎng)寬比和制定內(nèi)部填充策略，以提高最終布局的填充率；文獻(xiàn)[3]通過動(dòng)態(tài)約簡(jiǎn)填充排樣問題的包絡(luò)維數(shù)，將備選件對(duì)結(jié)果的負(fù)面影響定義為損傷程度，采用一種最小損傷優(yōu)先法以求解最優(yōu)布局問題；文獻(xiàn)[4]研究基于屬性重要度的優(yōu)化填充排樣算法，在考慮工件價(jià)格、顏色、花式的因素下，以材料利用率最高為目標(biāo)進(jìn)行優(yōu)化排樣；文獻(xiàn)[5]建立了二維正交矩形布局問題的數(shù)學(xué)模型，利用圖形矩陣化理論搜尋空白平面，通過動(dòng)態(tài)填充啟發(fā)式算法求解最優(yōu)布局方式。上述研究中提出了一系列解決矩形排樣問題的最優(yōu)化方法，提高了排樣效率與排樣質(zhì)量，但對(duì)工件價(jià)值的計(jì)算比較簡(jiǎn)單，大部分僅考慮了工件面積與材料利用率，而在填充排樣中需要填滿空白區(qū)域，排樣的工件總面積是一定的。因此，在排樣的過程中，矩形件價(jià)值的計(jì)算需要綜合考慮工件成本、加工時(shí)間、施工效率和設(shè)計(jì)偏好度等諸多因素，以更好地滿足設(shè)計(jì)人員的設(shè)計(jì)意圖。針對(duì)矩形件優(yōu)化填充排樣問題，綜合考慮價(jià)值評(píng)定因素，提出一種基于粗糙集理論的矩形件綜合價(jià)值計(jì)算方法，建立優(yōu)化填充排樣模型，采用動(dòng)態(tài)規(guī)劃原理求解最優(yōu)排樣方式，并成功應(yīng)用于系統(tǒng)開發(fā)，很好地解決了企業(yè)產(chǎn)品設(shè)計(jì)中的優(yōu)化填充排樣問題。

2 基本問題

2.1 排樣問題描述

已知一待排樣空白區(qū)域，工件系列共有r種，第i種工件的尺寸為li×wi（1≤i≤r），綜合考慮價(jià)值評(píng)定因素情況下，計(jì)算綜合價(jià)值為vi，對(duì)各類工件被選中的次數(shù)不做限制，排樣的目標(biāo)是在此區(qū)域排滿的情況下，使得該區(qū)域所含工件總價(jià)值最大，并確定布置方式。

為滿足實(shí)際的工況要求，工件的優(yōu)化填充排樣必須符合以下約束規(guī)則：

（1）相鄰性，即同樣型號(hào)規(guī)格的工件盡可能排布在一起，以縮短排樣的工期；

（2）互不干涉性，即工件排布時(shí)需兩兩緊靠，且互不干涉，要求排滿空白區(qū)域且不可超出；

（3）優(yōu)先性，即后填入的工件不影響已填入?yún)^(qū)域工件的排布位置；

（4）統(tǒng)一性，即同一排樣區(qū)域內(nèi)工件排列方式保持同步，統(tǒng)一橫排或統(tǒng)一縱排。

2.2 價(jià)值評(píng)定因素

排樣工件尺寸的選擇是由工件綜合價(jià)值決定的。工件綜合價(jià)值評(píng)定需要考慮的因素較多，這里選擇工件成本、加工時(shí)間、施工效率和設(shè)計(jì)偏好度作為評(píng)價(jià)因素。

（1）工件成本：主要指材料成本，受工件的尺寸規(guī)格的影響較大；

（2）加工時(shí)間：主要考察加工的難易程度，以及對(duì)產(chǎn)品生產(chǎn)周期的影響；

（3）施工效率：工件生產(chǎn)完成后現(xiàn)場(chǎng)施工，施工安裝的難易程度也作為評(píng)價(jià)的因素；

（4）設(shè)計(jì)偏好度：對(duì)于不同規(guī)格的工件其偏好程度不同，優(yōu)先選用易于加工和施工的工件尺寸，節(jié)省成本。

2.3 排樣相關(guān)概念

（1）段的分割。一個(gè)待排樣的多邊形空白區(qū)域稱為段。已知待排的多邊形的內(nèi)角均為π/2或3π/2，稱為排樣多邊形。排樣過程中，需遍歷排樣多邊形中內(nèi)角為3π/2所對(duì)應(yīng)的直角點(diǎn)，依次使用同方向的分割線將其劃分為多個(gè)X向或Y向矩形子段區(qū)域，由于受到單個(gè)工件最大尺寸的限制，還需將子段區(qū)域進(jìn)一步分割，段的水平分割和豎直分割示意圖，如圖1所示。

圖1 段的分割圖Fig.1 Segments Split Graph

（2）條帶。一個(gè)或多個(gè)工件排列成一行（或列），稱為條帶。條帶分為普通條帶和同質(zhì)條帶，為了方便排樣，采用同質(zhì)條帶，分為X向和Y向兩種，如圖2所示。

圖2 條帶圖Fig.2 Bands Graph

（3）最優(yōu)子段排樣。對(duì)于排樣多邊形，將其分割成若干個(gè)X向或Y向子段，依次求解各子段的最優(yōu)解以獲得該區(qū)域的最大價(jià)值，排樣方式，如圖3所示。

圖3 排樣方式圖Fig.3 Nesting Mode Graph

3 基于粗糙集的矩形件優(yōu)化填充排樣模型

在排樣過程中，備用可選的工件種類繁多，數(shù)量巨大，同時(shí)需要考慮諸多因素的影響，給決策帶來困難。因此，實(shí)現(xiàn)優(yōu)化排樣的首要前提是工件綜合價(jià)值vi的確定。粗糙集理論是用來處理不完整性和不確定性問題的有效數(shù)學(xué)手段[6]。通過粗糙集理論確定矩形件綜合價(jià)值vi，為后續(xù)求解最優(yōu)排樣模型提供決策依據(jù)。

3.1 基于粗糙集的綜合價(jià)值計(jì)算

設(shè)在排樣過程中需考慮的決策因素為 E=（E1，E2，…，Em），決策屬性為 F=（F1，F(xiàn)2，…，F(xiàn)n），有如下定義：

定義1DS=是一個(gè)四元組的決策信息系統(tǒng)。其中，

U≠?為論域；

A≠?為屬性集合，E為條件屬性，F(xiàn)為決策屬性，則有A=E∪F，E∩F=?；

f：U×R→V為信息函數(shù)，R為U的一組等價(jià)關(guān)系，f映射U中每一對(duì)象的屬性值。

（1）求F對(duì)E（k1≤k≤m）的依賴度 δE（kF）。δE（kF）表示DS根據(jù)的信息能夠劃分到等價(jià)類U/IND（E）的對(duì)象數(shù)占系統(tǒng)總對(duì)象數(shù)的比值，即：

式中：|*|—集合的基數(shù)。

（2）求條件屬性Ek的重要度φEk與權(quán)重ωk。φEk表示從E去除Ek，計(jì)算其決策結(jié)果浮動(dòng)的程度，浮動(dòng)程度越大表示該屬性所占權(quán)重越大。

（3）求矩形件的綜合價(jià)值vi。vi指所有影響決策結(jié)果變化的Ek權(quán)重加權(quán)和。

3.2 矩形件優(yōu)化填充排樣模型

根據(jù)以上問題描述與工件綜合價(jià)值的計(jì)算方法，建立矩形件優(yōu)化填充排樣模型。設(shè)排樣多邊形的最大價(jià)值為V，對(duì)于水平分割方式，分割成s個(gè)X向矩形子段，其總價(jià)值為VX，第k個(gè)子段尺寸為 xk×yk，ai為該子段中 xki×yk條帶的個(gè)數(shù)。

則xki×y條帶的價(jià)值：

第k個(gè)X向子段的價(jià)值：

X向段的總價(jià)值：

對(duì)于豎直分割方式，分割成t個(gè)Y向矩形子段，其總價(jià)值為VY，第 k 個(gè)子段尺寸為 xk×yk，bi為該子段中 xk×yki條帶的個(gè)數(shù)。

則 xk×yki條帶的價(jià)值：

第k個(gè)Y向子段的價(jià)值：

Y向段的總價(jià)值：

可見，該數(shù)學(xué)模型是背包問題[7-9]。下面將用動(dòng)態(tài)規(guī)劃原理求解，計(jì)算和最優(yōu)布置方式。

3.3 基于最優(yōu)子段排樣的動(dòng)態(tài)規(guī)劃算法

動(dòng)態(tài)規(guī)劃算法的思路是將待求解的問題劃分為多個(gè)相互聯(lián)系的子問題，先求子問題的解，再通過子問題解來獲得原問題解[10]。

設(shè)xmin、ymin為條帶最小長(zhǎng)度和寬度，Δx、Δy為長(zhǎng)度和寬度方向的增量，生成X向最優(yōu)子段xk×yk最大價(jià)值的動(dòng)態(tài)遞歸式為：

則基于最優(yōu)子段的X向段最大價(jià)值動(dòng)態(tài)規(guī)劃算法，如圖4所示。同理可求得Y向段全部可能尺寸的最大價(jià)值。

求解矩形件優(yōu)化填充排樣模型算法流程如下所示：

（1）輸入排樣多邊形尺寸與工件數(shù)據(jù)；

（2）根據(jù)式（1）～式（3）將條件屬性進(jìn)行定量描述，依次計(jì)算決策屬性表中的各矩形件的綜合價(jià)值vi；

（3）根據(jù)式（4）、式（7）確定 X 向條帶、Y 向條帶的價(jià)值 v（xki，yk）、v（xk，yki）；

（4）運(yùn)用動(dòng)態(tài)規(guī)劃算法分別求解式（10），計(jì)算排樣多邊形分別采用水平和豎直分割生成的最優(yōu)子段排樣總價(jià)值VX、VY；

（5）根據(jù) VX、VY，計(jì)算排樣模型最大價(jià)值 V=max（VX，VY），確定最優(yōu)布置方式。

圖4 基于最優(yōu)子段的動(dòng)態(tài)規(guī)劃算法Fig.4 Dynamic Programming Algorithm Based on Optimal Sub Segments

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

為驗(yàn)證上述方法的有效性，以國(guó)內(nèi)某一建筑科技公司鋁模板排模設(shè)計(jì)為例，基于C#語言開發(fā)鋁模板智能排模設(shè)計(jì)系統(tǒng)，系統(tǒng)在SolidWorks平臺(tái)上進(jìn)行二次開發(fā)，所有排摸結(jié)果以3D模型格式輸出。建筑樓面的形狀大多為排樣多邊形，其配模模板有平面模板、支撐模板和角模板三部分。平面模板布置在矩形子段區(qū)域，支撐模板布置在段的分割線處，角模板布置在樓面邊角位置，便于模板拆裝與固定。在鋁模板樓面排模設(shè)計(jì)過程中，由于支撐模板與角模板的尺寸、位置相對(duì)固定，故僅考慮平面模板的優(yōu)化填充排樣問題。已知，備選平面鋁模板系列共有123種，由于研究鋁模板在樓板平面內(nèi)的排樣問題，故僅需考慮其長(zhǎng)寬尺寸，鋁模板的標(biāo)準(zhǔn)尺寸規(guī)格，如表1所示。

表2 決策屬性表Tab.2 Decision Attribute Table

決策屬性定性描述分為設(shè)計(jì)結(jié)果非常好（F1）、好（F2）、一般（F3）、不好（F4）四個(gè)值，記為F=（F1，F(xiàn)2，F(xiàn)3，F(xiàn)4），且F1=3，F(xiàn)2=2，F(xiàn)3=1，F(xiàn)4=0；決策因素有工件成本、加工時(shí)間、施工效率和設(shè)計(jì)偏好度，故條件屬性分別記為E1、E2、E3、E4，其對(duì)應(yīng)的定量描述分別為非常重要（3）、重要（2）、一般（1）、不重要（0），由企業(yè)鋁模板設(shè)計(jì)規(guī)則與評(píng)價(jià)指標(biāo)，依次得出E1～E4和F的決策屬性值，如表2所示。根據(jù)決策屬性表和式（1）～式（3）計(jì)算各模板的綜合價(jià)值，其計(jì)算過程如下：

表1 鋁模板尺寸規(guī)格Tab.1 Aluminum Formwork Size

同理可求得ω2=0.223，ω3=0.184，ω4=0.362。

由式（4）得：

同理可求其余模板綜合價(jià)值，其常見規(guī)格模板的綜合價(jià)值，如表3所示。隨機(jī)選取3個(gè)待排樣的樓面區(qū)域，根據(jù)基于粗糙集理論的矩形件優(yōu)化填充排樣模型，利用基于最優(yōu)子段排樣的動(dòng)態(tài)規(guī)劃算法求解結(jié)果，如表4所示。X向段與Y向段排樣結(jié)果，如圖5所示。結(jié)果表明，1號(hào)區(qū)域和3號(hào)區(qū)域Y向段排樣模板種類少，標(biāo)準(zhǔn)模板較多，易于統(tǒng)計(jì)和施工，且VXVY，故選用X向段排樣方式。

表3 常見規(guī)格鋁模板綜合價(jià)值表Tab.3 Comprehensive Value of Common Aluminum Formwork

表4 排樣結(jié)果表Tab.4 Nesting Result

圖5 X向段與Y向段排樣結(jié)果示意圖Fig.5 Nesting Result of X and Y Segements

5 結(jié)束語

將工件成本、加工時(shí)間、施工效率和設(shè)計(jì)偏好度作為矩形件綜合價(jià)值的評(píng)定因素，提出一種基于粗糙集理論的矩形件綜合價(jià)值計(jì)算方法，建立矩形件優(yōu)化填充數(shù)學(xué)模型，將排樣多邊形劃分為多個(gè)矩形子段，采用基于最優(yōu)子段的動(dòng)態(tài)規(guī)劃算法計(jì)算出排樣最大價(jià)值，確定最優(yōu)布置方案，切實(shí)提高了企業(yè)產(chǎn)品設(shè)計(jì)中大規(guī)模排樣的效率與質(zhì)量。對(duì)于異形區(qū)域與異形工件的排樣問題將是下一步主要研究的工作。