吳焱明, 曹 寧, 李飛亞, 李 昂

(合肥工業(yè)大學 機械工程學院,安徽 合肥 230009)

0 引言

在板材生產(chǎn)過程中,對于多孔板材的攻絲加工是最耗時的一道工序。金屬板材上各孔的攻絲順序直接影響加工時間,只有合理規(guī)劃攻絲加工路徑,才能縮短刀具行程、提高加工效率。自動攻絲機在板材生產(chǎn)行業(yè)應用比較廣泛,但存在加工時間長、效率較低等缺點。對于大型金屬板材的攻絲加工,由于不同的板材螺紋孔規(guī)格有M3～M10不等,加工過程中需要更換刀具,但因為更換刀具必須要回到刀具的參考點,所以可以將每一類螺紋孔的加工看作是同一類問題。因此，對自動攻絲機同一規(guī)格螺紋孔的加工路徑進行優(yōu)化,能減少總加工時間、提高經(jīng)濟效益。

攻絲機在一次加工完成后,刀具需要回到起點,加工路徑是一個回路,這等同于旅行商問題(traveling salesman problem,TSP)。TSP問題是經(jīng)典的NP-hard問題,可以簡單描述為:一個商人在地圖的一系列城市中訪問,求解訪問每座城市一次并回到起點的最短路程。TSP問題有著廣泛的應用,如數(shù)控加工、無人機路徑規(guī)劃、機器人路徑規(guī)劃、物流配送、網(wǎng)絡通訊等。TSP問題是一個NP完備問題,其解空間存在“組合爆炸”,10個城市的TSP有大約18 000個可能的解,因此,要得到10個城市TSP問題的最短路徑,最壞的可能是要做18 000次搜索;20個城市的TSP問題,最壞可能要做1016次搜索;50個城市的TSP問題搜索次數(shù)更是一個天文數(shù)字。目前,關于TSP問題的解決方案有很多,對于孔群加工而言,現(xiàn)有的TSP問題解決方案大多以改進遺傳算法[1-5]和改進蟻群算法[6-10]為主。文獻[1]提出了改進遺傳算法,以408個孔的大型輪胎模具孔群加工為例,遺傳算法的平均運行時間為10 547.475 s,改進遺傳算法的平均運行時間為3 839.202 4 s;文獻[2]提出了改進蟻群算法,用82個無規(guī)律孔的沖壓板做實驗,基本蟻群算法的平均運行時間為91.311 7 s,改進蟻群算法的平均運行時間為30.730 9 s。在板材多孔加工中,螺紋孔的數(shù)目比較龐大,少則幾十,多則成百上千。在這種規(guī)模的問題中,現(xiàn)有的解決方案搜索時間太長,根本無法滿足生產(chǎn)要求。攻絲機的路徑規(guī)劃不需要一定求出最優(yōu)路徑,但必須在短時間內(nèi)求出在一定范圍內(nèi)的最優(yōu)解,如果路徑優(yōu)化所消耗的時間比刀具走過其縮短的路徑所需要的時間還長,那么這將沒有應用意義。

基于此,本文以攻絲機加工路徑為研究對象,建立以最短路徑為優(yōu)化目標的數(shù)學模型。為提高算法效率,針對實際生產(chǎn)中常見的單一規(guī)格螺紋孔的金屬板材孔位分布形式,采用不同的策略進行分組,運用貪心算法進行路徑規(guī)劃生成最短路徑,減少加工時間。

1 模型建立

攻絲機進行攻絲加工的路徑規(guī)劃問題可描述為:二維平面上有n(n≥1)個螺紋孔需要加工,各孔的圓心記為Pi,圓心坐標為(xi,yi)，i=1,2,…,n。各孔的集合記為A={P1(x1,y1),P2(x2,y2),…,Pn(xn,yn)}。在實際生產(chǎn)中,攻絲機的橫向和縱向最大移動速度相同,因此本文在計算路徑長度時采用切比雪夫距離(Chebyshev distance),即孔間距取兩孔橫坐標和縱坐標數(shù)值差絕對值的最大值。金屬板材螺紋孔i和螺紋孔j間的長度Dij為:

Dij=max(|xi-xj|,|yi-yj|)

(1)

攻絲機的刀具需要找到一條從任意一孔的圓心Pi出發(fā),途中經(jīng)過每個孔圓心的路徑,并使總路徑長度L最短,則L為目標函數(shù)。

2 算法分析

文獻[3]中將貪心算法、基本螞蟻算法以及改進的螞蟻算法進行了比較,選取TSPLIB中的eil51數(shù)據(jù)進行實驗,貪心算法耗時17 ms,基本螞蟻算法耗時8 035 ms,改進螞蟻算法耗時12 158 ms。由此可見,貪心算法在TSP問題求解中運算速度非?？臁?/p>

