[發明專利]一種基于最佳匹配規則與禁忌搜索的排樣優化方法和系統

在審

• 申請號: 202211615149.1
• 申請日: 2022-12-15
• 公開（公告）號: CN115965131A
• 公開（公告）日: 2023-04-14
• 發明（設計）人: 饒運清;趙旭升;羅強;方杰;杜冰;徐佳泰;楊飄若;萬曉晨;余守波
• 申請（專利權）人: 華中科技大學
• 主分類號: G06Q10/04
• 分類號: G06Q10/04;G06Q10/0631;G06Q50/04
• 代理公司: 華中科技大學專利中心 42201
• 代理人: 彭軍芬

本發明提供了一種基于最佳匹配規則與禁忌搜索的排樣優化方法和系統，屬于排樣優化技術領域。排樣過程中存在的后向影響的特性造成順序上的調整與布局上的調整無法對應，制約了順序調整的有效性。傳統方法未考慮該特性，采取了非必要且復雜的低效操作。本發明在保留最佳匹配規則的定位高效性的基礎上，改變了順序更新的方式，在原有順序中選擇某零件作為布局上保留和改變的分界點，且避開順序調整上的復雜操作，而僅采取該零件與該零件的后置零件之間的交換操作，通過這種方式保留該零件的前置零件的布局，改變該零件的后置零件的布局，與零件布局更新的方式更契合，避免了傳統方法所采取的過多的非必要且低效的復雜操作，提高了搜索效率。

技術領域

本發明屬于排樣優化技術領域，更具體地，涉及一種基于最佳匹配規則與禁忌搜索的排樣優化方法和系統。

背景技術

在工業切割行業的數字化制造流程中，排樣優化問題存在于下料切割環節中的設計環節，即在給定樣板上合理設計預定形狀零件的布局，零件之間不可重疊且靠接緊密，以此達到提高材料利用率的目的。矩形零件排樣是排樣優化問題中的一類分支問題，其零件形狀均為矩形，且零件采用正交放置，即矩形零件的邊界平行或垂直于板材的邊界，這種方式能夠保證零件排列的緊密程度。

排樣優化問題的解決方法稱為排樣優化算法，典型的排樣優化算法由定位策略與搜索算法兩部分共同組成，定位策略即通過設定啟發式的定位規則確定零件應放置的位置，而搜索算法是在定位策略的基礎上改變零件的順序與角度，構造不同的排樣布局并在其中挑選優質布局。常用的定位策略包含左下規則(bottom?left)和最佳匹配規則(bestfit)，左下規則與最佳匹配規則都要求設定零件的順序，但左下規則按照設定的零件順序執行排樣，讓每個零件放置于板材上最靠左下的位置，而最佳匹配規則并非完全按照設定的零件順序執行排樣，而是遍歷剩余零件并選出在當前排樣情況下最適合的零件，并放置于板材上選定的位置。

由于排樣過程中零件是按照順序逐個放置于板材上的選定位置，每個放置的零件將改變現有的零件邊界線結構，而邊界線結構又決定了下一個零件的選擇與零件的放置位置，因此，排樣過程具有后向影響的特性，即優先放置的零件始終影響著靠后放置的零件的排樣過程。

搜索算法通常以排樣質量的逐漸優化為目標，通過迭代的方式調整零件的順序，其調整方式為保留某些零件的順序，改變其余的零件的順序。在執行搜索算法時，零件的新的順序由原有順序做出調整而產生，并且原有順序和新的順序都需要經過零件逐個放置的方式構成排樣布局。由于排樣過程的后向影響的特性，順序上產生變化的第一個零件將改變原有順序對應的排樣布局中的零件邊界線結構，即從該零件開始，后續所有零件的布局將發生改變，因此，順序上的調整無法轉化為布局上的相應的調整，搜索算法仍存在搜索效率不足的缺陷。CN103500255A公開了一種用于矩形件的智能排樣方法，其矩形排樣滿足一刀切下料工藝，采用最低水平線的定位策略，結合遺傳算法搜索零件的順序。CN113032921A公開了一種基于并行自適應參數布谷鳥搜索與最低水平線的排樣算法，同樣采用最低水平線的定位策略，并改進布谷鳥算法，通過并行策略與參數自適應策略增強搜索的魯棒性。CN110909947A公開了一種基于灰狼算法的矩形件排樣方法及設備，同樣采用最低水平線的定位策略，改進了傳統灰狼算法的包圍、圍獵和游走，簡化了算法的流程同時增強搜索能力。這些方法均采用了隸屬于最佳匹配規則的最低水平線定位規則，但是搜索算法均未考慮排樣過程的后向影響的特性，因而搜索效率仍有待提高。

發明內容

針對現有技術的以上缺陷或改進需求，本發明提供了一種基于最佳匹配規則與禁忌搜索的排樣優化方法和系統，其目的在于解決現有搜索算法因未考慮排樣過程的后向影響的特性而采取了復雜且非必要的排序操作，導致搜索效率不足的技術問題。

為實現上述目的，按照本發明的一個方面，提供了一種基于最佳匹配規則與禁忌搜索的排樣優化方法，包括：

S1.隨機初始化矩形零件的順序序列和方位序列；