基于啟發(fā)式割集法的桁架裝配序列規(guī)劃研究

姜沖，張凱，于淼

基于啟發(fā)式割集法的桁架裝配序列規(guī)劃研究

姜沖，張凱*，于淼

（四川大學(xué) 機(jī)械工程學(xué)院，四川 成都 610065）

目前關(guān)于桁架類(lèi)產(chǎn)品的設(shè)計(jì)研究較少涉及其安裝過(guò)程，傳統(tǒng)的基于經(jīng)驗(yàn)的安裝模式很可能因?yàn)榘惭b不得當(dāng)，導(dǎo)致影響后續(xù)一系列同結(jié)構(gòu)模塊的安裝質(zhì)量，因此需要針對(duì)硬橫跨的安裝序列問(wèn)題，優(yōu)化安裝流程，提高其安裝效率和質(zhì)量可靠性。本文研究了桁架類(lèi)產(chǎn)品安裝問(wèn)題，提出了一種基于割集算法的啟發(fā)式桁架裝配序列規(guī)劃方法。通過(guò)分析模型建立裝配關(guān)聯(lián)矩陣，簡(jiǎn)化裝配關(guān)聯(lián)矩陣減少安裝序列搜索空間。使用基于啟發(fā)式算法的割集發(fā)對(duì)簡(jiǎn)化之后裝配關(guān)聯(lián)圖生成裝配序列。最后使用單跨硬橫跨模型為例生成安裝序列，為硬橫跨裝配工藝設(shè)計(jì)提供了新的參考。

桁架；虛擬裝配；裝配序列規(guī)劃；割集算法；啟發(fā)式方法

裝配是產(chǎn)品制造過(guò)程中最重要的一步，其在整個(gè)產(chǎn)品的制造過(guò)程中是最后一步，裝配質(zhì)量的好壞直接決定了產(chǎn)品最終的成型效果，早在1991年，Womack等人[1]就通過(guò)觀察提出，裝配耗時(shí)占據(jù)了產(chǎn)品制造總用時(shí)的20%～30%，而裝配成本占總成本的40%。裝配序列規(guī)劃在裝配流程中占有極其重要的地位，對(duì)裝配質(zhì)量起著決定性的作用。

對(duì)產(chǎn)品裝配質(zhì)量和產(chǎn)品裝配周期的控制，都對(duì)設(shè)計(jì)人員提出了較大的考驗(yàn)，對(duì)其裝配經(jīng)驗(yàn)和設(shè)計(jì)成熟度有很高的要求，而且最后裝配質(zhì)量和時(shí)間成本往往因人而異，在裝配設(shè)計(jì)上的標(biāo)準(zhǔn)性和規(guī)范性很難得到保障。裝配序列規(guī)劃（Assembly Sequence Planning，ASP）問(wèn)題作為虛擬裝配技術(shù)的關(guān)鍵一部分，設(shè)計(jì)人員可以在虛擬環(huán)境中進(jìn)行編排規(guī)劃，由計(jì)算機(jī)自動(dòng)輸出結(jié)果，能夠極大程度緩解裝配序列規(guī)劃對(duì)人的依賴(lài)程度，完成裝配的標(biāo)準(zhǔn)化規(guī)范化流程，減少因錯(cuò)誤的裝配規(guī)劃導(dǎo)致的成本上升。

在ASP優(yōu)化中，首要且最重要的步驟是建立并使用一種表達(dá)方法，以對(duì)裝配問(wèn)題進(jìn)行建模。裝配規(guī)劃的有效性很大程度上取決于裝配問(wèn)題的建模方式。通常情況下，ASP問(wèn)題表達(dá)形式分為三類(lèi)：基于連接方式的建模、基于裝配任務(wù)的建模以及基于零件的建模[2]。這些類(lèi)別的劃分都是根據(jù)其表示組裝問(wèn)題時(shí)的最小元素來(lái)定義的。其中超過(guò)半數(shù)的表達(dá)方式是基于零件建模，這很大程度上是因?yàn)檠芯咳藛T試圖模擬出組件中存在的最小裝配體。

