基于边收缩的最优装配序列求解方法

□梁勇强

（玉林师范学院 计算机科学与工程学院，广西 玉林 537000）

基于边收缩的最优装配序列求解方法

□梁勇强

（玉林师范学院 计算机科学与工程学院，广西 玉林 537000）

为确保最优装配序列的求解，本文提出一种新的最优装配序列求解方法. 首先扩展装配有向图结点的信息为一个边被收缩图，在此基础上给出扩展的装配有向图的概念，接着通过连续的边收缩生成扩展的装配有向图. 为了便于装配序列评价，又给出了装配任务有向图的概念，并将扩展的装配有向图转换成装配任务有向图，最后采用动态规划算法在装配任务有向图中搜索从初始任务到终止任务的最短路径以求解最优装配序列.

装配有向图；边被收缩图；装配过程；动态规划

1 引言

产品装配成本约占产品制造成本的一半，为了降低产品的制造成本，需要获取产品的最优装配序列.装配序列被定义为装配任务的有序集合[1].对于最优装配序列的求解，目前的各种求解方法可以分成两类.

第一类是硬计算方法.Mello等最先提出了基于与或图的经典方法[2]，并结合启发式搜索技术快速生成最优装配树[3].但应当注意到装配树描述的是一组装配任务的拓扑排序关系，不是具体的装配序列，实际上对应一组装配序列，因此可以说Mello等并没有彻底解决最优装配序列的求解问题，后来的学者也没有注意到这个问题，均以最优装配树作为最终结果.

第二类是软计算方法.在Mello等的硬计算方法提出之后，遗传算法、粒子群算法等软计算方法被广泛运用于装配序列的生成，但是软计算方法的引入并没有彻底解决最优装配序列的求解问题.以遗传算法为例，F.Bonneville等最先将遗传算法用于最优装配序列的求解[4]，其算法的操作对象是装配树，通过剪枝和嫁接实现遗传操作，显然该方法最多只能求出最优装配树.D.S. Hong等[5]以及 B.Lazzerini等[6]随后提出的算法则以零件序列作为操作对象，尽管这种做法后来被广泛采用（如文献[7]），但在不引起歧义的前提下，并不是任意可行的装配序列均可以用零件序列表示，这说明最优的装配序列可能不在算法的搜索范围内.文献[8]采用稳定性有向图的边的有序列表作为染色体编码确保了最优解包含在遗传算法的搜索范围内，但由于早熟现象的存在，使得算法本身并不确保一定能够搜索到最优解，有时只是一个满意解.

可见现有方法要么没有求出最优解，要么不能确保能够求出最优解.而在某些特殊情况下，人们十分希望能获得一个肯定的最优解，比如需求量很大的产品型号，另外研究软计算方法的性能时，也需要知道肯定的最优解.精确求解最优装配序列的一种方法是继续沿着Mello等的思路，在求得最优装配树的基础上进一步求解最优装配序列，但由于求解最优装配树和求解最优装配序列的评价标准是不同的，这使得从最优装配树生成的最优装配序列与产品的最优装配序列并不一定相同，因此这是不可行的.当然也先可以从装配与或图列举所有的装配树，再从所有装配树列举出来再评价，但这种穷举法性能上是不能接受的，笔者对一个12个零件的主机箱进行测试，结果执行时间需要将近一个小时.

本文提出一种基于边收缩的最优装配序列求解方法.本文首先扩展装配有向图的结点信息为一个边被收缩图，得到扩展的装配有向图，然后通过连续的边收缩来模拟产品的装配过程.为了便于装配序列评价，又引进装配任务有向图的定义，将扩展的装配有向图转换成装配任务有向图，在装配任务有向图中求解从初始装配任务到终止装配任务之间的最短路径表示的装配序列就是最优装配序列.

2 相关定义[1][9]

为了方便叙述，这里先列出参考文献上的相关定义.

定义1：在无向图G=(V,E)中删除顶点v1,v2之间的全部边，并使v1,v2重合得到顶点g，得到的图称为边(v1,v2)被收缩[5]，记作G/v1v2，g称为顶点v1,v2的收缩顶点.显然，图G/v1v2的顶点集合为V∪{g}-{v1,v2}[9].

定义2：产品的装配关联图G是一个无向图(V,E)，其中V表示产品零件的集合，对于任意的零件对v1,v2∈V，当零件v1,v2有关联关系时，边(v1,v2)∈E，否则(v1,v2)∈E.

