基于改進Floyd算法的轉(zhuǎn)向機拆卸序列研究*

劉玉娟，易朋興*，胡玖坤，羅璐琴

(1.華中科技大學(xué) 機械科學(xué)與工程學(xué)院，湖北 武漢 430070；2.東江環(huán)保股份有限公司，廣東 深圳 518057)

0 引 言

隨著我國汽車工業(yè)的飛速發(fā)展，汽車報廢量也逐年增加，而拆卸是回收和再利用的前提。良好的拆卸序列有利于提高拆卸效率、降低拆卸成本，因此退役汽車零部件拆卸序列規(guī)劃成為研究熱點之一。

目前，研究廢舊產(chǎn)品拆卸序列的基本思路就是“拆解模型(圖)+方案的尋優(yōu)算法”[1]。薛俊芳等[2]構(gòu)建了產(chǎn)品拆卸有向圖，將時間和拆卸復(fù)雜度的乘積作為權(quán)重，然后利用Floyd算法求出目標零件的最優(yōu)拆卸序列；張新建等[3]構(gòu)建了產(chǎn)品拆卸混合圖，分別以最少時間和最少費用作為評價標準，利用Floyd算法進行優(yōu)化分析。這兩種圖的模型都只適合對目標零件的拆卸進行優(yōu)化，在利用Floyd算法尋找最短路徑時不能遍歷所有節(jié)點，因此不能實現(xiàn)完全拆解。在實際拆解中，很多時候是把產(chǎn)品的一部分作為一個整體拆卸下來，然后再分別拆解。有向圖和混合圖中都只能表述零件之間的連接關(guān)系，不能反映一個部件(子裝配體)拆卸下來的情況。王喆等[4]在與或圖的基礎(chǔ)上演變出了拆卸網(wǎng)絡(luò)圖，可以解決上述問題，但未對Floyd算法進行改進，當拆卸網(wǎng)絡(luò)圖的節(jié)點較多時，出現(xiàn)計算效率低的情況。國內(nèi)外學(xué)者對Floyd算法進行了研究[5～7]，提出了改進思想。鄒桂芳等[8]對Floyd算法進行了改進，只需兩步迭代即可求出結(jié)果，提高了算法效率；徐達等[9]對Floyd算法進行優(yōu)化，省略非必要中間節(jié)點路徑計算，減少了計算量。

轉(zhuǎn)向機是汽車轉(zhuǎn)向系統(tǒng)中的核心部件，且被證明具有良好的可再制造性[10]。本文將對轉(zhuǎn)向機的拆卸序列進行研究，采用拆卸網(wǎng)絡(luò)圖對產(chǎn)品進行拆解建模，再利用改進的Floyd算法對其進行求解，從而得到轉(zhuǎn)向機優(yōu)化的拆卸序列。

1 轉(zhuǎn)向機拆卸網(wǎng)絡(luò)圖的構(gòu)建

1.1 轉(zhuǎn)向機結(jié)構(gòu)特征

循環(huán)球式轉(zhuǎn)向機的結(jié)構(gòu)圖如圖1所示。

圖1 循環(huán)球式轉(zhuǎn)向機1-螺桿；2-螺母；3-鋼球；4-扇齒；5-搖臂軸；6-殼體；7-推力軸承

轉(zhuǎn)向機有兩個傳動副，第一傳動副由螺桿、鋼球和螺母所組成，第二傳動副由螺母上的齒條和轉(zhuǎn)向搖臂軸上的齒扇組成。工作時，因鋼球經(jīng)過位于螺母中的球孔和插入球孔中的導(dǎo)套可循環(huán)流動，故稱之為循環(huán)球式轉(zhuǎn)向機。

對于一般的軸系結(jié)構(gòu)而言，按照從外到內(nèi)的順序依次拆卸即可，但循環(huán)球式轉(zhuǎn)向機的轉(zhuǎn)向螺桿和轉(zhuǎn)向臂軸呈十字交叉分布，拆解規(guī)劃涉及4個方向的變換，需重點考慮拆卸方向及拆卸工具的變化對拆卸的影響。

此外，傳統(tǒng)的拆卸序列規(guī)劃都是考慮將單個零件從裝配體上拆卸下來的先后順序，沒有考慮一個部件(子裝配體)拆卸下來的情況。但對于循環(huán)球式轉(zhuǎn)向機的螺母組件來說，若直接從裝配體上拆除導(dǎo)管和鋼球等零件，不便于使用拆卸工具，應(yīng)先把螺母組件作為一個整體從螺桿上拆下來再進行拆卸，則減小了拆卸難度。

