基于啟發式割集法的桁架裝配序列規劃研究

姜沖，張凱，于淼

基于啟發式割集法的桁架裝配序列規劃研究

姜沖，張凱*，于淼

（四川大學 機械工程學院，四川 成都 610065）

目前關于桁架類產品的設計研究較少涉及其安裝過程，傳統的基于經驗的安裝模式很可能因為安裝不得當，導致影響后續一系列同結構模塊的安裝質量，因此需要針對硬橫跨的安裝序列問題，優化安裝流程，提高其安裝效率和質量可靠性。本文研究了桁架類產品安裝問題，提出了一種基于割集算法的啟發式桁架裝配序列規劃方法。通過分析模型建立裝配關聯矩陣，簡化裝配關聯矩陣減少安裝序列搜索空間。使用基于啟發式算法的割集發對簡化之后裝配關聯圖生成裝配序列。最后使用單跨硬橫跨模型為例生成安裝序列，為硬橫跨裝配工藝設計提供了新的參考。

桁架；虛擬裝配；裝配序列規劃；割集算法；啟發式方法

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

對產品裝配質量和產品裝配周期的控制，都對設計人員提出了較大的考驗，對其裝配經驗和設計成熟度有很高的要求，而且最后裝配質量和時間成本往往因人而異，在裝配設計上的標準性和規范性很難得到保障。裝配序列規劃（Assembly Sequence Planning，ASP）問題作為虛擬裝配技術的關鍵一部分，設計人員可以在虛擬環境中進行編排規劃，由計算機自動輸出結果，能夠極大程度緩解裝配序列規劃對人的依賴程度，完成裝配的標準化規范化流程，減少因錯誤的裝配規劃導致的成本上升。

在ASP優化中，首要且最重要的步驟是建立并使用一種表達方法，以對裝配問題進行建模。裝配規劃的有效性很大程度上取決于裝配問題的建模方式。通常情況下，ASP問題表達形式分為三類：基于連接方式的建模、基于裝配任務的建模以及基于零件的建模[2]。這些類別的劃分都是根據其表示組裝問題時的最小元素來定義的。其中超過半數的表達方式是基于零件建模，這很大程度上是因為研究人員試圖模擬出組件中存在的最小裝配體。

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

桁架結構作為一種在大型橋梁、機場穹頂以及輸電線路中擁有廣泛應用的結構，隨著國內高鐵建設的快速展開和布局，電氣化鐵路需要在站場中布置大量硬橫跨來布設高鐵動車所使用的接觸網。特別是對于較大的樞紐場站，需要更復雜的硬橫跨，因此對硬橫跨的安裝流程提出了更高的要求，一旦裝配時出現不得當安裝方式，將會出現嚴重的位移應力集中，影響硬橫跨的長期使用。

本文提出了一種利用啟發式算法與余樹算法的改進式割集法來獲得裝配序列。減少了規劃過程中所需同時考慮的零部件數量，提高了規劃效率，避免了因同時計算的零件數量過多可能導致潛在的組合爆炸的情況。最后使用了單跨硬橫跨模型驗證了此方法。

1 系統設計

基于割集法的裝配序列規劃的生成流程主要如圖1所示，首先需要將裝配模型依據其連接關系，對零件分組編號使用無向圖生成裝配關聯圖，接下來聚類簡化裝配模型的表達，利用啟發式規則分析層次關系確定層次關系建立割集，最后使用余樹算法變換生成樹，得到裝配序列。

圖1 裝配序列規劃的生成流程

1.1 裝配模型表達

在此方法中，使用二維拓撲裝配關聯圖來表示產品中零件的連接關系，表示形式為：

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

為了得到裝配關聯圖，還需要先將模型的零件進行標號。圖2為某裝配體的表示方式。已裝配產品的拆解可以通過將關聯圖劃分為子圖的形式來表示，每一個子圖都表示產品中的一個零件或者子裝配體。分割圖的弧的集合稱為割集，用S表示。將某由五個零件組成的裝配體拆分為兩個子裝配體，可以通過圖2中表示為割集1＝{,,}來體現的。通過劃分裝配體并分析計算其基本割集，就可以得到其拆卸序列，如果將拆卸序列反向，就得到其裝配序列。因為在裝配過程中，同時需要安裝三個或者更多零件的情況很罕見，所以使用基本割集將模型分割至單個零件以及僅含有兩個零件構成的子裝配體為止。

圖2 裝配關聯圖及其分解示意

1.2 簡化裝配模型

Baldwin等[9]通過遍歷計算了裝配體中的所有基本割集（裝配體割集），來獲取生成裝配體中所有裝配序列，以尋找其中的最優裝配序列。判斷評價每一個裝配序列來尋找最優序列，會浪費大量的計算時間，因為在同一時間針對存在大量零件的復雜模型，其所需判斷裝配序列的數量會根據零件數量的增多呈指數級增長，導致搜索空間過大[10]。因此，有必要簡化復雜模型的裝配關聯圖、縮小需要同時進行計算的搜索空間，來達到減小計算量的目的。

單純簡化裝配模型同樣存在問題，并非每一次都能找到最優解。如圖3所示，在縮小搜索空間的同時，很有可能同時包括了可行解的空間。最嚴重的情況是減小的搜索空間全部在可行解范圍之內，這樣很可能無法獲得最佳的裝配序列，導致此方法無效。減小的搜索空間不包含可行解空間的情況是一種理想情況，不是每一次都會出現。