定义3：给定两个子装配θi和θj，若零件子集θk=θi∪θj标识一个子装配，则将θi和θj装配在一起的操作称为一个装配任务[1].

定义4：给定一个具有n个零件的装配体V，则符合下列条件的n-1个装配任务的有序集合t1t2…tn-1称为装配体V的一条装配序列：（1）没有两个装配任务具有相同的输入；（2）最后的装配任务tn-1的输出是整个装配体V；（3）任意装配任务ti的输入要么是单个零件构成的子装配，要么是ti前面的装配任务的输出.

装配序列可以采用装配任务的有序列表、二进制向量的有序列表、零件划分的有序列表、连接子集的有序列表等四种形式表示[1].

图1 一个手电筒和它的一棵装配树

装配树不是装配序列的有效表示，装配树表示的装配方案（Assembly Plan）通常包含一组符合定义4的装配序列，例如图1（b）是图1（a）所示的手电筒的一棵装配树，该装配树包含的装配序列为10条.

零件序列也不是装配序列的有效表示，因为在不引起歧义的情况下，零件序列只能表示将零件逐一装配到产品上，这使得不是任意的可行装配序列都可以采用零件序列表示.例如图2（a）所示的产品结构，其所有可行装配序列（如图2（b）所示）没有一条可以用零件序列表示.若产品整体或部分具有这个结构，则该产品任意可行的装配序列均不能用零件序列表示.

图2 一个产品结构及其所有可行装配序列

定义5：设装配体的零件集合用V={v1,v2,…,vn}表示，则产品可行装配序列的有向图(directed graph)为(XV,TV)，其中：

是稳定装配状态的集合，而

是装配状态转换的集合[1].

记号Δ(V)表示子集划分，而({A,B,…,Z}) 表示A∪B∪…∪Z.

在不特别说明的情况下，本文后面提到的装配有向图均指可行装配序列的有向图.

3 本文算法

3.1 算法的基本思路

装配有向图中从初始结点到终端结点的一条路径就是一条可行的装配序列，所有这种路径构成的集合就是产品全部可行装配序列的集合.对于给定的评价标准，求解最优装配序列的问题显然可以转化为求解装配有向图中从初始结点到终端结点的最短路径问题，因此能够求解最优装配序列的正确方法应当如下：

（1）求解产品可行装配序列的有向图.

（2）求解装配有向图中从初始结点到终端结点的最短路径，或者先将装配有向图转换为其他形式，再求最短路径，从而求得产品的最优装配序列.

以上的分析逻辑实际上已经说明了本文方法确保可以求出最优解.

3.2 生成扩展的装配有向图

3.2.1 扩展装配有向图的定义

生成装配有向图是关键，拟采用下面的方法：首先装配有向图的初始结点是已知的，从初始结点出发，生成初始结点的所有后继，并标记初始结点到各个后继的转换，接着对所有后继作相同的处理，直到所有转换路径到达终端结点，就可以生成整个装配有向图.但是按照定义5，对于任意装配有向图结点Θ，Θ是零件集合的一个子集划分，由于子集划分中不包含任何零部件之间的关联信息，所以不能根据装配有向图结点自身的信息求解其所有后继结点，因此需要对Θ的信息进行适当扩展.

设装配关联图为G，对于任意的零件子集θ∈Θ，由于θ表示子装配，导出子图<θ>是G的一个连通子图，可以在G中通过连续的边收缩将θ的顶点收缩在一起得到一个收缩顶点，对Θ中所有零件子集均作相同的处理，可以得到G的一个边被收缩图，记作G(Θ).从边被收缩图G(Θ)的形成可以看出，Θ和G(Θ)的相互对应是唯一的，因此下面引进定义6，将装配有向图的结点替换成相应的边被收缩图.

定义6：对于给定的装配有向图，其对应的扩展的装配有向图为，其中

为稳定装配状态对应的边被收缩图的集合，这里G(XV)表示XV的元素对应的边被收缩图构成的集合，而

是中的边被收缩图之间的转换的集合，与TV构成一一对应关系.

显然扩展的装配有向图和相应的装配有向图是完全同构的.

3.2.2 生成给定结点的后继

设G(Θ)为扩展的装配有向图的任一结点，显然收缩G(Θ)的一条边的等价于执行一个装配任务，分别收缩G(Θ)的每一条边就可以生成该结点的所有后继，图3给出了生成G(Θ)的所有后继的算法.

