摘要：概要介紹了所實施CIMS環(huán)境中的CAM系統(tǒng)，提出了在該系統(tǒng)中對數(shù)控代碼進行優(yōu)化處理的必要性。為滿足這一要求，利用圖論中經(jīng)典的"旅行商問題"數(shù)學模型，對墻板類零件典型的大量孔加工進行了優(yōu)化處理。實現(xiàn)了加工多個特征時所規(guī)劃的走刀路徑最短，縮短了走刀時間，提高了加工效率。

關鍵詞：CIMS；CAD/CAPP/CAM；點位最優(yōu)化；旅行商問題

    CAD/CAPP/CAM系統(tǒng)在CIMS中占有極其重要的地位。在某企業(yè)CIMS一期工程中，實現(xiàn)了基于產(chǎn)品數(shù)據(jù)管理(Product Data Management，PDM)的初步集成。該工程采用的CAD/CAM商用軟件為I-DEAS，CAM系統(tǒng)以I-DEAS GM模塊為平臺，一方面接受CAPP生成的工藝結果，另一方面接受CAD的幾何實體信息，生成各種加工信息，自動規(guī)劃刀位軌跡，經(jīng)過后置處理模塊，生成適用于不同數(shù)控系統(tǒng)的NC代碼。

    盡管創(chuàng)成式CAPP規(guī)劃了工序內(nèi)容，但沒有約束一道工序內(nèi)的加工順序。如果工序內(nèi)含有多個加工特征，如加工多個孔，則其加工順序由CAD系統(tǒng)的造型次序決定，因為CAM加工特征的實體號由CAD傳遞過來的。設計人員在造型過程中不考慮加工順序，這就意味著CAM規(guī)劃的加工順序是隨機的，由此會增加走刀路徑，增加能耗和降低加工效率，特別是加工特征數(shù)量很大時，這種問題暴露得更加明顯。本文采用數(shù)學上的"便宜"算法，在生成數(shù)控代碼的過程中，進行了特征加工的點位最優(yōu)化，很好地解決了該問題。

1 數(shù)學描述

    特征加工點位優(yōu)化的數(shù)學模型是圖論中的旅行商問題。這一問題的原形，即有一個旅行售貨商要從他所在的村子出發(fā)，到周圍的幾個村子售貨，每個村子去一次，最后回到出發(fā)點，求他的一條最短路徑。如果抽象成數(shù)學語言，可以說成： 給定一個正權完全圖，求其最短的哈密爾頓道路。如圖1所示，這是由結點?V1至V6組成的正權完全圖G，結點間的細線稱作邊，設線的長度為邊權；則粗線是旅行商問題的解。

     對這類問題的精確求解法是分支與定界法，它是在搜索過程中不斷地構造分支與確定界值；一旦確定了界值，則對大于等于界值的分支不再搜索，最后得到的界值就是問題的最優(yōu)解。此方法比枚舉法優(yōu)越得多，但是在最壞情況下，其計算復雜度仍為(n!)次(枚舉法的平均計算復雜度為(1/2(?n?-1)!))。因此，在實際問題中，需要采用近似算法求得問題的近似最優(yōu)解，以避免巨大的計算量。"便宜"算法是其中較好的一種近似算法。

    為了采用該算法，我們假定：①G是由n個結點組成的無向正權圖，即G的任意兩結點間有邊，且邊無向；②G的任意三結點符合三角不等式關系：兩邊之和大于第三邊。

    如果設G的邊權代表結點間的距離，用結點vk的下標K(K為結點序號)建立兩個序列S和T，則算法描述如下：

(1)置 S={2，3，¨¨，?n?}，T={1}；

(2)對S中的各結點，求dis?tmin=min(dist(j,k))，(j∈S,k∈T)?

(其中假定dis?t(i,j)為求結點i和j?間距離的函數(shù))

(3)設distmin=dist(m,n), ?(m∈S,n∈T)?

若dist(m,n-1)-dist(n,n-1)≤dist(m,n+1)-dist(n,n-1),則?m插入到T的n-1、n之間，否則，m插入到T的n、n+1?之間。

在S中將m?的位置置為零；

若S=Ф，結束；否則轉第(2)步。

T是一個不斷擴充的初級道路，最初只有一個結點。結點?m?插入的原則是尋找插入后對總路程貢獻小的位置。如果旅行商問題的最優(yōu)解為?Q?，"便宜"算法的解是?T，則可以證明T/Q＜2?。這一結果的近似程度并非理想，但在實際中它的解與最優(yōu)解十分接近，計算復雜度小，因而我們采用此種算法。

2 程序算法

程序邏輯如圖2和圖3所示。

    先從后置處理模塊產(chǎn)生的初始數(shù)控代碼文件中讀出各特征位置，即加工中各個特征的坐標值，按"便宜"算法求得最短路徑后，遵從模態(tài)原則回寫到原文件中。

3 實際驗證

    上述算法通過編碼實現(xiàn)，應用在企業(yè)CIMS的 CAM分系統(tǒng)中，取得了很好的效果。圖4是一個墻板類零件的孔加工示意圖。

    在加工多個孔特征時，例如，鉆12個孔，走刀路徑由CAD特征造型次序決定，其值并非最優(yōu)，如圖5所示。經(jīng)過本文提出的算法優(yōu)化后，刀位路徑結果如圖6所示，圖中虛線為刀具路徑。

4 結語

    作者將經(jīng)典的旅行商問題數(shù)學模型成功地應用于CAM分系統(tǒng)的后置處理模塊中，解決了生產(chǎn)實際問題。經(jīng)過實際驗證，尤其是在打中心孔時，由于一把刀具要完成80余個孔的加工，經(jīng)過該方法優(yōu)化的刀具路徑和原始的未經(jīng)處理的路徑相比，大大縮短了加工時間。因此，本文的算法符合實際情況，解決了多孔加工時刀具路徑冗長、加工效率較低的問題。