劉曉平， 李忠澤， 徐本柱， 朱吉滿， 何宏林

（合肥工業(yè)大學計算機與信息學院VCC研究室，安徽 合肥 230009）

汽車線束是指將不同工作用途的導線經(jīng)捆扎成束而形成的用于連接汽車各個電子設備的重要組件。線束預裝配是為了降低線束總成裝配時的復雜度和減少工作量而把線束分解成若干個子線束的過程。線束預裝配是線束進入總裝流水線的前工序，是直接影響產(chǎn)品生產(chǎn)效率及質(zhì)量提高的重要因素之一。目前現(xiàn)有的裝配控制研究主要集中在機械零部件的裝配序列規(guī)劃方面，主要方法有遺傳算法[1-2]、割集法[3-4]、優(yōu)先約束規(guī)則法[5]等。然而，線束預裝配主要完成把經(jīng)過壓接工序的導線預先裝配到電器接插件的端口中，與傳統(tǒng)的機械產(chǎn)品裝配有很大不同。機械產(chǎn)品裝配中零部件之間總是存在某種緊固或接觸聯(lián)接關(guān)系，相互關(guān)聯(lián)的零件能自發(fā)分離或者借助外力能夠發(fā)生分離[6-7]，然而線束中的導線經(jīng)過壓接工序后，導線之間復雜的實際物理連接關(guān)系便完全確定，在預裝配過程中必須完全保持它們之間的聯(lián)接約束，不能夠隨便發(fā)生分離。因此，傳統(tǒng)的遺傳算法、割集法、優(yōu)先約束規(guī)則法等常見的裝配序列規(guī)劃策略并不能夠直接應用于線束的預裝配過程中。

文獻[8]提出了一種基于約束集合模型的線束預裝配過程控制方法，然而該方法需要用戶手動選擇基準件和刪除不需預裝的導線和接插件，因此其本質(zhì)上只完成了導線連接關(guān)系的提取，并不是真正意義上的預裝配序列自動規(guī)劃。本文通過總結(jié)線束工藝設計中的工程語義約束信息，建立裝配關(guān)聯(lián)圖模型，并在此基礎上提出一種無需與用戶進行交互的線束預裝配自動規(guī)劃方法，實現(xiàn)對線束預裝配工藝的自動規(guī)劃。

1 相關(guān)概念

1.1 導線、接插件分類

線束圖紙是用來表示導線連接關(guān)系的 CAD圖紙。線束圖紙中存在大量的導線和接插件，為了在預裝配過程中針對不同情況實施不同的處理方法，本文先對導線和接插件進行分類。線束圖紙中的導線根據(jù)電路邏輯連接關(guān)系可以分為兩大類：單根線和內(nèi)聯(lián)線。

在上述導線定義的基礎上，本文根據(jù)端口連接的導線類型不同而把接插件分為以下3類：

定義3 簡單接插件(Simple Connector，SC )設接插件全集為，若ci( ci∈C )端口中連接的任意導線wi均為單根線時，稱ci為簡單接插件。簡單接插件端口中不同單根線的數(shù)目稱為簡單接插件的“單聯(lián)度”，記為 s cdeg( S C )，顯然 s cdeg( S C)≥ 1。

定義4 復雜接插件(Complicated Connector,CC ) 設接插件全集為，若 ci( ci∈C )端口連接的導線中至少存在一根內(nèi)聯(lián)線，稱ci為復雜接插件。復雜接插件中不同內(nèi)聯(lián)回路的數(shù)目稱為復雜接插件的“內(nèi)聯(lián)度”，記為 ic deg( C C )，顯然 ic deg( C C)≥ 1。與簡單接插件類似，復雜接插件也可能存在“單聯(lián)度”，scdeg( C C )≥ 0 ，然而簡單接插件的“內(nèi)聯(lián)度”一定為0。

定義5 孤立接插件(Isolated Connector，IC )設接插件全集為若ci( ci∈C )中所有端口均不連接任何導線時，稱ci為孤立接插件。顯然，s c deg( I C ) = i cdeg( I C )=0。由孤立接插件構(gòu)成的集合記為ICS。

1.2 子裝配體的定義

線束預裝配規(guī)劃主要完成從線束圖紙中提取出各個符合工程設計要求的子裝配體。子裝配體是導線與接插件的集合，在線束預裝配過程中，先要確定一個主接插件（簡稱主件），其它的接插件都是在主件的基礎上進行裝配。子裝配體的形式化定義如下：

