[發明專利]一種基于組化技術的矩形件排樣方法

有效

• 申請號: 201410196607.1
• 申請日: 2014-05-09
• 公開（公告）號: CN104008145B
• 公開（公告）日: 2017-03-29
• 發明（設計）人: 劉強
• 申請（專利權）人: 劉強
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 廣州嘉權專利商標事務所有限公司44205
• 代理人: 譚英強

技術領域

本發明涉及二維下料排樣領域，尤其是一種基于組化技術的矩形件排樣方法。

背景技術

二維矩形件排樣優化問題廣泛存在于玻璃、木板、鋼板、紙張等需要滿足“一刀切”工藝約束的板材加工行業，其優化目標是在給定的矩形板材上不重疊地放置盡可能多矩形件，以實現板材的利用率最大化。所述一刀切（Guillotine）是指任何一次直線切割都必須能把矩形件分成兩個獨立的矩形件，即任何一條直線切割線都必須從矩形件的一條邊延伸另外一條邊。

當切割過程需要滿足“一刀切”工藝約束時，排樣方法有別于常規的排樣方法。現有的比較經典的方法包括：

（1）分層式排樣優化方法，其基本原理如圖1所示：首先選定一矩形件（如1），以其作為基準，形成一個排樣層，而后在該層的未排樣區進行“一刀切”排樣，如排放3、5，當該排樣層排滿或者不能再排入其他矩形件后，則依照上方式開辟新一層的排樣層，直到所有的排樣結束。在選用基準矩形件以及進行未排樣區的排樣時，依賴于某些帶有啟發意義的排樣規則。對最優排樣方案的搜索就在于更換基準矩形件和優化每層未排樣區的排樣。

分層式排樣優化方法排樣速度較快，但易排除最優解，導致排樣質量下降。

（2）?放寬式搜索方法，具體原理如圖2-4所示：該方法要求板材尺寸固定，當排入一塊矩形件后，如圖2與3所示排入1后，存在兩種“一刀切”的切割方式：橫切和縱切。選擇其中一種后，形成兩個新的排樣區，依次執行類似排樣，如圖4所示。當某種切割方式不能滿足排樣率要求時，如廢料面積超過預期，則該方法回溯，嘗試用另一種切割方式進行排樣。如果在當前尺寸的板材上不能拍下所有矩形件，則放寬當前板材的長或寬，進行下一次排樣嘗試。

放寬式搜索方法放寬尺寸后導致多次搜索而使得搜索速度慢，如果強制設置一些嚴格的回溯條件以提高搜索速度，則也會導致排樣質量下降。

發明內容

為了解決上述技術問題，本發明的目的是：提供一種基于組化技術精確搜索方法、有效縮減搜索空間、提高搜索速度的矩形件排樣方法。

本發明所采用的技術方案是：一種基于組化技術的矩形件排樣方法，包括有以下步驟：

A、將所有矩形件中長度或者寬度相同的矩形件組合成組合矩形件；

B、將上述步驟中的所有矩形件和組合矩形件記錄在輔助存儲結構中；

C、利用組合矩形件及輔助存儲結構，根據待排矩形的尺寸特征，快速檢索優先排樣的組合矩形件；

D、結合上述組合矩形件的快速檢索方法，依據原材料的幾何特征，通過排樣與優化相結合的方式進行最優排樣方案的搜索。

進一步，所述步驟A中，若所有矩形件中存在一個矩形件，其長度或者寬度與一個組合矩形件的長度或者寬度相同，且該組合矩形件不包含該矩形件，則該矩形件與該組合矩形件組合成一個新的組合矩形件。

進一步，所述步驟A還包括有組合的終止條件，所述終止條件為組合成組合矩形件的矩形件超過限定值，或者所述終止條件為任意組合矩形件的長度或寬度超過限定值。

進一步，所述步驟B中，所述輔助存儲結構包括有長度方向輔助存儲結構和寬度方向輔助存儲結構；所述長度方向輔助存儲結構中按照矩形件和組合矩形件的長度降序排列，當存在長度相等的情況時，在相等長度的矩形件和/或組合矩形件中按照寬度降序排列，相等長度的矩形件和/或組合矩形件構成一個段，并記錄每個段的起始位置；所述寬度方向輔助存儲結構中按照矩形件和組合矩形件的寬度降序排列，當存在寬度相等的情況時，在相等寬度的矩形件和/或組合矩形件中按照長度降序排列，相等寬度的矩形件和/或組合矩形件構成一個段，并記錄每個段的起始位置。

進一步，所述步驟C中利用上述輔助存儲結構進行檢索的具體步驟包括有：

獲取待排樣材料的長度值；

在輔助存儲結構中找到不大于該長度值的最大長度的矩形件或組合矩形件，讀取該矩形件或組合矩形件所在段的起始位置；

從起始位置開始，讀取輔助存儲結構中的矩形件或組合矩形件，判斷其是否能排放到當前的待排樣材料中，如果可以，則選擇該矩形件或組合矩形件作為長度方向的最優矩形件；

獲取待排樣材料的寬度值；

在輔助存儲結構中找到不大于該寬度值的最大寬度的矩形件或組合矩形件，讀取該矩形件或組合矩形件所在段的起始位置；

從起始位置開始，讀取輔助存儲結構中的矩形件或組合矩形件，判斷其是否能排放到當前的待排樣材料中，如果可以，則選擇該矩形件或組合矩形件作為寬度方向的最優矩形件；