基于異形板材自動排料方法研究

柯于河

（中國直升機(jī)設(shè)計研究所，江西景德鎮(zhèn) 333001）

0. 引言

在板材自動排料問題研究中，研究對象只要零件和板材。在最開始研究中，零件都是先擬合成規(guī)則圖形如三角形、矩形、圓形等，然后在進(jìn)行排料[2]，之后的研究就直接為二維不規(guī)則零件在矩形板材中自動排樣。本文在此基礎(chǔ)上，研究二維不規(guī)則零件在異形板材（非標(biāo)準(zhǔn)矩形板材）自動排樣問題。其問題簡單描述為：將一定數(shù)量的不規(guī)則多邊形零件，盡可能多排放在一個形狀不規(guī)則的板材內(nèi)，并要在排放過程中，多邊形零件不能出板材邊界間，多邊形零件之間不能重疊。

二維不規(guī)則零件在異形板材自動排樣問題數(shù)學(xué)表述：

式（1）中C為排放零件，P為異形板材，Ps為排放零件占用異形板材的相對面積。目標(biāo)函數(shù)Zmaх為異形板材相對利用率，其值越大，表示排放結(jié)果越好。

二維不規(guī)則零件在異形板材自動排樣問題中，如果單純從二維不規(guī)則零件角度來看，則只需要考慮2個問題：首先是每次“選擇哪個零件”來排放，即零件定序問題，其次是將選擇好后的“零件排放在哪里”，即零件定位為題[3]。目前定序問題主要通過智能算法如遺傳算法，蟻群算法，模擬退火算法等來解決[4]，這些智能算法都具有較好的全局搜索能力。本文則直接采用應(yīng)用最為廣泛和成熟的遺傳算法。零件定位問題是異形板材自動排料中最重要的問題，也是本文研究的重點，本文通過內(nèi)外臨界多邊形來確定每個零件可排放位置。

1. 基于臨界多邊形的零件定位方法

零件在板材排放約束只有2個：零件間不重疊，零件不能出板材邊界。這2個約束是很弱的，滿足這2個約束的零件可排放點可能為一片區(qū)域內(nèi)的點，對于計算機(jī)來說，零件可排放點只能為離散有限解集。臨界多邊形（nofit-polygon，NFP）是一種可以快速判斷多邊形是否重疊，是否緊靠的重要幾何計算工具，因此在二維不規(guī)則排樣問題中廣泛應(yīng)用。

臨界多邊形的定義如下[5]：給定2個多邊形，固定其中一個多邊形A，另一個多邊形B繞多邊形A運動一周回到初始位置，在運動過程中多邊形B和A至少有一點相接觸但不能相交。而且多邊形B在運動過程中自身不能有任何旋轉(zhuǎn)，選擇多邊形B其中一個頂點作為參考點，該參考點隨多邊形B運動一周所形成的軌跡，稱為為多邊形B相對于多邊形A的臨界多邊形（為便于表述，在本文中也被稱為外臨界多邊形），記為NFPAB。在異形板材自動排料問題中，臨界多邊形的最大的意義是當(dāng)多邊形B在臨界多邊形NFPAB邊上時，多邊形B和多邊形A緊靠，在臨界多邊形NFPAB內(nèi)部時，多邊形B和多邊形A重疊相交，在臨界多邊形NFPAB外部時，多邊形B和多邊形A相離。因此可以通過臨界多邊形很快判斷兩多邊形間的重疊情況，減少了大量圖形相交計算。

在矩形板材中，可通過排放零件的各個頂點橫縱坐標(biāo)是否大于矩形板材長寬來快遞判斷零件是否排出板材邊界。而在異型板材中，由于其輪廓相比于矩陣板材是不規(guī)則的，為此引用內(nèi)臨界多邊形（Inner-no-fit-polygon，INFP）的概念。內(nèi)臨界多邊形的定義：給定多邊形C和多邊形板材D，固定多邊形板材D，多邊形C繞多邊形板材D運動一周回到初始位置，在運動過程中多邊形C要和多邊形板材D至少有一點相接觸但不能相交，而且多邊形C在運動過程中自身不能有任何旋轉(zhuǎn)，選擇多邊形C其中一個頂點作為參考點，該參考點隨多邊形C運動一周所形成的軌跡，定義為多邊形C相對于多邊形板材D的內(nèi)臨界多邊形，記為INFPC，如圖1所示。內(nèi)臨界多邊形的最大的意義就是當(dāng)多邊形C在內(nèi)臨界多邊形邊上或者內(nèi)部時候，可以保證多邊形C不出板材邊界。

圖1 內(nèi)臨界多邊形示意圖

當(dāng)零件在臨界多邊形邊上或者頂點處，零件間則恰好緊靠不重疊，當(dāng)零件在內(nèi)臨界多邊形邊上或者內(nèi)部，則可保證零件不出板材，為簡化計算量，本文只將臨界多邊形頂點和其相交的點作為零件排放位置，臨界多邊形各條邊不考慮。下面通過示例來描述在如何通過內(nèi)外臨界多邊形來確定零件C可排放位置，其中零件為A，B，C，板材為D，3個零件排放順序為A-B-C，具體步驟如下：