針對(duì)裝配序列規(guī)劃優(yōu)化的研究主要有兩個(gè)方向，一是傳統(tǒng)上比較成熟的推理法，比如優(yōu)先約束法[3]、割集法[4]等，二是基于元啟發(fā)式方法的算法，比如遺傳算法[5]、粒子群優(yōu)化[6]、蟻群算法[7]、人工神經(jīng)網(wǎng)絡(luò)[8]等。上述規(guī)劃優(yōu)化算法都取得了良好的進(jìn)展，但都是在全局進(jìn)行序列搜索，在非可行解空間浪費(fèi)了過(guò)多算力。

桁架結(jié)構(gòu)作為一種在大型橋梁、機(jī)場(chǎng)穹頂以及輸電線路中擁有廣泛應(yīng)用的結(jié)構(gòu)，隨著國(guó)內(nèi)高鐵建設(shè)的快速展開(kāi)和布局，電氣化鐵路需要在站場(chǎng)中布置大量硬橫跨來(lái)布設(shè)高鐵動(dòng)車(chē)所使用的接觸網(wǎng)。特別是對(duì)于較大的樞紐場(chǎng)站，需要更復(fù)雜的硬橫跨，因此對(duì)硬橫跨的安裝流程提出了更高的要求，一旦裝配時(shí)出現(xiàn)不得當(dāng)安裝方式，將會(huì)出現(xiàn)嚴(yán)重的位移應(yīng)力集中，影響硬橫跨的長(zhǎng)期使用。

本文提出了一種利用啟發(fā)式算法與余樹(shù)算法的改進(jìn)式割集法來(lái)獲得裝配序列。減少了規(guī)劃過(guò)程中所需同時(shí)考慮的零部件數(shù)量，提高了規(guī)劃效率，避免了因同時(shí)計(jì)算的零件數(shù)量過(guò)多可能導(dǎo)致潛在的組合爆炸的情況。最后使用了單跨硬橫跨模型驗(yàn)證了此方法。

1 系統(tǒng)設(shè)計(jì)

基于割集法的裝配序列規(guī)劃的生成流程主要如圖1所示，首先需要將裝配模型依據(jù)其連接關(guān)系，對(duì)零件分組編號(hào)使用無(wú)向圖生成裝配關(guān)聯(lián)圖，接下來(lái)聚類(lèi)簡(jiǎn)化裝配模型的表達(dá)，利用啟發(fā)式規(guī)則分析層次關(guān)系確定層次關(guān)系建立割集，最后使用余樹(shù)算法變換生成樹(shù)，得到裝配序列。

圖1 裝配序列規(guī)劃的生成流程

1.1 裝配模型表達(dá)

在此方法中，使用二維拓?fù)溲b配關(guān)聯(lián)圖來(lái)表示產(chǎn)品中零件的連接關(guān)系，表示形式為：

式中：為裝配體中所有零件的集合；為零件之間的所有連接的集合。

為了得到裝配關(guān)聯(lián)圖，還需要先將模型的零件進(jìn)行標(biāo)號(hào)。圖2為某裝配體的表示方式。已裝配產(chǎn)品的拆解可以通過(guò)將關(guān)聯(lián)圖劃分為子圖的形式來(lái)表示，每一個(gè)子圖都表示產(chǎn)品中的一個(gè)零件或者子裝配體。分割圖的弧的集合稱(chēng)為割集，用S表示。將某由五個(gè)零件組成的裝配體拆分為兩個(gè)子裝配體，可以通過(guò)圖2中表示為割集1＝{,,}來(lái)體現(xiàn)的。通過(guò)劃分裝配體并分析計(jì)算其基本割集，就可以得到其拆卸序列，如果將拆卸序列反向，就得到其裝配序列。因?yàn)樵谘b配過(guò)程中，同時(shí)需要安裝三個(gè)或者更多零件的情況很罕見(jiàn)，所以使用基本割集將模型分割至單個(gè)零件以及僅含有兩個(gè)零件構(gòu)成的子裝配體為止。

圖2 裝配關(guān)聯(lián)圖及其分解示意

1.2 簡(jiǎn)化裝配模型

