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

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

前言

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

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

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

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

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

f=m-n+2

(1)

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

2 行星傳動(dòng)方案圖模型的建立

對(duì)于任意形式的行星傳動(dòng)方案，按照如下步驟來建立方案的圖模型。

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

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

2.2 行星排的圖模型

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

2.3 制動(dòng)器和離合器的圖模型

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

2.4 元件之間的連接

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

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

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

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

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

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

表1 同名元件的連接形式

對(duì)于第1種變速器布置形式：

(2)

對(duì)于第2種變速器布置形式：

(3)

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

4.1 圖模型的預(yù)處理

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

4.2 圖模型平面性檢測(cè)算法

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

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

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

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

4.3 平面性檢測(cè)算法的驗(yàn)證

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

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

5 結(jié)論

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

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

參考文獻(xiàn)

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

[2] 戴一奇,胡冠章,陳衛(wèi).圖論與代數(shù)結(jié)構(gòu)[M].北京:清華大學(xué)出版社,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] 李宏才,閆清東,李慎龍.行星傳動(dòng)方案結(jié)構(gòu)幾何矛盾圖論判別方法[J].北京理工大學(xué)學(xué)報(bào),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] 任明琪.行星變速箱綜合簡(jiǎn)圖幾何相容性的判別[J].兵工學(xué)報(bào)(坦克裝甲車與發(fā)動(dòng)機(jī)分冊(cè)),1999,73(1):39-43.