1.2 拆卸網(wǎng)絡(luò)圖構(gòu)建規(guī)則

拆卸網(wǎng)絡(luò)圖是由與或圖演變而來的。在與或圖中以節(jié)點的形式來表達產(chǎn)品的拆卸狀態(tài)，從產(chǎn)品總成出發(fā)分析其可能的拆卸方式，并將拆卸后的零件用一條圓弧連接起來，它們之間是“與”的關(guān)系；若對于同一個部件，存在不同的拆卸方式，那么不同的拆卸方式之間是“或”的關(guān)系[11]。

拆卸網(wǎng)絡(luò)圖也是從產(chǎn)品總成出發(fā)，選定一個零件作為產(chǎn)品完全拆卸的終點，從而使所有的拆卸路徑歸于同一個節(jié)點。此外，拆卸網(wǎng)絡(luò)圖在與或圖的基礎(chǔ)上進行了簡化，把所有的單體零件刪除，只關(guān)注部件下一步的拆卸序列；對于部件(子裝配體)作為一個整體拆卸下來的情況，在同一個節(jié)點中用逗號隔開表示不同的部件。

1.3 基于MTM方法的拆卸時間評估

在得到拆卸路徑的網(wǎng)絡(luò)圖后需要給每條邊賦予相應(yīng)的權(quán)值，現(xiàn)有的評價標準包括拆解時間、拆解成本和拆解能量[12]，對于完全拆解來說，拆解成本隨拆解時間的增加而增加，因此本文以拆解時間作為評價標準。

基于方法時間衡量(method time measurement，MTM)法是一種時間測量技術(shù)，其基本單位為TMU，換算關(guān)系為1 TMU=0.036 s。相比于常用的直接法和間接法測量拆卸時間，MTM法不受拆卸人員業(yè)務(wù)水平和拆卸環(huán)境的影響，減少人工干擾，因此本文采用基于MTM方法的報廢汽車拆卸時間確定法。

MTM法是按基本動作單元(足動、腿動、轉(zhuǎn)身、俯屈、跪、站、行、手握)和執(zhí)行因素(伸手、搬運、旋轉(zhuǎn)、抓取、對準、拆卸、放手)設(shè)定作業(yè)時間標準及查定正常作業(yè)時間，制定作業(yè)標準時間[13]。利用MTM法確定拆卸時間時，首先要根據(jù)作業(yè)決定基本動作，然后測定基本動作的大小(如距離、旋轉(zhuǎn)角度等)，識別動作的基本性質(zhì)，最后通過代碼對動作進行描述，根據(jù)代碼查表即可得到相應(yīng)的時間。MTM法分析方法較為復(fù)雜，但是精度較高，適用范圍廣泛。

這里以其中一步拆卸操作—從轉(zhuǎn)向機殼體上取下加油螺口為例進行分析，其MTM編碼如表1所示。

表1 取加油螺口的MTM編碼

則拆卸時間為：T=TMU×0.036 s×頻率=(8.2+2.0+18.0+9.4×14+18.0)×0.036=6.4 s，向上取整為7 s。

2 改進Floyd算法

2.1 Floyd算法簡介

Floyd算法是用于求解加權(quán)網(wǎng)絡(luò)最短問題的經(jīng)典算法，其核心是一種逐步逼近的思想[14]?；静襟E如下：

(1)網(wǎng)絡(luò)圖D={v，w}，v表示圖中節(jié)點，w表示節(jié)點間的連接，將網(wǎng)絡(luò)圖轉(zhuǎn)化為賦權(quán)矩陣D，矩陣中第i行第j列元素表示從節(jié)點i到節(jié)點j的距離，當i=j時，dij=0；若節(jié)點i和節(jié)點j之間沒有直接相連的線，則dij=∞。

(2)將賦權(quán)矩陣進行多次迭代，得到一個矩陣序列D1、D2、…、Dn，其中：

(1)

迭代完成后，Dn中的元素就是最終從節(jié)點i到節(jié)點j的最短路徑。其核心思想是讓原始路徑依次跨接v1、v2、…、vn各個節(jié)點，即從跨接一個節(jié)點到跨接n個節(jié)點。每次迭代中保留距離較短的路徑，完成所有迭代后即可找到任意兩點之間的最短距離。

(3)反向追蹤，找到具體的路徑。Floyd算法的一個原理是，假設(shè)P是從i到j(luò)最短路，k是P上的一個節(jié)點，則沿著P從k到j(luò)，必然也是從k到j(luò)的最短路。因此，可以定義一個path矩陣，與賦權(quán)矩陣同時迭代，用來追蹤最短路徑。