Baldwin等[9]通過(guò)遍歷計(jì)算了裝配體中的所有基本割集（裝配體割集），來(lái)獲取生成裝配體中所有裝配序列，以尋找其中的最優(yōu)裝配序列。判斷評(píng)價(jià)每一個(gè)裝配序列來(lái)尋找最優(yōu)序列，會(huì)浪費(fèi)大量的計(jì)算時(shí)間，因?yàn)樵谕粫r(shí)間針對(duì)存在大量零件的復(fù)雜模型，其所需判斷裝配序列的數(shù)量會(huì)根據(jù)零件數(shù)量的增多呈指數(shù)級(jí)增長(zhǎng)，導(dǎo)致搜索空間過(guò)大[10]。因此，有必要簡(jiǎn)化復(fù)雜模型的裝配關(guān)聯(lián)圖、縮小需要同時(shí)進(jìn)行計(jì)算的搜索空間，來(lái)達(dá)到減小計(jì)算量的目的。

單純簡(jiǎn)化裝配模型同樣存在問(wèn)題，并非每一次都能找到最優(yōu)解。如圖3所示，在縮小搜索空間的同時(shí)，很有可能同時(shí)包括了可行解的空間。最嚴(yán)重的情況是減小的搜索空間全部在可行解范圍之內(nèi)，這樣很可能無(wú)法獲得最佳的裝配序列，導(dǎo)致此方法無(wú)效。減小的搜索空間不包含可行解空間的情況是一種理想情況，不是每一次都會(huì)出現(xiàn)。

圖3 搜索空間示意圖

因此，針對(duì)桁架產(chǎn)品的結(jié)構(gòu)特點(diǎn)，提出了一種方法簡(jiǎn)化桁架產(chǎn)品以達(dá)到減小搜索空間的結(jié)果，而不影響其可行解空間：

（1）根據(jù)自上而下的方法分析其裝配層次結(jié)構(gòu)，得到若干個(gè)子裝配體，子裝配體中連接關(guān)系簡(jiǎn)單、易于規(guī)劃，從而將整個(gè)模型的裝配問(wèn)題轉(zhuǎn)化為子裝配體之間的裝配問(wèn)題，從而達(dá)到簡(jiǎn)化整體模型的結(jié)果。

（2）將功能和尺寸都相同的連續(xù)布置的連桿聚類(lèi)顯示，將其表示成為連接圖中的一個(gè)節(jié)點(diǎn)，以減少所需計(jì)算的節(jié)點(diǎn)。

2 使用啟發(fā)式方法生成割集

使用啟發(fā)式方法的流程如圖4所示，主要分為三步。

2.1 啟發(fā)式規(guī)則圖

在這一步中，需要使用啟發(fā)式方法生成規(guī)則圖。在圖4中，將之前連接圖中零件之間的聯(lián)結(jié)關(guān)系視為節(jié)點(diǎn)，被指向的連接必須優(yōu)先完成，而指向同一連接同等級(jí)的連接則不分先后。因?yàn)樵趯?shí)際的產(chǎn)品中零件的裝配過(guò)程中，某些連接總是需要優(yōu)先于其他連接的先行完成；反之，在拆卸過(guò)程需要更早地解除與主體的連接。

圖4 啟發(fā)式方法流程圖

通過(guò)啟發(fā)式規(guī)則在產(chǎn)品的CAD數(shù)據(jù)中生成針對(duì)安裝的規(guī)則圖。圖5顯示了使用啟發(fā)式規(guī)則在連接法蘭中簡(jiǎn)化的螺栓連接生成規(guī)則圖的示例。

圖5 螺栓連接規(guī)則圖

2.2 基于層次結(jié)構(gòu)的權(quán)重分配

在上一步中得到了基于啟發(fā)式規(guī)則的優(yōu)先圖，每一個(gè)啟發(fā)式優(yōu)先圖都是應(yīng)用了啟發(fā)式規(guī)則而產(chǎn)生的。接下來(lái)，根據(jù)得到的優(yōu)先圖，建立其層次結(jié)構(gòu)模型。如圖6所示，依據(jù)啟發(fā)式規(guī)則圖建立了裝配體的連接優(yōu)先圖，以此來(lái)得到其層級(jí)結(jié)構(gòu)圖。每個(gè)箭頭指向的連接相對(duì)具有更高的層級(jí)，而層級(jí)越高的連接就需要在裝配中越早連接。

依據(jù)連接的層級(jí)結(jié)構(gòu)模型，可以為每一層中的連接關(guān)系賦予權(quán)重，將權(quán)重值賦予連接關(guān)系圖，將圖2中的每一條連接賦予權(quán)重，得到圖7。使用w來(lái)表示圖中每一條邊的權(quán)重，比如w＝1。權(quán)重值越大的連接需要在安裝過(guò)程中越早出現(xiàn)，反之則需要在安裝過(guò)程的更后面出現(xiàn)。

