鋼邊箱鋼帶沖齒布局算法設計

田文奇

TIAN Wen-qi

（浙江交通職業技術學院 機電學院，杭州 311112）

0 引言

鋼邊箱設計的難點在其包邊鋼帶，看似簡單但約束條件較多，計算復雜。在包邊鋼帶上有扣子、沖齒、剪角、搭接點等多種元素，相互之間又有邊距、間距、長度、相互避讓等諸多約束要求，設計結果必須使鋼帶生產加工省時、省料、加工方便且布局合理。尤其是沖齒加工，為提高加工效率目前常用的加工模具只有6齒、5齒、4齒等三種類型，且條件允許的情況下最好是用6齒模具加工，大大增加了布局難度。

在目前的企業實踐中，鋼帶的設計主要有純手工排料布局和采用AutoCAD等通用CAD軟件進行手工繪圖輔助排料布局兩種方法，但這兩種方法均具有效率低、容易遺漏約束條件、設計結果未經優化、不利于信息交換及對技術人員要求高等局限性。若采用計算機算法實現鋼邊箱專用智能CAD系統進行自動計算，可使行業面貌大為改觀。但截止目前，還未有相關軟件算法研究報道和成熟應用系統。本文基于模擬退火、多邊形檢測算法，提出了一種鋼邊箱包邊鋼帶沖齒快速優化布局算法。

1 沖齒布局問題

鋼邊箱包邊鋼帶由上下兩個邊框和垂直方向四根立條構成，起到連接加固鋼邊箱各膠合板的作用。立條設計較邊框設計要簡單，且絕大大部分細節相似，文中以鋼邊箱邊框設計為主闡述。鋼邊箱邊框鋼帶圍合后的結構示意如圖1所示：

圖1 鋼邊箱邊框鋼帶圍合示意圖

圖1所示為包邊鋼帶在實際使用時的圍合狀態，在生產加工時展開為一條鋼帶，且多個邊框和立條連續加工。沖齒加工時為成組加工，即模具一次沖壓成型多個沖齒，因此在布局時除需同時考慮整組沖齒及該組中每個齒的位置。考慮到安裝拆卸、載重受力等鋼邊箱功能需求，沖齒需在整個鋼帶上均勻合理分布，且不能有任何一齒打在剪角處，因為這樣在鋼帶圍合后會在剪角處形成缺口，影響鋼帶性能。在加工模具需跨剪角或在箱體尺寸較小的情況下，布局難度有所增加。

2 模擬退火求解步驟

模擬退火算法源于固體退火原理，是一種通用概率算法，用來在一個大的搜尋空間內找尋命題的最優解。模擬退火算法不需要有較好的近似值作為初值，有效避免了常規算法對初值的敏感性，且算法具有較好的穩定性。

模擬退火算法求解的主要步驟描述如下[3]：

1）產生初始解狀態S，得到符合約束條件、但未經優化的工藝參數系列，設定初始溫度T0；2）按照特定規則在當前解基礎上隨機產生鄰域新解S’；3）計算新解與當前解的增量Δt’=C(S’)-C(S)，其中C(S)為評價函數。Δt’<0則接受S’作為新的當前解，否則以概率exp(-Δt’/T)接受S’作為新的當前解；4）按一定方式將T降溫，即Ti+1

算法中解空間的構成為沖齒加工布局工藝參數系列，主要包括左邊距、右邊距、各加工位的間距（即加工位置）及加工次數等，其中加工次數可根據其它參數直接算出。解空間中參數如圖2所示。

圖2 布局參數示意圖

圖2中沖齒組依加工模具的不同有6齒、5齒、4齒等不同規格，組中每個齒均不能與剪角位置相沖突，計算后沖齒組的數目即加工次數Cut_Num，右邊距Offset_R可根據最后一個齒組位置自動產生。由于不同的兩剪角間的加工模具間的間距可能并不同相同，圖2中所示的間距在整個鋼帶上并不是一致的，即解空間中包含若干個間距參數Gap1 、Gap2…Gapn。

