二維不規(guī)則排樣CAD系統(tǒng)的設計.pdf

1、本文研究了二維不規(guī)則圖形的排樣問題，它對制造、船舶、服裝、模具等眾多行業(yè)有重要意義。二維排樣是一個平面布局優(yōu)化問題，目的是在平面板材上盡可能多的布置不同形狀的零件，并滿足以下約束條件：(1) 零件布置于板材內部且布置的零件盡可能的多；(2) 各零件之間互不重疊；(3) 滿足一定的工藝要求。它的優(yōu)化目標是：尋求一個優(yōu)化零件布局方案，使得浪費的板材面積為最小，亦即材料利用率為最大。針對目前二維排樣問題中的難點和關鍵問題，本文就幾何計算、定位

2、規(guī)則以及智能優(yōu)化等3個方面，進行了廣泛而深入的理論研究，提出了一系列解決方案和算法，并將其編入CAD應用系統(tǒng)。研究成果和創(chuàng)新點可概括如下： (1)臨界多邊形NFP算法研究：采用了一種新的基于軌跡線計算的臨界多邊形快速求解算法，解決了NFP求解的準確性問題，并在NFP的計算速度上有了較大的提高。 NFP算法是二維排樣問題中的基礎性幾何計算問題，也是目前限制二維排樣算法發(fā)展的瓶頸問題。長期以來缺乏準確、穩(wěn)定、快速的NFP算

3、法，使得零件定位優(yōu)化、多角度旋轉、板材帶孔洞等問題得不到很好的解決，而NFP算法的計算速度也限制了排樣問題往智能優(yōu)化方面發(fā)展。 本文提出了一種新的臨界多邊形快速求解算法，力求比較徹底地解決NFP計算問題。該算法將多邊形滑動碰撞問題轉化為頂點和邊之間的軌跡線計算，從而可引入幾何索引算法降低時間復雜度，并可統(tǒng)一處理板材孔洞、內部靠接NFP等特殊情況。理論分析和實驗結果表明新的NFP算法的計算速度較優(yōu)化移動碰撞法有較大提高(降低一個數(shù)

4、量級)。 (2)零件定位規(guī)則研究：提出了基于重心NFP的最點重心點定位算法，通過選擇多角度重心NFP中的最低重心位置來確定零件的排樣位置，從而使得排樣后的邊界能夠保持水平，同時提高了零件分布密度。 (3)智能排樣算法研究：結合NFP中幾何計算的特點，提出采用遺傳算法(GA)負責零件調度優(yōu)化，遺傳算法部分涉及個體編碼、種群進化過程、適應度計算等方面；最后討論了GA與NFP計算的結合與優(yōu)化，并進行了實例計算和對比。實驗表