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

柯于河

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

0. 引言

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

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

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

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

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

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

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

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

圖1 內臨界多邊形示意圖

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

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

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

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

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

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

圖3 零件可排放點

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

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

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

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

Step2：排放初始零件1；

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

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

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

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

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

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

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

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

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

4.結語

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