馬明月，劉艷芳，徐向陽，張博文

(北京航空航天大學交通科學與工程學院，北京 100191)

前言

行星傳動方案因具備體積小、承載大和易于實現(xiàn)液壓控制的優(yōu)點而廣泛應用于液力自動變速器(AT)。隨著制造工藝和控制技術(shù)的發(fā)展，變速器市場上出現(xiàn)了越來越多的結(jié)構(gòu)更為復雜的行星傳動方案。對于復雜行星傳動方案的結(jié)構(gòu)設計，僅僅依靠設計人員的經(jīng)驗來設計結(jié)構(gòu)方案的傳統(tǒng)方法難以獲得最佳傳動方案，因此必須實現(xiàn)行星傳動方案結(jié)構(gòu)設計的程序化。

機械干涉檢測是行星傳動方案結(jié)構(gòu)設計的關鍵問題之一，是基于圖的平面性檢測來實現(xiàn)的。圖的平面性檢測一直是圖論的熱點研究方向之一，可用于解決許多實際問題，如單面印刷電路板和集成電路的布線問題[1]。常用的平面性檢測算法包括文獻[2]中提出的D.M.P.算法，文獻[3]中提出的Hopcroft-Tarjan算法和文獻[4]中提出的邊嵌入算法。其中，D.M.P.算法在平面性檢測過程不必尋找Kuratowski子圖，可以根據(jù)需求來修改初始回路和嵌入路徑，在實際問題中得到廣泛應用。目前，針對行星傳動方案機械干涉檢測問題，國內(nèi)外學者已完成很多有價值的研究工作[5-7]。研究工作主要包括圖模型的建立和圖模型平面性檢測算法的實現(xiàn)，但檢測效率低，難于實現(xiàn)大規(guī)模的方案檢測。本文中結(jié)合圖論相關知識建立了行星傳動方案各主要元件的圖模型，給出同名元件之間的不同連接方式和行星傳動方案圖模型的建立方法。融合D.M.P.算法和深度優(yōu)先搜索算法，提出并實現(xiàn)了適用于判斷行星傳動方案簡圖數(shù)學模型平面性的檢測算法。

1 平面圖的基本定理[2]

若能把圖G畫在一個平面上，使任何兩條邊都不相交，就稱G為可嵌入平面，或稱G是可平面圖。可平面圖在平面上的一個嵌入稱為平面圖。例如圖1(b)是圖1(a)的一個平面嵌入。

可嵌入平面圖G的平面嵌入把平面分成若干個連通的閉區(qū)域，每個閉區(qū)域叫做G的一個面，用f來表示G的面的數(shù)目。歐拉定理表明，若G是平面連通圖，則G的面的數(shù)目為

f=m-n+2

(1)

式中：m為圖G的邊數(shù)；n為圖G的頂點數(shù)。

2 行星傳動方案圖模型的建立

對于任意形式的行星傳動方案，按照如下步驟來建立方案的圖模型。

2.1 殼體、輸入軸和輸出軸的圖模型

液力自動變速器有兩種輸入輸出軸的布置形式。第1種布置形式是輸入軸和輸出軸沿同一軸線布置，如圖2(a)所示。第2種布置形式是輸入軸和輸出軸沿平行軸線布置，如圖1(b)所示。針對這兩種布置形式分別給出殼體、輸入軸及輸出軸的圖模型1和圖模型2，如圖1(c)和圖1(d)所示。其中點G1、G2表示殼體，L1表示輸入軸，L2表示輸出軸。

2.2 行星排的圖模型

單行星排的圖模型是將太陽輪S、齒圈R、行星架A分別抽象為點，并在太陽輪與行星架、齒圈與行星架之間分別添加一條邊e1、e2，如圖3所示。復合式行星排的圖模型可表示為兩個單行星排圖模型的組合。

2.3 制動器和離合器的圖模型