3 剪角避讓

在沖齒加工時，不能在剪角處（即進行圍合時鋼帶折彎處）留下缺口，這樣影響鋼帶強度、應力分布以及美觀性，因此在進行沖齒布局時要使整個齒組的所有加工齒避開剪角折彎處。沖齒和剪角相互位置如圖3所示。

圖3 沖齒剪角相互位置

在展開狀態下，剪角呈三角形。由圖可知，沖齒與剪角的相互位置可總結為三種情況：1）沖齒完全處于剪角區域外部；2）沖齒完全處于剪角區域內部；3）沖齒與剪角區域有交叉重疊但無相互完全包含關系。三種情況中，第三種情況為沖突狀態，在加工設計時應予以避免。

在將沖齒尖角處的小段圓弧以5段直線擬合的前提下，沖齒和剪角顯然均為凸多邊形，因此沖齒與剪角的沖突檢測可轉化為兩個凸多邊形的沖突檢測。設沖齒的頂點為P1P2…Pn，剪角的頂點為Q1Q2…Qn，由圖3可知，要檢測兩多邊形是否有交叉（相互包含情況除外），則只需判斷由多邊形1的任意連續兩個頂點構成的線段PiPi+1與多邊形2的任意兩個頂點構成的線段QjQj+1是否存在相交的情況，若均不存在相交情況，則可認為兩多邊形無沖突。

快速判斷兩線段是否相交可采用叉積法。兩有向線段相交的充分必要條件為點Pi、Pi+1位于線段QjQj+1的兩側，而點Qj、Qj+1亦位于線段PiPi+1的兩側，即兩線段相互跨立對方。在本例中若兩線段共線亦可視為交叉沖突的情況。若線段矢量PiPi+1跨立QjQj+1，則有：

式1中(Pi-Qj)×(Qj+1-Qj)為兩向量的叉積，其他同理。考慮到共線情況也視為沖突，則式1可改寫為：

線段矢量QjQj+1跨立PiPi+1同理可推出。依次對多邊形各線段進行相交測試，只要出現有線段相交情況，則可得出兩多邊形有沖突的結論。

在一個齒組中，只要有一個齒與剪角相沖突，即視為該齒組與剪角沖突，必須對整個齒組進行位置調整。在算法實現中，為提高執行速度，在進行沖突檢測時可先期進行矩形檢測，即先判斷沖齒組的包絡矩形是否與剪角沖突，若無沖突則表明齒組中所有齒均不可能與剪角相沖突，不必進行進一步的逐齒檢測。

對于與剪角沖突的齒組，需先計算齒組中與剪角沖突的齒調整到不沖突狀態所需的距離（向左為負，向右為正），取絕對值較小者為整個齒組需要移動的距離。

4 初始狀態與相鄰狀態的產生

模擬退火算法必須先得到一個初始解，并以此為基礎進行演化。鋼帶沖齒布局初始狀態的計算描述如下：

1）在工藝要求允許的OffsetL_Min～OffsetL_Max范圍內，隨機產生左邊距Offset_L和右邊距Offset_R，邊距的選擇直接影響后續實際參加計算的鋼帶長度；

2）根據箱體的設計載重W，推算出理想的加工齒組間距值Gap_Ref（此處可采用間距與載重間的行業經驗系數），若計算出的Gap_Ref超出允許的工藝范圍，則直接取允許的最小值或最大值；依據Gap_Ref估算加工次數Cut_Num以及各加工位置的坐標，設鋼帶長度為Len，則Cut_Num=( Len-Offset_L-Offset_R)/ Gap_Ref，結果取整。需要說明的是此時各齒組間的間距為均勻的，即均為Gap_Ref；

3）按照第3節中提到的剪角避讓算法，對所有沖齒組進行剪角避讓計算，調整與剪角有沖突的所有沖齒組的位置，產生新的間距Gapi和加工坐標，Gap_Ref被替代；