子裝配體根據(jù)導線預裝過程的不同，還可以分為兩大類：后插型子裝配體和非后插型子裝配體。

如圖1(a)所示的為后插型子裝配體，圖1(b)所示的為非后插型子裝配體。

圖1 子裝配體

1.3 工程語義約束

對于導線和接插件數(shù)目很多的線束圖紙來說，如果通過組合方式直接生成所有的預裝配序列，必然會產(chǎn)生組合爆炸。然而，在實際的預裝配過程中，很多的預裝配序列并不符合工程設計上的要求。本文通過引入工程語義約束條件，可以直接在預裝配過程中把不符合約束條件的裝配序列排除掉，減少搜索空間，提高自動裝配效率。

約束 1 回路約束 對于內(nèi)聯(lián)線 wi, wj，若wi, wj為同一內(nèi)聯(lián)回路中的導線，則 wi, wj必須在同一裝配體SA內(nèi)，即 wi, wj∈SA。

約束 2 主件約束 主件選擇必須符合“CC先于SC”規(guī)則，即復雜、簡單接插件同時存在同一子裝配體時，應優(yōu)先考慮把復雜接插件作為主件。若同時存在多個復雜接插件，則應選擇“內(nèi)聯(lián)度”最大的接插件作為主件。

約束 3 端口約束 ICS=?，即預裝配過程中，不能出現(xiàn)把簡單、復雜接插件變成孤立接插件的情況。

2 預裝配規(guī)劃算法

2.1 裝配關(guān)聯(lián)圖模型

本文采用無向連接圖G( V, E)來對線束圖紙進行描述，其中頂點集合 V ( v1, v2,… ,vn)表示線束圖紙中的接插件集合C，邊集合E( e1, e2,…,em)表示導線的連接關(guān)系，它體現(xiàn)了線束圖紙中的回路約束，G( V, E)稱為裝配關(guān)聯(lián)圖。由于接插件端口內(nèi)可能包含多根導線從而與多個接插件存在連接約束關(guān)系，即 vi={w1, w2,…,wj, …,wk} ,wj∈W ，因此G( V, E)存在平行邊，是一個多重圖。

如圖2(a)所示，頂點圓圈內(nèi)的數(shù)字表示該頂點所代表的接插件端口中包含的導線代號，該圖中包含 2 個內(nèi)聯(lián)回路（1，4，6）、（2，3，5）。頂點V1和V4之間存在兩條邊，其中一條邊表示V1中的導線2和V4中的導線5連通，另一條邊表示V1中的導線1和V4中的導線6連通。為了方便起見，規(guī)定把裝配關(guān)聯(lián)圖中兩個頂點之間的平行邊均合并為一條，于是，裝配關(guān)聯(lián)圖由多重圖變?yōu)楹唵蔚臒o向連通圖，如圖2(b)所示。根據(jù)裝配關(guān)聯(lián)圖的定義，可建立G( V, E)對應的關(guān)聯(lián)矩陣 M ( G ) = (aij)n*n，其中i行 j列元素aij定義如下：

圖2 裝配關(guān)聯(lián)圖

顯然，關(guān)聯(lián)矩陣M( G)具有以下規(guī)律：

1）M( G)是一個n階方陣，n為線束圖紙中接插件的數(shù)目。

2）由初始的G( V, E)建立M( G)時，M( G )是一個對稱矩陣。

3）M( G)中任意頂點對應的行向量元素值不能同時存在1和-1。

4）M( G)中選為主件的頂點對應的行向量元素值不能存在-1。

5）若內(nèi)聯(lián)回路的導線不滿足導線約束時，該內(nèi)聯(lián)回路導線所在頂點對應的行向量元素值均為0或-1。

2.2 預裝配規(guī)劃算法

1）主件選取

為了滿足前面所述的主件約束條件，首先必須分析每個接插件的“內(nèi)聯(lián)度”和“單聯(lián)度”，因此從G( V, E)中確定當前子裝配體主件的步驟如下：

Step 1 求出M( G)中行向量元素值不存在-1或2的頂點集合Vm；

Step 4 若滿足 ic deg( vi) = δ(vi)的頂點有多個，假設分別為只有一個，則把該頂點對應的接插件作為主件；否則，隨機選取其中一個作為主件，主件選取結(jié)束。

2）最大子裝配體提取