Step1：排放零件A，初始零件排放位置一般默認(rèn)為左下角；

Step2：基于零件A和零件B臨界多邊形，以及零件B于板材D內(nèi)臨界多邊形來確定零件B排放位置，此處直接將零件B排放在與零件A和板材D都緊靠位置上，零件A和零件B排放位置如圖3（a）虛線所示；

Step3：求出零件C和零件A臨界多邊形NFPAC，如圖2（a）所示，零件C和零件B臨界多邊形NFPBC，如圖2（b）所示，零件C和板材D的內(nèi)臨界多邊形INFPC，零件C擬排放點為這3個臨界多邊形所有頂點以及這3個臨界多邊形相交的交點，如圖3（a）所示；

圖2 求解零件間臨界多邊形

Step4：最終零件C可排放點必須同時滿足：臨界多邊形NFPAC邊上或者外部；臨界多邊形NFPBC邊上或者外部；內(nèi)臨界多邊形INFPC邊上或者內(nèi)部。不滿足其中任何一條的點都應(yīng)該剔除，最終零件C可排放點，如圖3（b）所示；

圖3 零件可排放點

Step5：零件C放置在每一個可排放點時候，都可以保證它與零件A和零件B緊靠不重疊且在板材內(nèi)部，在這些可排放點中選取合適點排放零件C后，后續(xù)零件以此類推排放。

2. 基于異形板材有缺陷區(qū)域處理辦法

在現(xiàn)實中，異形板材內(nèi)部可能存在已被切割后的區(qū)域，這些已被切割后的有缺陷區(qū)域無法作為異形板材可排放區(qū)域。在實際中對于這類問題中，可以把這些缺陷區(qū)域看作一個已排放的“特殊零件”，只要保證后續(xù)零件排放不與這些缺陷區(qū)域重疊就行，因此只需要在零件定位算法上進(jìn)行修改，具體步驟如下：

Step1：求解所有零件之間臨界多邊形、所有零件與每個缺陷區(qū)域之間臨界多邊形、所有零件與板材之間內(nèi)臨界多邊形；

Step2：排放初始零件1；

Step3：求出零件2和零件外1臨界多邊形、求出零件2和每個缺陷外臨界多邊形，零件2和板材內(nèi)臨界多邊形，零件2擬排放點為這些臨界多邊形所有頂點以及相交的交點；

Step4：剔除掉在任意外臨界多邊形內(nèi)部的點或是在任意內(nèi)臨界多邊形外部的點，即板材外部點和缺陷區(qū)域內(nèi)部的點以及零件間會重疊的點，剩下點為零件2可排放點；

Step5：確定零件2排放點后，后續(xù)零件以此類推排放。

本文從歐洲排樣問題興趣小組ESICUP提供的Shirts的99個零件作為測試零件，然后再設(shè)計一個帶2缺陷區(qū)域的異形板材，最終測試結(jié)果如圖4所示，從排樣結(jié)果圖可以看出所有零件間沒有出現(xiàn)重疊情況，也沒有出現(xiàn)板材外部和缺陷區(qū)域內(nèi)部等情況，證明了算法可行性。

圖4 帶缺陷區(qū)域異形板材排樣

3.針對異形板材有狹窄區(qū)域處理辦法

在對隨機(jī)異形板材測試過程中，一些有狹窄區(qū)域的異形板材的板材利用會大大降低，如圖5所示，右側(cè)大面積可排區(qū)域沒有排。通過斷點代碼運行分析可知，造成這樣排樣結(jié)果是由于每個零件與板材之間的內(nèi)臨界多邊形計算錯誤導(dǎo)致的，從內(nèi)臨界多邊形廣義范疇來講，對于這種有狹窄區(qū)域特殊的異形板材來講，每個零件與它之間的內(nèi)臨界多邊形應(yīng)該有2個（左右各一個），零件在這2個內(nèi)臨界多邊形任何一個的邊上或者內(nèi)部都可保證零件在其異形板材內(nèi)部。但在實際計算中，由于初始點從左下角開始的，只計算出左邊一個內(nèi)臨界多邊形，故零件在排樣過程中都只在左邊區(qū)域排放。

圖5 有狹窄區(qū)域異形板材排樣

針對這種問題，目前無法通過對內(nèi)臨界多邊形求解算法改進(jìn)來完美解決。可以通過排放前的預(yù)處理，或是設(shè)定閾值來解決。比如當(dāng)已排零件面積與板材總面積比值小于閾值，或者已排零件區(qū)域最大長度、寬度與板材總長度、寬度比值小于閾值時候，可以在剩余板材區(qū)域內(nèi)尋找新的初始排放點繼續(xù)排放剩余零件，最后將多次排放結(jié)果合并。

4.結(jié)語

由于目前關(guān)于異形板材自動排樣研究方面較少，研究該類問題較為權(quán)威的歐洲排樣問題興趣小組ESICU也沒有相關(guān)評估標(biāo)準(zhǔn)和測試實例。因此本文也僅僅從異形板材的自動排樣可行性角度上進(jìn)行研究，從排樣結(jié)果看，整個排樣算法仍然有很大的優(yōu)化空間。