图3 生成扩展的装配有向图的结点的所有后继的算法

在不考虑装配约束的情况下，显然G(Θ)的后继有|E(G(Θ))|个.图4(a)是图1(a)所示的手电筒的装配关联图（表示初始装配状态），图4演示了该结点的9个后继的生成过程，为演示边收缩和装配任务的对应关系，暂时没有考虑装配约束.

图4 生成扩展的装配有向图的结点的所有后继的例子

3.2.3 检查装配约束

图3的算法包含装配约束的检验问题，Mello等指出在产品装配过程中有四种类型的装配约束，即子装配约束、子装配稳定性、机械可行性和几何可行性需要检验.这里还需要注意的是：对于给定的装配有向图结点，纵然检查了上面提到的装配约束，仍然可能产生不合法的后继.例如，对于图4(c)所示的结点中，由于零件0和零件3装配在一起，零件1将不能被装配到产品中.为了防止这类非法结点生成，除了要检验前面提到的四种装配约束之外，还必须检查装配优先关系，防止一些零件因为几何可行性而不能装配到最终的产品中.显然，本质上检验优先关系也是检查装配几何可行性，因此可以借用现有的几何可行性检验方法.

本文假设所有检验装配约束的函数已经预先设计好，结合到图3所示的算法中.

3.2.4 防止结点的重复加入

不同的结点可能拥有相同的后继，共同后继的存在使得相同的结点可能被多次加入到装配有向图中.为了防止这种情况发生，在加入新的结点到装配有向图前，首先检查装配有向图是否存在相应的结点，只有结点不存在，才添加结点到装配有向图并添加相应的有向边，否则只添加相应的有向边.

本文的具体做法如下：（1）按照边收缩图中的顶点分组，将边收缩图转换成一个一维向量，使得比较两个边收缩图的大小就是比较相应的两个一维向量的大小.（2）为了提高检查的效率，增加一个列表保存结点的索引，这个列表按照结点的大小有序排列，这样就可以在这个索引列表的基础上应用二分搜索算法检查结点的存在性.

3.2.5 生成扩展装配有向图的算法描述

图5 生成扩展的装配有向图和相应的装配任务有向图的算法

设装配关联图为G，装配有向图的初始结点为Θ，显然G(Θ)就是G，因此生成扩展装配有向图的基本思路是：首先将G作为初始结点加入，然后展开结点G求解其所有可行后继，在求解后继的过程中检验装配约束，只有满足装配约束的后继才加入.设G'是G的后继，G''加入时分两种情况处理：如果G'不在XG中，则将G'加入XG中，并且添加有向边(G,G')到TG中；如果G'在XG中，则直接添加有向边(G,G')到TV中.对加入XG中的边收缩图G'均象G一样处理，由于G'的后继总比G'少一个顶点，最终得到一个平凡的边被收缩图，表明产品的所有零件已经被装配在一起.当所有的装配路径处理完毕，算法结束.

图5是生成扩展的装配有向图的算法，算法同时生成了装配任务有向图，装配任务有向图的概念将在后面交待.

图6显示了图1(a)所示的手电筒的扩展的装配有向图的生成过程，G0～G21是结点的加入顺序，这里已经考虑了装配约束，装配约束由表1给出的连接函数和移动函数定义，有关连接函数和移动函数的详细描述可参看文献[10].

表1 图1(a)所示的手电筒的连接函数和移动函数

图6 生成扩展的装配有向图和相应的装配任务有向图的例子

3.3 转换扩展装配有向图为装配任务有向图

装配序列的执行代价实际是各个装配任务的执行代价加上装配任务之间的转换代价，为了便于对装配序列进行评价，引进装配任务有向图的概念.

定义7：设有装配有向图(XV,TV)，tBEGIN为初始的装配任务，tEND为结束的装配任务，则其对应的任务有向图为(XT,TT)，此处

是装配任务的集合，而

是装配任务之间转换的集合.

装配任务有向图可以从装配有向图(XV,TV)转换得来，由于扩展的装配有向图(XG,TG)和装配有向图(XV,TV)完全同构，因此也可以从扩展的装配有向图(XG,TG)转换得来，本文在生成扩展的装配有向图(XG,TG)的过程中同时完成转换过程，具体算法已包含在图5中，而与图6相应的装配任务有向图可以根据图6画出.