主件確定后，需要提取出該主件對應的最大子裝配體，在提取最大子裝配體時必須將與主件存在回路約束的頂點都歸入該子裝配體中。根據(jù)裝配關(guān)聯(lián)圖的關(guān)聯(lián)矩陣定義，若兩個頂點之間有邊連接，其所在的行和列對應元素值為1或-1，說明這兩個頂點存在回路約束，因此由主件行向量的元素值便可得到其對應的最大子裝配體。

圖3所示的是某裝配關(guān)聯(lián)圖的關(guān)聯(lián)矩陣。若當前主件對應的頂點為vi，vi對應的行向量說明vi和vj、vs存在回路約束關(guān)系，vi、vj、vs構(gòu)成了以vi為主件的最大子裝配體，如圖3(b)所示。

直接由裝配關(guān)聯(lián)圖關(guān)聯(lián)矩陣的行向量得到的最大子裝配體并不一定是最終的子裝配體，因為其可能違背第1節(jié)所述的工程語義約束規(guī)則。如圖4所示，頂點圓圈內(nèi)的數(shù)字表示該頂點所代表的接插件端口中包含的導線代號，圖4(a)中包含了 3 個內(nèi)聯(lián)回路（1，2，3）、（4，5，6）、（7，8，9）。如果選擇頂點v2作為主件（虛線方框表示），直接由v2對應的行向量提取得到的最大子裝配體如圖 4(b)所示，v3中包含了（7，8，9）內(nèi)聯(lián)回路中的導線7，從而造成圖4(b)、圖4(c)所示的子裝配體不滿足回路約束。因此需要將圖4(b)中v3頂點的導線7刪除，從而得到圖4(d)、圖4(e)所示的子裝配體。圖4(e)中虛線圓圈表示頂點v3對應的接插件已經(jīng)在其它子裝配體中預裝，其實際為一個后插型子裝配體。

圖3 裝配關(guān)聯(lián)圖的關(guān)聯(lián)矩陣

圖4 子裝配體提取示例

由前面分析可見，最大子裝配體提取完成后，還需要對其進行工程語義約束檢測，對不符合約束規(guī)則的最大子裝配體通過適當刪除某些接插件或?qū)Ь€，使得該最大子裝配體本身及隨后生成的各個子裝配體都能滿足所有工程語義約束規(guī)則。因此，最終得到的子裝配體是最大子裝配體的一個子集。

3）工程語義約束檢測

為了敘述的方便，下面首先引入集合封閉性的定義。

定義9 集合封閉性 在G( V, E)中，設存在非空頂點集合任意頂點 vi( 1 ≤ i≤n )，若與vi存在回路約束的頂點都是頂點集合V中的元素，則稱V具備集合封閉性。

在關(guān)聯(lián)矩陣M( G)中，行向量值為 1或-1的元素表明了與該行向量對應頂點存在回路約束的其它頂點。如圖 5所示，若關(guān)聯(lián)矩陣中時，頂點集合 V { vi, vj, vk}具備集合封閉性；若 ajs=1， asj= 1 或-1時，頂點集合 V { vi, vj, vk}不具備集合封閉性，因為這時vj與vs存在回路約束，

圖5 裝配關(guān)聯(lián)圖的關(guān)聯(lián)矩陣

具備集合封閉性的頂點集合中任意頂點與集合外其它頂點不存在回路約束關(guān)系，因此如果最大子裝配體中所有頂點構(gòu)成的集合具有集合封閉性，那么此最大子裝配體與其它頂點也不會存在任何回路約束關(guān)系，其它子裝配體也不會因為此最大子裝配體而產(chǎn)生違背工程語義約束規(guī)則的情況。所以，具備集合封閉性的最大子裝配體可以直接作為最終的子裝配體而無需經(jīng)過工程語義約束檢測。

如果提取得到的最大子裝配體SA不具備集合封閉性，我們必須利用工程語義約束規(guī)則對它進行檢測，具體檢測方法如下：

Step 2 判斷wi是單根線還是內(nèi)聯(lián)線，并由判斷結(jié)果分別執(zhí)行1）或2）。

（1）若iw是單根線，則進行端口約束檢測，即判斷wi另一端是否存在于其它未被預裝的接插件內(nèi)，若是則把wi從SA中刪除，否則保留wi。

（2）若wi是內(nèi)聯(lián)線，判斷wi所在內(nèi)聯(lián)回路是否屬于SA的主件c1中的內(nèi)聯(lián)回路，若不是則把wi從SA中刪除，同時判斷wi所在內(nèi)聯(lián)回路的導線是否滿足導線約束，若不滿足，把iw所在的接插件也從SA中刪除。