對于非換聯(lián)式行星傳動方案，制動器與離合器可分別抽象為兩度點B和C，其中離合器僅與行星排的基本元件相連。對于換聯(lián)式行星傳動方案，離合器的一端與輸入軸或輸出軸相連。設與制動器和離合器相連的元件分別用點v1、v2、v3和v4表示，它們之間的連接用邊e1、e2、e3和e4表示，則制動器和離合器的圖模型分別如圖4(a)和圖4(b)所示。

2.4 元件之間的連接

行星傳動方案元件之間的連接包括行星排的基本元件經(jīng)輔助構(gòu)件或離合器的連接、殼體與行星排的基本元件經(jīng)制動器的連接及輸入輸出軸與行星排的基本元件經(jīng)輔助構(gòu)件或離合器的連接。將相連元件之間連接映射為圖模型中的邊，可得到一系列行星傳動方案圖模型。例如：對于如圖5(a)所示的行星傳動方案簡圖，該方案的圖模型之一如圖5(b)所示。

3 同名元件的連接形式分析

行星傳動方案中直接相連的元件(不包括離合器和制動器)稱為同名元件。在建立行星傳動方案圖模型時，由于同名元件的存在使得行星傳動方案存在多個圖模型，對于同一行星傳動方案而言，不同的圖模型的平面性也可能是不同的，當存在一個可平面的圖模型時，該方案即在結(jié)構(gòu)上是可以實現(xiàn)的。

N個同名元件呈鏈狀連接的圖模型共有N-1條邊和N!/2種連接形式。當同名元件個數(shù)為2時，同名元件之間僅有1條邊和1種連接形式。當同名元件個數(shù)N≥3時，同名元件之間的鏈狀連接方式呈現(xiàn)多樣性。表1中給出了3個同名元件的3種連接形式和4個同名元件的12種連接形式。其中，圖中的頂點v1、v2、v3和v4表示同名元件，邊e1、e2、e3、e4、e5和e6表示同名元件之間的連接。

對于第1種布置形式的制動器與N個同名元件之間連接的圖模型數(shù)目為N，對于第2種布置形式的制動器與N個同名元件之間連接的圖模型數(shù)目為2N。與離合器相連的兩組同名元件的數(shù)目分別為M和N，離合器與同名元件之間連接的圖模型數(shù)目為M×N。

設行星傳動方案的同名元件數(shù)目分別為N1,N2,…,Nt，制動器相連的同名元件的數(shù)目分別為M1,M2,…,Ms，離合器相連的同名元件的數(shù)目分別為L1,L2,…,Lr，則行星傳動方案圖模型的數(shù)目X為

表1 同名元件的連接形式

對于第1種變速器布置形式：

(2)

對于第2種變速器布置形式：

(3)

4 平面性檢測算法的實現(xiàn)

4.1 圖模型的預處理

根據(jù)圖論的相關知識，在檢測圖形的平面性前，應預先檢測被測圖形是否為連通圖，圖形中是否存在自環(huán)和兩度點。對于行星傳動方案而言，其圖模型必為連通圖且不存在自環(huán)，因此，在執(zhí)行平面性檢測算法前，只須去除圖模型中的兩度點。以圖5(b)所示的圖模型為例，經(jīng)預處理后的圖模型和鄰接矩陣如圖6所示。

4.2 圖模型平面性檢測算法

針對行星傳動方案的圖模型，將D.M.P.算法做了相應調(diào)整，具體描述如下：

(2) 求G關于Gi的片D；

(4) 采用DFS算法對將要嵌入的片進行搜索，找到路徑Pi?D，且Pi的兩端點為Gi的節(jié)點；

(6) 設圖G的頂點數(shù)為n，邊數(shù)為m，如果面數(shù)f=m-n+2，則圖G為可平面圖，返回結(jié)果并退出程序；否則轉(zhuǎn)(2)，繼續(xù)循環(huán)。

4.3 平面性檢測算法的驗證