圖6 優(yōu)先級(jí)圖轉(zhuǎn)換層次結(jié)構(gòu)圖

圖7 連接權(quán)重賦值示意

2.3 生成樹(shù)與基本割集

對(duì)連接關(guān)系賦權(quán)重的意義在于，可以依據(jù)安裝過(guò)程中優(yōu)先順序的不同，對(duì)割集的質(zhì)量進(jìn)行評(píng)估。因此建立了評(píng)價(jià)函數(shù)Q對(duì)不同割集S進(jìn)行評(píng)價(jià)，其計(jì)算公式為：

式中：w為割集S中所包含的線段的權(quán)重值；為權(quán)重值的平均值。

計(jì)算得到Q值越小，就認(rèn)為其割集的質(zhì)量越好，所以對(duì)于圖7，其最佳割集為＝{,,}。

生成樹(shù)是指在圖中不存在環(huán)路且能遍歷圖中所有節(jié)點(diǎn)的最少邊的圖。獲取所需要的生成樹(shù)來(lái)得到連接圖中的基本割集，用以生成裝配序列。如圖8所示，生成樹(shù)可表示為＝{,,,}，其基本割集S有四個(gè)，可計(jì)算出它們每一個(gè)割集的質(zhì)量Q。

接下來(lái)根據(jù)比內(nèi)－柯西定理，通過(guò)計(jì)算對(duì)應(yīng)關(guān)聯(lián)圖的關(guān)聯(lián)矩陣的子矩陣B與其子矩陣轉(zhuǎn)置BT乘積的秩，就可以求解出圖2連接圖所對(duì)應(yīng)的生成樹(shù)的總數(shù)，為det（BT）＝12個(gè)。如果對(duì)于每一顆生成樹(shù)都進(jìn)行基本割集計(jì)算，是浪費(fèi)時(shí)間的，因?yàn)楦鶕?jù)不同圖的復(fù)雜程度，生成樹(shù)的數(shù)量十分巨大。因此使用余樹(shù)算法來(lái)進(jìn)行生成樹(shù)變換，以尋找其最佳生成樹(shù)，從而減少計(jì)算量。

圖8 生成樹(shù)示意圖

定義余樹(shù)為＝(－)，其意義為在完整的連接圖中去除某一生成樹(shù)之后剩下的弦的集合。使用余樹(shù)算法進(jìn)行生成樹(shù)變換可獲得其最佳生成樹(shù)，其算法過(guò)程如圖9所示。

圖9 余數(shù)算法流程圖

通過(guò)使用圖9的算法，就可得到連接圖的良好基本割集，從而得到最佳裝配序列。使用余數(shù)算法進(jìn)行生成樹(shù)變換的過(guò)程如圖10所示。

基于最后變換得到的生成樹(shù)，就可以通過(guò)值，按從小到大的順序，將對(duì)應(yīng)生成樹(shù)的基本割集進(jìn)行排序，依據(jù)對(duì)應(yīng)基本割集在生成樹(shù)中排出的零件，就可以得到對(duì)應(yīng)裝配體的最佳裝配序列。圖2所對(duì)應(yīng)的裝配體，其最佳裝配序列為2－3－4－1－5或者2－3－4－5－1。

3 應(yīng)用實(shí)例

接下來(lái)通過(guò)某型硬橫跨橫梁邊段三維模型來(lái)驗(yàn)證上述方法，其結(jié)構(gòu)如圖11所示，結(jié)構(gòu)功能相同的零件作為同一零件表示，連接圖如圖12所示。

根據(jù)啟發(fā)式割集方法和余樹(shù)算法計(jì)算其割集之后，即可得到硬橫跨橫梁邊段的最優(yōu)裝配序列為：1－4－2－5－7－（6.1, 6.2）－3。

圖10 余算法執(zhí)行過(guò)程

4 結(jié)論

本文提出了一種基于啟發(fā)式割集法的裝配序列的生成方法，通過(guò)建立割集分離提取產(chǎn)品中的子裝配體或者零件，以此來(lái)得到產(chǎn)品的裝配序列。該規(guī)劃方法的特點(diǎn)是通過(guò)使用啟發(fā)式方法和余數(shù)算法來(lái)對(duì)關(guān)聯(lián)圖進(jìn)行生成樹(shù)變換，以獲取新的良好基本割集，進(jìn)而生成裝配序列。實(shí)例表明，該方法可以得到良好的裝配序列。

