基于改进Floyd算法的转向机拆卸序列研究*

刘玉娟，易朋兴*，胡玖坤，罗璐琴

(1.华中科技大学 机械科学与工程学院，湖北 武汉 430070；2.东江环保股份有限公司，广东 深圳 518057)

0 引 言

随着我国汽车工业的飞速发展，汽车报废量也逐年增加，而拆卸是回收和再利用的前提。良好的拆卸序列有利于提高拆卸效率、降低拆卸成本，因此退役汽车零部件拆卸序列规划成为研究热点之一。

目前，研究废旧产品拆卸序列的基本思路就是“拆解模型(图)+方案的寻优算法”[1]。薛俊芳等[2]构建了产品拆卸有向图，将时间和拆卸复杂度的乘积作为权重，然后利用Floyd算法求出目标零件的最优拆卸序列；张新建等[3]构建了产品拆卸混合图，分别以最少时间和最少费用作为评价标准，利用Floyd算法进行优化分析。这两种图的模型都只适合对目标零件的拆卸进行优化，在利用Floyd算法寻找最短路径时不能遍历所有节点，因此不能实现完全拆解。在实际拆解中，很多时候是把产品的一部分作为一个整体拆卸下来，然后再分别拆解。有向图和混合图中都只能表述零件之间的连接关系，不能反映一个部件(子装配体)拆卸下来的情况。王喆等[4]在与或图的基础上演变出了拆卸网络图，可以解决上述问题，但未对Floyd算法进行改进，当拆卸网络图的节点较多时，出现计算效率低的情况。国内外学者对Floyd算法进行了研究[5～7]，提出了改进思想。邹桂芳等[8]对Floyd算法进行了改进，只需两步迭代即可求出结果，提高了算法效率；徐达等[9]对Floyd算法进行优化，省略非必要中间节点路径计算，减少了计算量。

转向机是汽车转向系统中的核心部件，且被证明具有良好的可再制造性[10]。本文将对转向机的拆卸序列进行研究，采用拆卸网络图对产品进行拆解建模，再利用改进的Floyd算法对其进行求解，从而得到转向机优化的拆卸序列。

1 转向机拆卸网络图的构建

1.1 转向机结构特征

循环球式转向机的结构图如图1所示。

图1 循环球式转向机1-螺杆；2-螺母；3-钢球；4-扇齿；5-摇臂轴；6-壳体；7-推力轴承

转向机有两个传动副，第一传动副由螺杆、钢球和螺母所组成，第二传动副由螺母上的齿条和转向摇臂轴上的齿扇组成。工作时，因钢球经过位于螺母中的球孔和插入球孔中的导套可循环流动，故称之为循环球式转向机。

对于一般的轴系结构而言，按照从外到内的顺序依次拆卸即可，但循环球式转向机的转向螺杆和转向臂轴呈十字交叉分布，拆解规划涉及4个方向的变换，需重点考虑拆卸方向及拆卸工具的变化对拆卸的影响。

此外，传统的拆卸序列规划都是考虑将单个零件从装配体上拆卸下来的先后顺序，没有考虑一个部件(子装配体)拆卸下来的情况。但对于循环球式转向机的螺母组件来说，若直接从装配体上拆除导管和钢球等零件，不便于使用拆卸工具，应先把螺母组件作为一个整体从螺杆上拆下来再进行拆卸，则减小了拆卸难度。

1.2 拆卸网络图构建规则

拆卸网络图是由与或图演变而来的。在与或图中以节点的形式来表达产品的拆卸状态，从产品总成出发分析其可能的拆卸方式，并将拆卸后的零件用一条圆弧连接起来，它们之间是“与”的关系；若对于同一个部件，存在不同的拆卸方式，那么不同的拆卸方式之间是“或”的关系[11]。

拆卸网络图也是从产品总成出发，选定一个零件作为产品完全拆卸的终点，从而使所有的拆卸路径归于同一个节点。此外，拆卸网络图在与或图的基础上进行了简化，把所有的单体零件删除，只关注部件下一步的拆卸序列；对于部件(子装配体)作为一个整体拆卸下来的情况，在同一个节点中用逗号隔开表示不同的部件。

1.3 基于MTM方法的拆卸时间评估

在得到拆卸路径的网络图后需要给每条边赋予相应的权值，现有的评价标准包括拆解时间、拆解成本和拆解能量[12]，对于完全拆解来说，拆解成本随拆解时间的增加而增加，因此本文以拆解时间作为评价标准。