采用M語言編寫了行星傳動方案圖模型綜合算法和圖模型平面性檢測算法，并針對大量典型算例驗證對該算法進行測試，證實了算法的準確性和可靠性。圖7為對圖6(a)所示的簡化圖模型進行平面性檢測時路徑嵌入過程的演示。測試結(jié)果顯示該圖模型為可平面圖，與實際情況一致，證實了平面性檢測算法的有效性。

在確定片和嵌入路徑時，采用DFS算法預先標定圖模型各頂點的位置，避免了盲目遍歷式搜索，提高了整體運行效率。此外，選取了固定的初始回路和初始嵌入平面，也進一步簡化了檢測算法。采用上述平面性檢測算法對2 006組3個行星排6個換擋元件的行星傳動方案進行檢測，其中具有可平面性的方案數(shù)為399，總的運行時間為170.51s。由于不同方案其同結(jié)構(gòu)方案數(shù)存在差異，因此單個方案的檢測時間是不同的，用于檢測的2 006組行星傳動方案的獨立運行時間曲線如圖8所示。與文獻[10]相比，單個方案的平均檢測時間由897.1ms降至34.1ms，檢測算法在運行效率上有了明顯提高，適用于大規(guī)模方案的平面性檢測。

5 結(jié)論

應用平面圖理論的相關知識，分別給出了行星傳動方案中各元件圖模型的定義，實現(xiàn)了方案簡圖與圖模型的轉(zhuǎn)化。綜合了多個同名元件鏈狀連接的具體形式，得到一個更為全面的行星傳動方案圖模型數(shù)目的計算公式，并提出了一種系統(tǒng)的用于行星傳動方案圖模型的綜合方法，該方法是借助圖模型的鄰接矩陣實現(xiàn)的，非常直觀且不易出錯。

借助圖的鄰接矩陣對圖的片進行定義并采用深度優(yōu)先搜索算法的思想構(gòu)造嵌入路徑，采用M語言編寫了適用于行星傳動方案圖模型的D.M.P.算法。以多組平面圖和非平面為測試對象進行平面性檢測，結(jié)果準確。通過程序運行中保存的嵌入路徑，還原了可平面圖的整個平面嵌入過程，得到了該圖形的一個平面嵌入，從而再次證明平面性算法的準確性。

參考文獻

[1] 殷劍宏,吳開亞.圖論及其算法[M].合肥:中國科學技術(shù)大學出版社,2004:130-134.

[2] 戴一奇,胡冠章,陳衛(wèi).圖論與代數(shù)結(jié)構(gòu)[M].北京:清華大學出版社,1995:69-79.

[3]HopcroftJ,TarjanR.EfficientPlanarityTesting[J].JournaloftheAssociationforComputingMachinery,1974,21(4):549-568.

[4]BoyerJM,MyrvoldWJ.OntheCuttingEdge:SimplifiedO(n)PlanaritybyEdgeAddition[J].JournalofGraphAlgorithmsandApplications,2004,8(3):241-273.

[5]HsuC,HuangR.SystematicDesignofSix-SpeedAutomaticTransmissionswithanEight-LinkTwo-DOFRavigneauxGearMechanism[J].JournalofMechanicalDesign,2009,131(1).

[6]ChatterjeeG.EnumerationandAutomaticSketchingofEpycyclic-typeAutomaticTransmissionGearTrain[D].Maryland:SUniversityofMaryland,1993.

[7] 李宏才,閆清東,李慎龍.行星傳動方案結(jié)構(gòu)幾何矛盾圖論判別方法[J].北京理工大學學報,2010,30(9):1047-1050,1064.

[8]SchererH.ZF6-SpeedAutomaticTransmissionforPassengerCars[C].SAEPaper2003-01-0596.

[9]NaojiKatouTT,KazumasaTsukamoto,MasahiroHayabuchi,etal.AISINAWNewSix-SpeedAutomaticTransmissionforFWDVehicles[C].SAEPaper2004-01-0651.

[10] 任明琪.行星變速箱綜合簡圖幾何相容性的判別[J].兵工學報(坦克裝甲車與發(fā)動機分冊),1999,73(1):39-43.