3.4 求解最优装配序列

3.4.1 评价指标

为了对符合定义4的装配序列进行评价，将装配序列划分成若干个片段，在一个片断中的所有装配操作具有相同的基准零件.例如图6中的一条装配序列G0G1G4G9G15G20G21可以分成两个片段，第一个片段是G0G1G4，这个片段表示以零件0为基准零件，依次将零件1和3装配到基准零件0上，第二个片段是G9G15G20G21，这个片段表示以零件4作为基准零件，依次将零件2,5,6和0（这里零件0实际上是零件0,1,3构成的子装配）装配到基准零件4上.这样我们就可以对参考文献[3]中的评价方法稍作修改，得到本文的装配序列代价：

其中d是装配方向的切换次数，g是夹具的切换次数，s为相似操作的组数，f是片断数，w1～w4为权值，由领域专家确定.

限于篇幅，暂时不将装配序列评价的内容列入本文的研究范围，以上的评价方法仅仅作为计算的需要，实际应用本文算法时，可以采用更为合理的评价方法.

3.4.2 应用动态规划算法求解最短路径

装配任务有向图表示的装配序列的集合和对应的装配任务有向图一致，如果将装配任务有向图中装配任务的转换代价看作距离，那么从初始任务tBEGIN到终止任务tEND之间的最短路径就是最优的装配序列.本文采用动态规划算法求解最短路径：

（1）装配任务有向图有明显的分阶段的特点，任意两个装配任务t和t'，如果在装配有向图中t和t'指向的装配状态的具有相同的零部件数，则t和t'处于相同的阶段，显然总共有|V|+1个阶段.

（2）按照式(8)的评价标准，在任务有向图中，任意两个相邻的任务t和t'，t和t'之间的转换代价完全由t和t'本身确定，与前面的装配任务无关.因此，任意给定一个装配任务t，t后面的过程的发展变化不受前面的装配任务影响，因此满足无后效性.

（3）状态转移方程由装配任务有向图确定.

（4）采用下面的指标函数：

此处tk,tk+1,tEND等表示装配任务，uk,un+1为状态决策，wk(tk,uk)表示装配任务tk在决策uk的作用下到下一个装配任务的转换代价，Wk,n(tk,uk,…,tEND)表示装配任务tk在一系列决策构成的策略的作用下到tEND的转换代价，本文采用式(8)计算.

（5）采用下面的最优值函数：

动态规划方法在文献[11]中有详细介绍，本文不再赘述.本文采用逆序解法，输出装配任务指向的装配状态构成的序列恰巧表示产品的装配过程.

4 算法的性能

由于本文算法与现有各种算法的生成结果本质上不同，因此将本文算法和现有各种算法进行执行效率上的比较没有意义.因此下面仅对本文算法在性能上的可接受性进行分析.

4.1 算法复杂度

4.1.1 不考虑装配约束

本文算法的时间复杂度包含三部分：生成扩展的装配有向图的时间复杂度为O(|XG|+|TG|)，生成任务有向图的时间复杂度为O(|XT|+|TT|)，执行动态规划算法在装配任务有向图中求解最短路径的时间复杂度为O(|XT|+|TT|).而空间复杂度包含两部分：存储装配有向图的空间复杂度为O(|XV|+|TV|)，存储任务有向图的空间复杂度为O(|XT|+|TT|).设m为装配关联图的边数，则：

以上分析说明：1）装配关联图越稀疏，算法的代价越小.2）若不考虑装配约束，算法的代价还是比较大的.

（2）考虑装配约束

若考虑装配约束，则装配约束将对装配有向图结点的生成产生层层筛选作用，设一个被筛选掉的边被收缩图具有m'条边，则以上的|XG|,|TG|,|XT|,|TT|将在总量上减少问题规模为m'时的|XG|,|TG|,|XT|,|TT|.可见，装配约束越多则筛选越严格，算法的效率就越高.

（3）小结

从（1）和（2）的分析得知，装配关联图越稀疏，装配约束越严格，本文算法的执行效率越高.

4.2 实验测试

为了测试算法的实际执行效果，用C#语言实现了本文算法，随机选择一些常见的产品或者产品模块作为输入进行测试，测试结果如表2所示.

表2 本文算法的执行效果