基于方法时间衡量(method time measurement，MTM)法是一种时间测量技术，其基本单位为TMU，换算关系为1 TMU=0.036 s。相比于常用的直接法和间接法测量拆卸时间，MTM法不受拆卸人员业务水平和拆卸环境的影响，减少人工干扰，因此本文采用基于MTM方法的报废汽车拆卸时间确定法。

MTM法是按基本动作单元(足动、腿动、转身、俯屈、跪、站、行、手握)和执行因素(伸手、搬运、旋转、抓取、对准、拆卸、放手)设定作业时间标准及查定正常作业时间，制定作业标准时间[13]。利用MTM法确定拆卸时间时，首先要根据作业决定基本动作，然后测定基本动作的大小(如距离、旋转角度等)，识别动作的基本性质，最后通过代码对动作进行描述，根据代码查表即可得到相应的时间。MTM法分析方法较为复杂，但是精度较高，适用范围广泛。

这里以其中一步拆卸操作—从转向机壳体上取下加油螺口为例进行分析，其MTM编码如表1所示。

表1 取加油螺口的MTM编码

则拆卸时间为：T=TMU×0.036 s×频率=(8.2+2.0+18.0+9.4×14+18.0)×0.036=6.4 s，向上取整为7 s。

2 改进Floyd算法

2.1 Floyd算法简介

Floyd算法是用于求解加权网络最短问题的经典算法，其核心是一种逐步逼近的思想[14]。基本步骤如下：

(1)网络图D={v，w}，v表示图中节点，w表示节点间的连接，将网络图转化为赋权矩阵D，矩阵中第i行第j列元素表示从节点i到节点j的距离，当i=j时，dij=0；若节点i和节点j之间没有直接相连的线，则dij=∞。

(2)将赋权矩阵进行多次迭代，得到一个矩阵序列D1、D2、…、Dn，其中：

(1)

迭代完成后，Dn中的元素就是最终从节点i到节点j的最短路径。其核心思想是让原始路径依次跨接v1、v2、…、vn各个节点，即从跨接一个节点到跨接n个节点。每次迭代中保留距离较短的路径，完成所有迭代后即可找到任意两点之间的最短距离。

(3)反向追踪，找到具体的路径。Floyd算法的一个原理是，假设P是从i到j最短路，k是P上的一个节点，则沿着P从k到j，必然也是从k到j的最短路。因此，可以定义一个path矩阵，与赋权矩阵同时迭代，用来追踪最短路径。

2.2 改进Floyd算法分析

Floyd算法虽然能找到任意两个节点之间的最短路径，但每个节点都需要迭代n次，共有n×n个节点，因此算法复杂度为O(n3)。当节点数量较大时，算法需要进行n3次加法计算，计算效率很低；并且原始算法需要迭代n次，产生了n个迭代矩阵，占据较大的内存空间。

针对这些问题，学者们提出了许多改进方法。文献[9]的核心思想是较小的行与列先计算，通过两次迭代即可完成计算。第一次迭代计算D1时，第一行和第一列不需计算，直接计算第二行和第二列中未包含在第一行和第一列中的元素，让其跨接，接着计算第三行和第三列中未包含在第1、2行和第1、2列中的元素，让其跨接v1，依次下去，直到第n行。第二次迭代则反向进行，先计算第n-1行和第n-1列中未包含在前n-2行和前n-2列中的元素，让其跨接节点，反向向较小的行列元素计算，完成第二次迭代。分析对比改进前后的算法可知，一般Floyd算法是n次迭代，让各个路径依次跨接所有节点，逐一比较、选择其中最小值，而改进后的Floyd算法仅通过两次迭代就能跨接到所有节点，完成n次比较。这种方法通过两次迭代即可求得最短路径，大大减少了计算所需的内存空间。

本文将两种改进方法融合，既能减少程序占用的内存空间，又能减少计算量，提高运算效率。

改进Floyd算法的伪代码描述如下：

Input：

赋权矩阵：Dn×n={D12,D13,…,Dnn}

Output：

规划矩阵：：Dn={D12,D13,…,Dnn}

路径矩阵：path={v11,v12,…,vnn}

Begin：

1.fori=2 ton

2.forj=i+1 ton

3.fork=1 toi-1

4.ifDij是所在行或列的最小值

6.else=min{Dij,Dik+Dkj};

7.ifDij是所在行或列的最小值

9.elseDji=min{Dji,Djk+Dki};

10.end for

11.fori=n-1 to 1

12.fork=ntoi+1

13.forj=i+1 ton

14.Repeat 4～9

15.end for

End

3 算例分析