2.2 改進Floyd算法分析

Floyd算法雖然能找到任意兩個節(jié)點之間的最短路徑，但每個節(jié)點都需要迭代n次，共有n×n個節(jié)點，因此算法復(fù)雜度為O(n3)。當節(jié)點數(shù)量較大時，算法需要進行n3次加法計算，計算效率很低；并且原始算法需要迭代n次，產(chǎn)生了n個迭代矩陣，占據(jù)較大的內(nèi)存空間。

針對這些問題，學(xué)者們提出了許多改進方法。文獻[9]的核心思想是較小的行與列先計算，通過兩次迭代即可完成計算。第一次迭代計算D1時，第一行和第一列不需計算，直接計算第二行和第二列中未包含在第一行和第一列中的元素，讓其跨接，接著計算第三行和第三列中未包含在第1、2行和第1、2列中的元素，讓其跨接v1，依次下去，直到第n行。第二次迭代則反向進行，先計算第n-1行和第n-1列中未包含在前n-2行和前n-2列中的元素，讓其跨接節(jié)點，反向向較小的行列元素計算，完成第二次迭代。分析對比改進前后的算法可知，一般Floyd算法是n次迭代，讓各個路徑依次跨接所有節(jié)點，逐一比較、選擇其中最小值，而改進后的Floyd算法僅通過兩次迭代就能跨接到所有節(jié)點，完成n次比較。這種方法通過兩次迭代即可求得最短路徑，大大減少了計算所需的內(nèi)存空間。

本文將兩種改進方法融合，既能減少程序占用的內(nèi)存空間，又能減少計算量，提高運算效率。

改進Floyd算法的偽代碼描述如下：

Input：

賦權(quán)矩陣：Dn×n={D12,D13,…,Dnn}

Output：

規(guī)劃矩陣：：Dn={D12,D13,…,Dnn}

路徑矩陣：path={v11,v12,…,vnn}

Begin：

1.fori=2 ton

2.forj=i+1 ton

3.fork=1 toi-1

4.ifDij是所在行或列的最小值

6.else=min{Dij,Dik+Dkj};

7.ifDij是所在行或列的最小值

9.elseDji=min{Dji,Djk+Dki};

10.end for

11.fori=n-1 to 1

12.fork=ntoi+1

13.forj=i+1 ton

14.Repeat 4～9

15.end for

End

3 算例分析

本文以某型循環(huán)球式轉(zhuǎn)向機為例來驗證本算法的可行性與有效性，其結(jié)構(gòu)圖如圖2所示。

由于很多零部件是作為附屬件依附于主要零部件的，當進行拆解時只要將主要零部件拆解完成，附屬件可以從主要零部件中分離出來，如螺栓、螺母、墊片和軸套等零件均為附屬件，在本文中對其進行了簡化使模型更為直觀，同時也為后續(xù)拆解規(guī)劃提供便利。筆者在分析零件之間聯(lián)接關(guān)系的基礎(chǔ)上，把螺桿螺母組件作為一個整體進行拆卸，組件中包含的零部件拆卸順序可以確定且是唯一的。

轉(zhuǎn)向機零部件的信息表如表2所示。

圖2 循環(huán)球式轉(zhuǎn)向機爆炸圖a-加油螺口；b-左端蓋；c-調(diào)整螺栓；d-轉(zhuǎn)向臂軸；e-轉(zhuǎn)向臂軸油封；f-殼體；g-螺桿螺母組件；h-軸承i-上端蓋；j-轉(zhuǎn)向螺桿油封

代號名稱拆解工具拆解方向a加油螺口扳手+Zb左端蓋+Zc調(diào)整螺栓—+Yd轉(zhuǎn)向臂軸—+Ze轉(zhuǎn)向臂軸油封專用工具-Zf殼體——g螺桿螺母組件—+Xh軸承—+Xi上端蓋—+Xj轉(zhuǎn)向螺桿油封專用工具+X

表2列出了關(guān)鍵零部件的名稱、拆解工具和拆解方向。

根據(jù)拆卸網(wǎng)絡(luò)圖的構(gòu)建規(guī)則可以得到循環(huán)球式轉(zhuǎn)向機拆卸路徑的網(wǎng)絡(luò)圖如圖3所示。

圖3 循環(huán)球式轉(zhuǎn)向機拆卸路徑的網(wǎng)絡(luò)圖