在對問題求解時,貪心算法總是做出在當前看來最好的選擇。也就是說,不從整體最優(yōu)上加以考慮,而是求出在某種意義上的局部最優(yōu)解。貪心算法解決問題效率高,時間復雜度低,其基本思想是從問題的某一個初始解出發(fā)一步一步地進行,根據(jù)某個優(yōu)化測度,每一步都要確保能獲得局部最優(yōu)解。在板材多孔位加工中,板材的規(guī)格較大(一般為2 m×4 m),螺紋孔數(shù)目也較多,少則幾十,多則成百上千,而且可能有些區(qū)域孔位分布比較密集,有些區(qū)域孔位分布比較稀疏。由于貪心算法的特點是不從整體最優(yōu)上加以考慮,而是求出在某種意義上的局部最優(yōu)解,結合板材孔位分布特點,在進行路徑規(guī)劃之前,先對板材上的螺紋孔群進行分組。因為實際板材的孔位分布不盡相同,本文提出對螺紋孔進行一維分組和二維分組。一維分組為按X坐標分組或按Y坐標分組;二維分組為按X坐標分組后再按Y坐標分組或按Y坐標分組后再按X坐標分組。在分好的每一組內(nèi)采用貪心算法求出每組的最優(yōu)解,最后將每一組的路徑連接起來得到全局加工路徑。

由于孔位分布的不同,按照不同方向進行路徑規(guī)劃結果差異明顯。本文結合分組策略,在路徑規(guī)劃中定義2種路徑法，即XY向路徑法和YX向路徑法。XY向路徑法為:一維分組中按X坐標分組后組內(nèi)按Y坐標進行排序或采用貪心算法;二維分組中按X坐標分組后再按Y坐標分組,組內(nèi)采用貪心算法。YX向路徑法與XY向路徑法相反。

下面以尺寸為732 mm×3 570 mm且分布220個M6的待加工螺紋孔板材為實例進行驗證。

2.1 一維分組后按坐標排序

考慮到在實際生產(chǎn)中,有一些金屬板材的螺紋孔分布呈比較規(guī)則的矩形陣列,或者孔位分布比較密集,因此可按陣列規(guī)律,采用簡單易行的方法進行加工路徑的規(guī)劃,即一維分組后按坐標排序。

首先,根據(jù)攻絲機刀具的起點位置建立板材加工的坐標系,刀具起點位于坐標原點;其次,根據(jù)建立的坐標系對螺紋孔按X軸或Y軸坐標進行排序;最后，根據(jù)排序結果繼續(xù)按X軸或Y軸方向進行分組,組間距為50 mm,組內(nèi)按照Y坐標或X坐標進行排序,這樣可以將問題規(guī)模進行分解,分成若干個小規(guī)模問題進行求解。此算法的路徑規(guī)劃仿真結果如圖1所示。XY向路徑法的加工路徑長度為27 776.0 mm,YX向路徑法的加工路徑長度為27 428.9 mm。

圖1 一維分組后按坐標排序的加工路徑仿真結果

2.2 一維分組后采用貪心算法

在實際生產(chǎn)中,板材螺紋孔的分布并不都是矩形陣列,采用按坐標分組排序得到的路徑不適用于所有板材多孔位加工,因此需要對上述排序方法進行優(yōu)化。

將螺紋孔按X坐標或Y坐標進行排序分組,組間距仍為50 mm,在每組內(nèi)采用貪心算法進行排序。此算法的路徑規(guī)劃仿真結果如圖2所示。XY向路徑法的加工路徑長度為23 191.6 mm,YX向路徑法的加工路徑長度為28 503.5 mm。

圖2 一維分組后采用貪心算法的加工路徑仿真結果

2.3 二維分組后采用貪心算法

考慮到對孔群一維分組后每組的待加工螺紋孔數(shù)目依然很多,不能更好地發(fā)揮貪心算法的優(yōu)勢,因此在對孔群按X坐標或Y坐標分組后,在組內(nèi)對孔群再按Y坐標或X坐標分組,X方向和Y方向的組間距均為50 mm。這樣將金屬板材上的所有螺紋孔分為若干個矩形方塊,即網(wǎng)格狀,故稱為二維分組或網(wǎng)格化分組。將孔群二維分組后,在每個網(wǎng)格內(nèi)采用貪心算法進行排序。此算法的路徑規(guī)劃仿真結果如圖3所示。XY向路徑法的加工路徑長度為23 554.4 mm,YX向路徑法的加工路徑長度為22 257.5 mm。

圖3 二維分組后采用貪心算法的加工路徑仿真結果

3 路徑優(yōu)化

以上3種方法所得到的路徑長度不同,見表1所列。

表1 不同方法及路徑法得到的路徑長度 單位:mm