本文以某型循环球式转向机为例来验证本算法的可行性与有效性，其结构图如图2所示。

由于很多零部件是作为附属件依附于主要零部件的，当进行拆解时只要将主要零部件拆解完成，附属件可以从主要零部件中分离出来，如螺栓、螺母、垫片和轴套等零件均为附属件，在本文中对其进行了简化使模型更为直观，同时也为后续拆解规划提供便利。笔者在分析零件之间联接关系的基础上，把螺杆螺母组件作为一个整体进行拆卸，组件中包含的零部件拆卸顺序可以确定且是唯一的。

转向机零部件的信息表如表2所示。

图2 循环球式转向机爆炸图a-加油螺口；b-左端盖；c-调整螺栓；d-转向臂轴；e-转向臂轴油封；f-壳体；g-螺杆螺母组件；h-轴承i-上端盖；j-转向螺杆油封

代号名称拆解工具拆解方向a加油螺口扳手+Zb左端盖+Zc调整螺栓—+Yd转向臂轴—+Ze转向臂轴油封专用工具-Zf壳体——g螺杆螺母组件—+Xh轴承—+Xi上端盖—+Xj转向螺杆油封专用工具+X

表2列出了关键零部件的名称、拆解工具和拆解方向。

根据拆卸网络图的构建规则可以得到循环球式转向机拆卸路径的网络图如图3所示。

图3 循环球式转向机拆卸路径的网络图

笔者将图3中的节点进行编号，其中编号1为转向机总成，编号18为转向机壳体，其他编号为拆卸操作中所有可能存在的零件和部件的状态。再将由MTM法算出来的拆卸时间作为权值赋给相应的边，最终得到转向机的拆卸网络图如图4所示。

图4 循环球式转向机的拆卸网络图

根据循环球式转向机的拆卸网络图，可以得到赋权矩阵D，将其代入改进的Floyd算法Matlab程序，得出一个18×18的path矩阵。Floyd算法给出了任意两点间的最短路径，根据转向机拆卸网络图可知，本文仅需要找出从节点1到节点18最短时间及路径。从Matlab的输出结果D18和path矩阵分别截取第一行如表3所示。

从表中可以读出：矩阵D第1行18列元素为54，即拆卸路径最短的耗时为54 s；在path矩阵中，从终点反推路径，即先找到P[1,18]为16，表明1-18最短路径为1-16-18，接下来找P[1,16]为14，表明最短路径为1-14-16-18，依次类推，可以得出完整的最优拆卸路径为1-2-5-6-7-9-12-14-16-18。

对应转向机，该路径表明在拆卸时首先应该拧下加油螺口(a)，再将侧盖和转向臂轴总成一起从壳体中拆出来，取出和左端盖连在一起的调整螺栓，得到转向臂轴(d)，然后将调整螺栓(b)和左端盖(c)分离。将转向机整体转90°，拆转向螺杆油封(j)，由于拆除油封需要专门的工具，继续拆转向臂轴油封(e)。接下来按顺序依次拆除上端盖(i)，轴承(h)以及螺杆螺母组件(g)，最后剩下转向机壳体(f)，拆解完毕。

通过在程序中设计断点和计时可以比较几种算法，具体结果如表4所示。

在针对转向机的拆卸规划中，几种算法计算结果相同，能得到相同的最短拆卸时间和优化序列。相比原始Floyd算法，两种改进后的算法复杂度降低，循环次数减少。第一种改进算法运行速度更快，但用Matlab程序实现时，难以追踪路径；第二种改进的主要迭代思想并没有改变，是通过先判断后计算的方法，改进的力度有限，尤其是当网络图节点较多、即矩阵较大时。而融合后的新算法综合了两种改进算法的优点，循环次数和算法复杂度都有大幅减少，特别是针对节点较多的零部件进行拆解时，能够更高效地得到结果。

表3 输出结果部分数据

表4 改进算法与初始算法计算结果对比

4 结束语

本文选择循环球式转向机作为研究对象，通过网络图建立拆解信息模型，只需一条路径就能将结构完全拆解；基于MTM作业时间衡量，比传统经验能更准确地算出每个动作所需时间。在比较两种改进Floyd算法计算效率和运用局限性的基础上，融合两种算法的改进思想，再运用融合改进后的Floyd算法快速准确地得到了转向机拆卸时间最短的拆卸序列。

该方法可推广用于零件数为10～40的其他零部件的拆卸规划。但对于发动机、变速箱这一类零件数较多结构复杂的零部件，需将整体根据产品结构模型先拆分为子系统，再对各子系统运用该方法。