圖3 搜索空間示意圖

因此，針對桁架產品的結構特點，提出了一種方法簡化桁架產品以達到減小搜索空間的結果，而不影響其可行解空間：

（1）根據自上而下的方法分析其裝配層次結構，得到若干個子裝配體，子裝配體中連接關系簡單、易于規劃，從而將整個模型的裝配問題轉化為子裝配體之間的裝配問題，從而達到簡化整體模型的結果。

（2）將功能和尺寸都相同的連續布置的連桿聚類顯示，將其表示成為連接圖中的一個節點，以減少所需計算的節點。

2 使用啟發式方法生成割集

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

2.1 啟發式規則圖

在這一步中，需要使用啟發式方法生成規則圖。在圖4中，將之前連接圖中零件之間的聯結關系視為節點，被指向的連接必須優先完成，而指向同一連接同等級的連接則不分先后。因為在實際的產品中零件的裝配過程中，某些連接總是需要優先于其他連接的先行完成；反之，在拆卸過程需要更早地解除與主體的連接。

圖4 啟發式方法流程圖

通過啟發式規則在產品的CAD數據中生成針對安裝的規則圖。圖5顯示了使用啟發式規則在連接法蘭中簡化的螺栓連接生成規則圖的示例。

圖5 螺栓連接規則圖

2.2 基于層次結構的權重分配

在上一步中得到了基于啟發式規則的優先圖，每一個啟發式優先圖都是應用了啟發式規則而產生的。接下來，根據得到的優先圖，建立其層次結構模型。如圖6所示，依據啟發式規則圖建立了裝配體的連接優先圖，以此來得到其層級結構圖。每個箭頭指向的連接相對具有更高的層級，而層級越高的連接就需要在裝配中越早連接。

依據連接的層級結構模型，可以為每一層中的連接關系賦予權重，將權重值賦予連接關系圖，將圖2中的每一條連接賦予權重，得到圖7。使用w來表示圖中每一條邊的權重，比如w＝1。權重值越大的連接需要在安裝過程中越早出現，反之則需要在安裝過程的更后面出現。

圖6 優先級圖轉換層次結構圖

圖7 連接權重賦值示意

2.3 生成樹與基本割集

對連接關系賦權重的意義在于，可以依據安裝過程中優先順序的不同，對割集的質量進行評估。因此建立了評價函數Q對不同割集S進行評價，其計算公式為：

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

計算得到Q值越小，就認為其割集的質量越好，所以對于圖7，其最佳割集為＝{,,}。

生成樹是指在圖中不存在環路且能遍歷圖中所有節點的最少邊的圖。獲取所需要的生成樹來得到連接圖中的基本割集，用以生成裝配序列。如圖8所示，生成樹可表示為＝{,,,}，其基本割集S有四個，可計算出它們每一個割集的質量Q。

接下來根據比內－柯西定理，通過計算對應關聯圖的關聯矩陣的子矩陣B與其子矩陣轉置BT乘積的秩，就可以求解出圖2連接圖所對應的生成樹的總數，為det（BT）＝12個。如果對于每一顆生成樹都進行基本割集計算，是浪費時間的，因為根據不同圖的復雜程度，生成樹的數量十分巨大。因此使用余樹算法來進行生成樹變換，以尋找其最佳生成樹，從而減少計算量。

圖8 生成樹示意圖

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

圖9 余數算法流程圖

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

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

3 應用實例

接下來通過某型硬橫跨橫梁邊段三維模型來驗證上述方法，其結構如圖11所示，結構功能相同的零件作為同一零件表示，連接圖如圖12所示。

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

圖10 余算法執行過程

4 結論

本文提出了一種基于啟發式割集法的裝配序列的生成方法，通過建立割集分離提取產品中的子裝配體或者零件，以此來得到產品的裝配序列。該規劃方法的特點是通過使用啟發式方法和余數算法來對關聯圖進行生成樹變換，以獲取新的良好基本割集，進而生成裝配序列。實例表明，該方法可以得到良好的裝配序列。

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

圖12 硬橫跨橫梁邊段裝配關聯圖

[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]夏平均，姚英學，劉江省，等. 基于虛擬現實和仿生算法的裝配序列優化[J]. 機械工程學報，2007，43（4）：44-52.

[4]付宜利，田立中，謝龍，等. 基于有向割集分解的裝配序列生成方法[J]. 機械工程學報，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]. 計算機集成制造系統，2017，23（4）：781-790.

[7]劉曉陽，劉恩福，靳江艷. 基于蟻群算法的異步并行裝配序列規劃方法[J]. 機械工程學報，2019，55（9）：107-119.

[8]張晶，崔漢國，朱石堅. 基于人工神經網絡的裝配序列規劃方法研究[J]. 武漢理工大學學報（交通科學與工程版），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

四川省科技計劃重點研發項目（2019YFG0061）；四川大學自貢市校地科技合作專項資金項目（2018CDZG-5）；賽爾網絡下一代互聯網技術創新項目（NGII20180804）

姜沖（1995－），男，四川成都人，碩士研究生，主要研究方向為智能制造。*通訊作者：張凱（1984－），安徽淮南人，工學博士，助理研究員，主要研究方向為智能制造，E-mail：zkscu2005@163.com。