Step 3 取出SA中下一根未處理的導線wj，重復，Step 2直至把SA中所有的導線處理完畢，這時SA便是最終的子裝配體。

4）預裝配規(guī)劃算法

根據(jù)前文所述，得到下面完整的線束預裝配規(guī)劃算法：

Step 1 由線束圖紙G( V, E)構(gòu)造初始關(guān)聯(lián)矩陣M( G)；

Step 2 在M( G)中選取一個主件頂點vi，同時提取出vi對應的最大子裝配體SiA；

Step 3 對SiA進行工程語義約束檢測，得到最終的子裝配體SA，并更新M( G)；

Step 4 重復Step2至Step3，直到M( G)中所有元素的值均為2。

3 應用實例

本文所述的思想已經(jīng)在由作者所在研究團隊基于Object ARX進行開發(fā)的線束工藝設計軟件系統(tǒng)中得到驗證。系統(tǒng)把線束圖紙讀入后，用戶只需要從菜單執(zhí)行“預裝設計”命令，便能夠自動生成各個子裝配體，并保存到指定目錄中。

圖6為某汽車車型簡化的線束圖紙，其中包含了9個接插件，內(nèi)聯(lián)回路為（11，21，32）、（43，50，16）、（71，82，91）、（104，89，13）、（143，152，160），其中101號導線為單根線，其兩端分別接于接插件HL02FB-M和HNMWP02FGYM-LOCK端口內(nèi)。

經(jīng)過預裝配自動規(guī)劃后依次得到的子裝配體如圖7(a)、圖7 (b)、圖7 (c)所示，其中圖7 (b)、圖7 (c)為后插型子裝配體，圖7 (a)為非后插型子裝配體。

圖6 線束圖紙

圖7 子裝配體

4 總結(jié)與展望

本文針對線束預裝配設計的特點，總結(jié)了線束預裝配過程中的工程語義約束信息，并建立裝配關(guān)聯(lián)圖模型，通過主件選取、最大子裝配體提取以及工程語義約束檢測來自動完成對整個線束圖紙的預裝配序列規(guī)劃。最后的實例表明該方法是有效可行的，能較好的解決大線束圖紙中預裝配序列規(guī)劃問題。本方法的最大優(yōu)點是整個預裝配序列規(guī)劃能夠自動完成，不需要與用戶進行交互。然而由本文方法得到的裝配序列僅是所有可行裝配序列中的一個，并不能確保其是最優(yōu)的，原因在于當多個接插件的“內(nèi)聯(lián)度”和“單聯(lián)度”都相等時，主件選擇具有一定的隨機性。此外，若遇到線束圖紙中存在某些極端情況，如大接插件與其它所有接插件均有回路約束關(guān)系時，該算法會把整個線束作為一個子裝配體。如果能夠進一步總結(jié)線束預裝配過程中的其他約束，如設定主件的內(nèi)聯(lián)回路數(shù)目閾值，考慮壓接位置約束、子裝配體數(shù)目約束等，將使自動預裝配規(guī)劃的結(jié)果更符合工程設計上的要求，進一步提高裝配的效率。

[1]王敬品, 胡志勇, 藺吉順, 等. 基于遺傳算法的裝配序列規(guī)劃[J]. 機械工程與自動化, 2008, (2): 9-11.

[2]Shan Hongbo, Li Shuxia, Gong Degang, et al. Genetic simulated annealing algorithm-based assembly sequence planning [C]//Technology and Innovation Conference, 2006: 1573-1579.

[3]張艷萍, 李從東. 集成環(huán)境下基于割集的裝配順序生成算法研究[J]. 機械設計, 2004, 21(9): 10-13.

[4]Mello L S, Sanderson A C. A correct and complete algorithm for the generation of mechanical assembly sequences [J]. IEEE Transactions on Robotics and Automation, 1991, 7(2): 228-240.

[5]朱海平, 邵新宇, 張國軍. 基于自動拆卸過程的裝配序列生成方法研究[J]. 工程圖學學報, 2008, 29(4):27-32.

[6]楊培林, 朱 均, 陳曉南. 裝配規(guī)劃中裝配體的表達及子裝配的識別[J]. 西安交通大學學報, 1999,33(12): 40-43, 60.

[7]張 勐, 古天龍. 基于帶權(quán)無向連接圖的子裝配體識別方法研究[J]. 桂林電子科技大學學報, 2008,28(1): 18-22.

[8]何士雙, 程光春, 吳 黃, 等. 汽車線束預裝配過程控制研究[C]//計算機技術(shù)與應用進展(下), 2007:957-960.