筆者將圖3中的節(jié)點進行編號，其中編號1為轉(zhuǎn)向機總成，編號18為轉(zhuǎn)向機殼體，其他編號為拆卸操作中所有可能存在的零件和部件的狀態(tài)。再將由MTM法算出來的拆卸時間作為權(quán)值賦給相應(yīng)的邊，最終得到轉(zhuǎn)向機的拆卸網(wǎng)絡(luò)圖如圖4所示。

圖4 循環(huán)球式轉(zhuǎn)向機的拆卸網(wǎng)絡(luò)圖

根據(jù)循環(huán)球式轉(zhuǎn)向機的拆卸網(wǎng)絡(luò)圖，可以得到賦權(quán)矩陣D，將其代入改進的Floyd算法Matlab程序，得出一個18×18的path矩陣。Floyd算法給出了任意兩點間的最短路徑，根據(jù)轉(zhuǎn)向機拆卸網(wǎng)絡(luò)圖可知，本文僅需要找出從節(jié)點1到節(jié)點18最短時間及路徑。從Matlab的輸出結(jié)果D18和path矩陣分別截取第一行如表3所示。

從表中可以讀出：矩陣D第1行18列元素為54，即拆卸路徑最短的耗時為54 s；在path矩陣中，從終點反推路徑，即先找到P[1,18]為16，表明1-18最短路徑為1-16-18，接下來找P[1,16]為14，表明最短路徑為1-14-16-18，依次類推，可以得出完整的最優(yōu)拆卸路徑為1-2-5-6-7-9-12-14-16-18。

對應(yīng)轉(zhuǎn)向機，該路徑表明在拆卸時首先應(yīng)該擰下加油螺口(a)，再將側(cè)蓋和轉(zhuǎn)向臂軸總成一起從殼體中拆出來，取出和左端蓋連在一起的調(diào)整螺栓，得到轉(zhuǎn)向臂軸(d)，然后將調(diào)整螺栓(b)和左端蓋(c)分離。將轉(zhuǎn)向機整體轉(zhuǎn)90°，拆轉(zhuǎn)向螺桿油封(j)，由于拆除油封需要專門的工具，繼續(xù)拆轉(zhuǎn)向臂軸油封(e)。接下來按順序依次拆除上端蓋(i)，軸承(h)以及螺桿螺母組件(g)，最后剩下轉(zhuǎn)向機殼體(f)，拆解完畢。

通過在程序中設(shè)計斷點和計時可以比較幾種算法，具體結(jié)果如表4所示。

在針對轉(zhuǎn)向機的拆卸規(guī)劃中，幾種算法計算結(jié)果相同，能得到相同的最短拆卸時間和優(yōu)化序列。相比原始Floyd算法，兩種改進后的算法復(fù)雜度降低，循環(huán)次數(shù)減少。第一種改進算法運行速度更快，但用Matlab程序?qū)崿F(xiàn)時，難以追蹤路徑；第二種改進的主要迭代思想并沒有改變，是通過先判斷后計算的方法，改進的力度有限，尤其是當網(wǎng)絡(luò)圖節(jié)點較多、即矩陣較大時。而融合后的新算法綜合了兩種改進算法的優(yōu)點，循環(huán)次數(shù)和算法復(fù)雜度都有大幅減少，特別是針對節(jié)點較多的零部件進行拆解時，能夠更高效地得到結(jié)果。

表3 輸出結(jié)果部分數(shù)據(jù)

表4 改進算法與初始算法計算結(jié)果對比

4 結(jié)束語

本文選擇循環(huán)球式轉(zhuǎn)向機作為研究對象，通過網(wǎng)絡(luò)圖建立拆解信息模型，只需一條路徑就能將結(jié)構(gòu)完全拆解；基于MTM作業(yè)時間衡量，比傳統(tǒng)經(jīng)驗?zāi)芨鼫蚀_地算出每個動作所需時間。在比較兩種改進Floyd算法計算效率和運用局限性的基礎(chǔ)上，融合兩種算法的改進思想，再運用融合改進后的Floyd算法快速準確地得到了轉(zhuǎn)向機拆卸時間最短的拆卸序列。

該方法可推廣用于零件數(shù)為10～40的其他零部件的拆卸規(guī)劃。但對于發(fā)動機、變速箱這一類零件數(shù)較多結(jié)構(gòu)復(fù)雜的零部件，需將整體根據(jù)產(chǎn)品結(jié)構(gòu)模型先拆分為子系統(tǒng)，再對各子系統(tǒng)運用該方法。