圖11 硬橫跨邊段三維模型示意圖

圖12 硬橫跨橫梁邊段裝配關(guān)聯(lián)圖

[1]Womack J P，Jones D T，Roos D. The Machine That Changed the World[M]. Scribner，1991.

[2] Abdullah M A，Ab Rashid M F F，Ghazalli Z. Optimization of Assembly Sequence Planning Using Soft Computing Approaches: A Review[J]. Archives of Computational Methods in Engineering. 2019，26（2）：461-474.

[3]夏平均，姚英學(xué)，劉江省，等. 基于虛擬現(xiàn)實(shí)和仿生算法的裝配序列優(yōu)化[J]. 機(jī)械工程學(xué)報(bào)，2007，43（4）：44-52.

[4]付宜利，田立中，謝龍，等. 基于有向割集分解的裝配序列生成方法[J]. 機(jī)械工程學(xué)報(bào)，2003，39（6）：58-62.

[5]At M，Csp R. Implementation of genetic algorithm to optimize the assembly sequence plan based on penalty function[J]. ARPN J Eng Appl Sci.，2014，9（4）：453-456.

[6]吳永明，戴隆州，李少波，等. 基于改進(jìn)粒子群優(yōu)化算法的混流裝配線演進(jìn)平衡[J]. 計(jì)算機(jī)集成制造系統(tǒng)，2017，23（4）：781-790.

[7]劉曉陽(yáng)，劉恩福，靳江艷. 基于蟻群算法的異步并行裝配序列規(guī)劃方法[J]. 機(jī)械工程學(xué)報(bào)，2019，55（9）：107-119.

[8]張晶，崔漢國(guó)，朱石堅(jiān). 基于人工神經(jīng)網(wǎng)絡(luò)的裝配序列規(guī)劃方法研究[J]. 武漢理工大學(xué)學(xué)報(bào)（交通科學(xué)與工程版），2010，34（5）：1053-1056.

[9]Baldwin D，Abell T，Lui M. An Integrated Computer Aid for Generating and Evaluating Assembly Sequences for Mechanical Products[J]. IEEE TRANSACTIONS ON ROBOTICS AND AUTOMATION，1991，7（1）：78-94.

[10]De Fazio T，Whitney D. Simplified generation of all mechanical assembly sequences[J]. IEEE Journal on Robotics and Automation，1987，3（6）：640-658.

Research on Truss Assembly Sequence Planning Based on Heuristic Cut Set Method

JIANG Chong，ZHANG Kai，YU Miao

( School of Mechanical Engineering,Sichuan University, Chengdu 610065,China)

At present, the design and research of truss products seldom involves its installation process. The traditional experience-based installation mode is likely to subsequently affect the installation quality of a series of modules with the same structure due to improper installation. Therefore, the installation process needs to be optimized to improve the efficiency and reliability. In this paper, a heuristic truss assembly sequence planning method based on cut set algorithm is proposed. The assembly correlation matrix is established by analyzing the model, which simplifies the assembly correlation matrix and reduces the search space of the installation sequence. Cut set method based on heuristic algorithm is used to generate assembly sequences for the assembly association graphs simplified. Finally, a single span portal structure model is used as an example to generate the installation sequence, which provides a new reference for the design of the portal structure assembly process.

truss；virtual assembly；assembly sequence planning；cut set algorithm；heuristic method

TP391.7

A

10.3969/j.issn.1006-0316.2020.05.002

1006－0316 (2020) 05－0012－06

2020－01－16

四川省科技計(jì)劃重點(diǎn)研發(fā)項(xiàng)目（2019YFG0061）；四川大學(xué)自貢市校地科技合作專(zhuān)項(xiàng)資金項(xiàng)目（2018CDZG-5）；賽爾網(wǎng)絡(luò)下一代互聯(lián)網(wǎng)技術(shù)創(chuàng)新項(xiàng)目（NGII20180804）

姜沖（1995－），男，四川成都人，碩士研究生，主要研究方向?yàn)橹悄苤圃臁?通訊作者：張凱（1984－），安徽淮南人，工學(xué)博士，助理研究員，主要研究方向?yàn)橹悄苤圃欤珽-mail：zkscu2005@163.com。