基于改進Floyd算法的轉向機拆卸序列研究*

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

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

0 引 言

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

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

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

1 轉向機拆卸網絡圖的構建

1.1 轉向機結構特征

循環球式轉向機的結構圖如圖1所示。

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

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

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

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

1.2 拆卸網絡圖構建規則

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

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

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

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

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

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

這里以其中一步拆卸操作—從轉向機殼體上取下加油螺口為例進行分析，其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算法是用于求解加權網絡最短問題的經典算法，其核心是一種逐步逼近的思想[14]?；静襟E如下：

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

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

(1)

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

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

2.2 改進Floyd算法分析

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

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

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

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

Input：

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

Output：

規劃矩陣：：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 算例分析

本文以某型循環球式轉向機為例來驗證本算法的可行性與有效性，其結構圖如圖2所示。

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

轉向機零部件的信息表如表2所示。

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

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

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

根據拆卸網絡圖的構建規則可以得到循環球式轉向機拆卸路徑的網絡圖如圖3所示。

圖3 循環球式轉向機拆卸路徑的網絡圖

筆者將圖3中的節點進行編號，其中編號1為轉向機總成，編號18為轉向機殼體，其他編號為拆卸操作中所有可能存在的零件和部件的狀態。再將由MTM法算出來的拆卸時間作為權值賦給相應的邊，最終得到轉向機的拆卸網絡圖如圖4所示。

圖4 循環球式轉向機的拆卸網絡圖

根據循環球式轉向機的拆卸網絡圖，可以得到賦權矩陣D，將其代入改進的Floyd算法Matlab程序，得出一個18×18的path矩陣。Floyd算法給出了任意兩點間的最短路徑，根據轉向機拆卸網絡圖可知，本文僅需要找出從節點1到節點18最短時間及路徑。從Matlab的輸出結果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，依次類推，可以得出完整的最優拆卸路徑為1-2-5-6-7-9-12-14-16-18。

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

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

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

表3 輸出結果部分數據

表4 改進算法與初始算法計算結果對比

4 結束語

本文選擇循環球式轉向機作為研究對象，通過網絡圖建立拆解信息模型，只需一條路徑就能將結構完全拆解；基于MTM作業時間衡量，比傳統經驗能更準確地算出每個動作所需時間。在比較兩種改進Floyd算法計算效率和運用局限性的基礎上，融合兩種算法的改進思想，再運用融合改進后的Floyd算法快速準確地得到了轉向機拆卸時間最短的拆卸序列。

該方法可推廣用于零件數為10～40的其他零部件的拆卸規劃。但對于發動機、變速箱這一類零件數較多結構復雜的零部件，需將整體根據產品結構模型先拆分為子系統，再對各子系統運用該方法。