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

關(guān)鍵詞：CIMS；CAD/CAPP/CAM；點(diǎn)位最優(yōu)化；旅行商問(wèn)題

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

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

1 數(shù)學(xué)描述

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

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

    為了采用該算法，我們假定：①G是由n個(gè)結(jié)點(diǎn)組成的無(wú)向正權(quán)圖，即G的任意兩結(jié)點(diǎn)間有邊，且邊無(wú)向；②G的任意三結(jié)點(diǎn)符合三角不等式關(guān)系：兩邊之和大于第三邊。

    如果設(shè)G的邊權(quán)代表結(jié)點(diǎn)間的距離，用結(jié)點(diǎn)vk的下標(biāo)K(K為結(jié)點(diǎn)序號(hào))建立兩個(gè)序列S和T，則算法描述如下：

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

(2)對(duì)S中的各結(jié)點(diǎn)，求dis?tmin=min(dist(j,k))，(j∈S,k∈T)?

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

(3)設(shè)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=Ф，結(jié)束；否則轉(zhuǎn)第(2)步。

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

2 程序算法

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

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

3 實(shí)際驗(yàn)證

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

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

4 結(jié)語(yǔ)

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