表2的数据表明：（1）在装配关联图比较稀疏，装配约束比较严格的情况下（符合大多数实际产品的情况），本文算法的执行时间还是比较小的，求解17个零件的齿轮泵的最优装配序列仅需约138秒，求解22个零件的压缩机的最优装配序列仅需约38秒.（2）随着零件数目的增加，本文算法的执行时间有明显增加的趋势，说明对于大型产品，不宜直接采用本文算法生成最优装配序列，但可以结合分层的思想.（3）算法的空间代价很小，完成以上测试未见出现内存不足的现象.

本文的实验环境为：主频2.0GHz CPU(双核)，1G RAM、Windows XP操作系统、Microsoft Visual Studio 2005集成开发环境.

5 结束语

本文算法属于精确求解最优装配序列的硬算法.理论上，本文算法确保能够生成最优装配序列，这是现有各种算法暂时还没有做到的.应用上，从理论分析看本文算法对于装配关联图稀疏、装配约束严格的产品是有效的，实验测试也证实了这一点，在开发实际的应用系统时，本文算法可以与文献[8]的方法结合在一起，对于装配关联图稀疏、装配约束严格的产品尝试本文算法，否则尝试文献[8]的算法. ■

[1]LUIZ S. HOMEM DE MELLO, ARTHUR C.SANDERSON. Representations of Mechanical Assembly Sequences [J]. IEEE Transaction on Robotics and Automation, 1991, 7(2):211-227.

[2]LUIZ S. HOMEM DE ME-LLO, ARTHUR C.SANDERSON. A Correct and Complete Algorithm for Mechanical Assembly Sequences [J], IEEE Transaction on Robotics and Automation, 1991, 7(2):228-240.

[3]LUIZ S. HOMEM DE MELLO, ARTHUR C.SANDERSON. Two Criteria for the Selection of Assembly Plans: Maximizing the Flexibility of Sequencing the Assembly Tasks and Minimizing the Assembly Time through Parallel Execution of Assembly Task [J]. IEEE Transaction on Robotics and Automation, 1991, 7(5): 626-633.

[4]F.Bonneville, C.Perrard. A genetic algorithm to generate and evaluate assembly plans. IEEE Symposium on Emerging Technology and Factory Automation, October, 1995: 231-239.

[5]D.S. Hong and H.S. Cho. A genetic-algorithm-based approach to the generation of robotic assembly sequences. Control Engineering Practice, February. 1999,7:151-159.

[6]B.Lazzerini, F.Marcelloni. A Genetic Algorithm for Generating Optimal Assembly Plans [J]. Artificial Intelligence in Engineering, 1999, 14:319-329.

[7]刘元伟,崔光宇.基于遗传算法的装配顺序优化[J].大连交通大学学报,2009,30(4):22-25.

[8]LIANG Yong-qiang, ZHU Xiao-shu, XIE Miao. Improved Chromosome Encoding for Genetic-Algorithmbased Assembly Sequence Planning, In:2010 International Conference on Intelligent Computing and Integrated Systems, GuiLin, China, 2010:35-39.

[9]王朝瑞.图论[M].北京：北京理工大学出版社，1997.

[10]张建标，唐荣锡，魏生民等.装配顺序的生成算法研究[J].机械工程学报，1999，35(5)：58-61.

[11]《运筹学》教材编写组. 运筹学[M].北京：清华大学出版社，2005.

【责任编辑 谢明俊】

A Method for Generation the Optimal Assembly Sequence By Using Edge Contraction

LIANG Yong-qiang
(College of Mathematics & Computer Science, Yulin Normal University, Yulin, Guangxi 537000)

To ensure the generation of the optimal assembly sequence, a novel algorithm for generating optimal assembly sequence is proposed. On the basis of the information extension of the node of assembly directed graph (ADG) based on edge contracted graph (ECG), the notion of extended assembly directed graph (EADG) is presented firstly. And then, EADG is generated by iterative contraction of edges of ECG. To facilitate the assembly sequence evaluation, EADG is converted to assembly task directed graph (ATDG) after the notion of ATDG is presented. Finally, the optimal assembly sequence is generated by using the dynamic programming algorithm to search the shortest path from the initial assembly task to the final assembly task in ATDG.

assembly directed graph, edge contracted graph, assembly process, dynamic programming

TP391.73

A

1004-4671（2014）05-0108-10

2014-09-05

梁勇强（1967～），男，广西玉林人，玉林师范学院计算机科学与工程学院副教授，硕士，研究方向：图论算法和计算机视觉。