4）無論沖齒組位置是向左還是向右移動，都將影響與其相鄰的加工位置的間距，導致局部間距不均勻。因此需要對相鄰兩剪角間的所有加工位置再次進行均一化處理，可先保持在步驟（3）中被調整過位置的沖齒組不動，根據相鄰剪角間距離和剩余的沖齒組數目計算局部均一化間距，并據此調整相應沖齒組位置。經上述步驟即得到n個實際間距Gap1、Gap2…Gapn，n的大小取決于沖齒組的個數，亦即加工次數。

5）若Gap1、Gap2…Gapn有任一值超出工藝允許的間距范圍，則本次計算失敗，回到步驟1）重新計算。

通過上述方法得到初始解，已具備相當程度的實用性，且初始解是以理想間距值作為計算起點，可在一定程度上保證最終計算出各間距與理想值不會偏離太大，在本例中足以滿足要求。

初始狀態產生后，對決策變量Offset_L、Offset_R和Gap_Ref進行變換。決策變量新值產生函數為x’ =x±r*factor，其中r為0～1間的隨機數，factor為自適應鄰域因子，factor在每次迭代時應逐步減少。在新值產生后若超出工藝要求允許的范圍，則需重新產生。決策變量新值重復上述步驟3）和步驟4），計算間距值，若得到的Gap1…Gapn有任一值超出工藝允許的間距范圍，則視為本次演化失敗，需重新產生決策變量新值，并重新計算結果。

5 評價函數

沖齒布局除滿足加工工藝要求外，還希望分布均勻，即加工位置間距一致性好，選擇沖齒分布均勻性作為算法中模擬退火評價函數可保證得到優化的計算結果。沖齒分布的均勻性可以標準差加以評價。標準差是一組數據平均值分散程度的一種度量。一個較大的標準差，代表大部分數值和其平均值之間差異較大；一個較小的標準差，代表這些數值較接近平均值。設評價函數為C(S)，則其計算公式為：

6 結束語

模擬退火算法在解決文中所及排料布局問題具有天然優勢，應用實踐表明沖齒布局算法具有良好的性能和速度，能產生理想的放樣結果。若給定的箱體尺寸和模具類型在客觀上無法放樣，程序可自動選擇齒數更少的模具并重新計算。為滿足用戶的個性需求，在自動計算的基礎上增加交互編輯功能，使軟件具備良好的商用價值。在箱體尺寸和工藝參數范圍不是很大的前提下，采用遍歷搜索之類的方法亦可實現放樣布局，但此類方法不具有通用性，且結果沒有得到足夠的優化。

[1] 周之平,張颯兵,吳介一等.基于矩形包圍盒的多邊形碰撞檢測算法[J].中國圖象圖形學報：A輯.2004,9(11)：1294-1303.

[2] 吳輝.求解兩個簡單多邊形碰撞距離的最優算法[J].華中理工大學學報.1995,23(4)：89-91.

[3] 趙晶,唐煥文,朱動芝.模擬退火算法的一種改進及其應用研究[J].大連理工大學學報,2006,46(5)：775-780.

[4] 許小勇.混沌模擬退火算法在數值函數優化中的應用[J].計算機與數字工程.2010,38(3)：37-40.

[5] 肖思和,魯紅英,范安東,宋弘.模擬退火算法在求解組合優化問題中的應用研究[J].四川理工學院學報：自然科學版,2010,23(1)：116-118.

[6] 計華,于治樓.一種分階段優化的排料算法[J].計算機應用,2008,28(B06)：333-336.

[7] 曹鋒,賈桂紅.基于VC＋＋的二維排料與數控自動編程系統的設計[J].機床與液壓.2008,36(9)：130-132.

[8] 毛美姣.基于遺傳規劃的連接板優化排料算法的研究[J].機械科學與技術.2008,27(2)：180-183.