大規模角度的二維不規則版片下料方法
2023-10-08 20:13:04 6
專利名稱：大規模角度的二維不規則版片下料方法
技術領域：
本發明涉及版片下料方法領域，特別涉及一種應用於大規模角度的二維不規則版片下料方法。
背景技術：
「下料問題」是把相同形狀的一些原材料分割加工成若干個不同規格大小的零件的問題，此類問題在工程技術和工業生產中有著重要和廣泛的應用。可應用的行業包括鈑金件加工、服裝行業、紙業與玻璃業、木材製品、印刷業排版、集裝貨物、微電子工業的排版等眾多領域，上述印刷業排版涉及對各種書刊的排版，服裝行業涉及各種布料皮革定級中的優化排樣等，集裝貨物涉及將貨物優化地裝入有限空間的貨櫃中，微電子工業涉及集成電路的排布等，可見，對下料問題的相關研究具有十分重要的實際意義。有一篇華東理工大學理學院數學系(上海200237)發表的論文「關於有交貨時間限制的大規模實用下料問題」，對於一維下料問題得到一個有各自交貨時間的模型，該模型提出一種DP貪婪算法，材料利用率高，有效節約了成本。關於規則版片下料方法，有一篇來自華中科技大學計算機科學與技術學院(武漢 430074)名稱為「一種求解矩形塊狀填問題的擬人算法」的論文，該算法使用了兩個主要的思想策略，即矩形塊選擇策略和矩形塊放置策略，對求解矩形塊裝填問題十分有效。二維版片下料問題，在原材料切割生產時，有著很重要的意義。排版布局的優劣， 直接與材料成本、經濟效益有關。瀋陽工業大學信息科學與工程學院發布的一篇名稱為「二維不規則形狀自動排料算法的研究與實現」的文獻，它是針對二維不規則形狀自動排料問題，給出了自動排料的求解思路，並對自動排料的主要算法作出了研究和改進。主要內容包括自動排料過程描述與自動排料主要算法，所述自動排料過程是將新排零件與已排零件或原料邊界保持接觸且不重疊，新零件的最優位置與其方向和已排零件的位置有關，最佳方向和相對位置的確定， 只能靠已排零件邊界移動的試探法來尋找，這將非常耗時，而且很難準確確定新零件的位置。目前存在的主要問題是，材料利用率低，造成了巨大的浪費，特別是對於生產規模較大，原材料成本很高的企業來說，即使將材料利用率提高少許，也會帶來巨大的經濟效益，而現有技術尚未研究出能很好解決上述問題的二維版片的下料方法，所以對二維不規則版片下料的算法研究，具有十分重要的意義。
發明內容
為了克服現有技術存在的缺陷，本發明提供一種應用於大規模角度的二維不規則版片下料方法，有效提高了原材料的利用率，降低了企業的運行成本，提高了其計算速度和整體工作效率。本發明的技術方案如下所述
大規模角度的二維不規則版片下料方法，是將二維版片下料問題，建模成旅行商問題，利用郭濤演化算法(已被應用的工程算法，出自計算機輔助設計與圖形學學報第12 卷第7期，中圖法分類號TP3791. 72)對旅行商問題出色的處理能力，群體爬山策略在前期迅速地進行收斂，有效地解決玩具版片下料中，運算量巨大、收斂速度慢等問題，然後利用既定的規則，順序和角度放置樣片，經過一定代數的運算，達到較好排列的結果。具體過程包括以下步驟(1)先將上述二維不規則版片歸類為佔角、貼邊與正常三種類型，將每個版片依次放入容器擺放的次序作為遺傳因子，隨機生成多個遺傳因子作為初始群體，每個遺傳因子對應每個版片的放置順序和旋轉角度。(2)將上述十個遺傳因子進行逆轉變異操作，保留優勝的遺傳因子，進化到下一代。(3)重複上述步驟( 的過程，直到進化到第N代，停止上述過程，選取最優的遺傳因子作為問題的解，根據最優遺傳因子當中每個版片的角度和排列次序，將版片旋轉制定角度後，逐個放入容器內。(4)從容器底部中點開始，先寬度後高度，逐個像素的搜索適合放置的位置，直到找到適合放下的位置，然後將上述版片放下。(5)重複步驟(4)所述的方法，放置下一個版片，如果版片為佔角或貼邊類型，則先從角上和邊上開始尋找放置位置。進一步，上述步驟(1)中所述多個遺傳因子可以為十個、二十個或者其它數目的遺傳因子作為初始群體；上述步驟C3)中N的數目一般為五十代左右，當然越大越好，最後選擇的遺傳因子更優。將上述方法應用於皮料的生產中經過實踐獲知，200片樣板，排1. 5X IOm的範圍， 耗時10分鐘，原材料利用率達到90 %，相對於通常的手工下料，原材料節約了 20 %，效率提高了 10倍，不僅幫企業節省了大量的資金，也有力地推動了數控切割設備如雷射切割機在原材料切割應用上的推廣。本發明的有益效果是，方法新穎，獨特巧妙，有效解決了二維不規則版片的下料複雜問題，簡化了程序，節約了時間，將該方法應用於各類有需要的行業當中去，能夠為企業節約成本，提高實際運作效率。
圖1為本發明的流程示意圖。
具體實施例方式為使本發明實現的技術手段、創作特徵、達成目的與功效易於明白了解，下面結合具體實施方式
，進一步闡述本發明。實施例參看圖1，本發明大規模角度的二維不規則下料方法，通過一定的規則， 順序和角度放置樣片，經過一定代數的運算，達到較好排列的結果。具體過程包括以下步驟
首先，進行步驟Si，將二維不規則版片歸類，分為佔角、貼邊與正常三種類型；步驟S2，將每個版片依次放入容器擺放的次序作為遺傳因子，隨機生成十個遺傳因子作為初始群體，每個遺傳因子對應每個版片的放置順序和旋轉角度。步驟S3，對上述十個遺傳因子進行逆變異操作，保留優勝的遺傳因子，進化到下一代。重複上述此過程，直到進化到第五十代才停止，選取最優的遺傳因子作為問題的解。最後進行步驟S4，根據所述最優遺傳因子當中每個版片的角度和排列次序，將版片旋轉制定角度後，逐個放入容器內。此時，從容器底部中點開始，先寬度後高度，逐個像素的搜索適合放置的位置，直到找到適合放下的位置，然後將上述版片放下。重複步驟S4將每個版片放到合適的位置，如果版片為佔角或貼邊類型，則先從角上和邊上開始尋找放置位置。通過上述方法，有效提高了原材料的利用率，降低了企業的運行成本，提高了其計算速度和整體工作效率。以上顯示和描述了本發明的基本原理、主要特徵和本發明的優點。本行業的技術人員應該了解，本發明不受上述實施例的限制，上述實施例和說明書中描述的只是說明本發明的原理，在不脫離本發明精神和範圍的前提下本發明還會有各種變化和改進，這些變化和改進都落入要求保護的本發明範圍內。本發明要求保護範圍由所附的權利要求書及其等同物界定。
權利要求
1.大規模角度的二維不規則版片下料方法，其特徵在於，它主要包括以下步驟(1)將二維不規則版片歸類，為佔角、貼邊與正常三種類型，將每個版片依次放入容器擺放的次序作為遺傳因子；(2)將上述多個遺傳因子進行逆轉變異操作，保留優勝的遺傳因子，進化到下一代，然後再進化；(3)選取進化到最後一代的最優遺傳因子作為問題的解，根據最優遺傳因子當中每個版片的角度和排列次序，將版片旋轉制定角度後，逐個放入容器內；(4)從所述容器底部中點開始，先寬度後高度，逐個像素的搜索適合放置的位置，直到找到適合放下的位置，然後將上述版片放下；(5)重複步驟(4)所述的方法，放置下一個版片，如果版片為佔角或貼邊類型，則先從角上和邊上開始尋找放置位置。
2.根據權利要求1所述的大規模角度的二維不規則版片下料方法，其特徵在於，上述步驟( 將優勝的遺傳因子進化五十代或更多代，再選取最後一代的最優遺傳因子作為問題的解。
3.根據權利要求1所述的大規模角度的二維不規則版片下料方法，其特徵在於，在步驟(1)後隨機選取十個遺傳因子作為初始群體，在進行下一步逆變異操作。
全文摘要
本發明公開了一種應用於大規模角度的二維不規則版片的下料方法，它主要是將二維版片下料問題，建模成旅行商問題，利用郭濤演化算法對旅行商問題出色的處理能力，群體爬山策略在前期迅速地進行收斂，有效地解決版片下料中運算量巨大、收斂速度慢等問題，然後利用既定的規則，順序和角度放置樣片，經過一定代數的運算，達到較好排列的結果。本發明方法獨特，有效提高了原材料的利用率，降低了企業的運行成本，提高了其計算速度和整體工作效率。
文檔編號G06F17/50GK102236730SQ20101016410
公開日2011年11月9日 申請日期2010年4月29日 優先權日2010年4月29日
發明者朱衝, 朱順興, 陸曉燕 申請人:上海咔咻智能科技有限公司