由表1可知:XY路徑法中二維分組后采用貪心算法所得到的路徑長度比一維分組后按坐標排序得到的結果縮減了15.2%,比一維分組后采用貪心算法得到的結果增加了1.6%;YX路徑法中二維分組后采用貪心算法得到的路徑長度比一維分組后按坐標排序得到的結果縮減了18.9%,比一維分組后采用貪心算法所得到的結果縮減了21.9%;一維分組后按坐標排序YX路徑法比XY路徑法路徑長度縮減了1.2%,一維分組后采用貪心算法XY路徑法比YX路徑法路徑長度縮減了18.6%;二維分組后采用貪心算法YX路徑法比XY路徑法路徑長度縮減了5.5%。

由此可以得出,在相同路徑法下不同方法所得到的路徑結果差異非常大,同樣,相同方法不同路徑法所得到的路徑結果差異也非常大。因此,路徑優(yōu)化需要尋找最優(yōu)方法和路徑法組合,使得路徑長度最短。

以上分析是建立在組間距一定的情況下,下面討論組間距對路徑結果的影響。

在實際生產(chǎn)環(huán)境中,板材上面的螺紋孔一般比較密集,如果組間距的取值大于臨界值時,那么分組時會將所有的螺紋孔分到一組,而此臨界值不會太大。上述每種算法耗時都在加工要求范圍內(nèi),因此在按坐標分組時采用一維搜索的方式尋找最優(yōu)組間距,在網(wǎng)格化分組時采用二維搜索的方式尋找最優(yōu)組間距。組間距從初始值20 mm開始搜索,增量為10 mm,搜索終止條件為該方向的分組結果為一組。

在搜索過程中,組間距的某些取值可以使得上述算法得到的加工路徑總長最短。相較于路徑優(yōu)化所帶來的效果,優(yōu)化過程的時間開銷可以忽略不計,通過搜索最優(yōu)組間距使得算法最終取得了良好的效果。一維分組和二維分組優(yōu)化后的加工路徑仿真結果如圖4所示。

圖4 經(jīng)過優(yōu)化后的路徑結果

一維分組和二維分組優(yōu)化后的路徑長度和耗時見表2所列。

表2 路徑優(yōu)化結果及耗時

一維優(yōu)化路徑是按X坐標分組后采用貪心算法且X坐標組間距為340 mm的情況,路徑長度為21 796.3 mm;二維優(yōu)化路徑是X坐標組間距為50 mm、Y坐標組間距為80 mm且采用YX路徑法的情況,路徑長度為19 832.3 mm。因此最優(yōu)路徑為二維優(yōu)化路徑。在相同方法和路徑法條件下,最優(yōu)路徑長度比初始路徑長度(即組間距為50 mm時的路徑長度)縮減了10.9%,而優(yōu)化總耗時最多不會超過1 s,由此可見路徑優(yōu)化取得了顯著效果。

在路徑優(yōu)化之后,自動攻絲機的整體路徑規(guī)劃算法基本完成,前面的仿真結果還需要進一步在生產(chǎn)現(xiàn)場進行測試驗證。自動攻絲機在實際加工時界面上只顯示最優(yōu)路徑,刀具按照最優(yōu)路徑進行攻絲操作。

實際加工時的界面如圖5所示,其中所顯示的最終加工路徑與仿真時對比得到的最優(yōu)路徑一致。

圖5 自動攻絲機加工界面

4 結論

本文以自動攻絲機的加工路徑為研究對象,提出3種不同的排序算法對孔群加工進行路徑規(guī)劃。第1種有針對性地解決了排列規(guī)則的金屬板材路徑規(guī)劃問題,且簡單易行,另2種基于貪心算法對加工路徑進行優(yōu)化,縮短了加工時長，提高了加工效率。最后通過對分組參數(shù)進行尋優(yōu),對算法進一步優(yōu)化,最終在一定程度上找到了最優(yōu)路徑。通過仿真以及現(xiàn)場測試得出以下結論：

(1) 在實際生產(chǎn)中,一部分板材的孔位分布呈矩形陣列,孔位分布密集且相互之間距離相差很小,此時采用簡單分組后按坐標排序的方式進行路徑規(guī)劃,簡單易行且效率高。但考慮到加工方位的影響,對比2種方位分組排序結果,取路徑最小者為實際加工路徑。

(2) 對于非矩形陣列分布的金屬板材,在分組后采用貪心算法對加工路徑進行優(yōu)化,從而減小路徑長度，縮短加工時間。

(3) 為了充分發(fā)揮貪心算法的優(yōu)勢,將孔群第1次分組后按另一坐標再進行分組,即將金屬板材上的孔群劃分為網(wǎng)格狀,然后采用貪心算法進行路徑規(guī)劃,進一步縮減路徑長度。

(4) 通過對分組參數(shù)的分析,經(jīng)搜索最優(yōu)組間距,得到的最終加工路徑相較于優(yōu)化前的結果縮減明顯。

本文研究結果對機械加工中的零件和板材的制孔以及攻絲路徑規(guī)劃有一定的參考意義,算法易于理解、優(yōu)化,適應性強,運行速度快,能夠大幅度提高加工效率。