基于蚁群算法的废旧手机目标拆卸序列规划研究

王晓东 刘广阔 李泓瑞 孙华栋 符永高 李林

1.青岛科技大学机电工程学院 山东青岛 266061；2.中国电器科学研究院股份有限公司 广东广州 510300

1 引言

随着科技的进步和居民消费水平的提高，电器电子产品更新速度不断加快。2020年每个月的手机产量均保持在13000万台左右，并且随着5G时代的来临必将带来一波换机潮，初步估计2020年将会有3.4亿部废旧手机。在如此大的手机保有量，且手机产品更新换代的速度不断加快，产品不断地推陈出新的情况下，必然产生大量淘汰的废旧手机[1]。据中国工业和信息化部的数据显示，现在每年产生的废旧手机大约有2亿部。废弃的电气和电子设备（Waste Electrical and Electronic Equipment，WEEE）既有可能成为有价值的材料来源，又是有害物质的潜在来源[2]。作为WEEE其中的一类，废旧手机同样如此。如果妥善处理这部分资源一方面会降低生产成本，带来巨大的经济收益；另一方面会减少对环境的危害，实现绿色发展。近年来，拆解分离废旧手机回收其中的元器件以及提取贵金属的做法逐渐发展流行起来[3]。拆卸零件的顺序对于拆卸废旧手机商业化是至关重要的。

近年来，学者们对于拆卸序列进行了广泛的研究。在拆卸模型方面，周喜梅等[4]提出了可以生成可行拆卸序列的分层模块划分模型。聂应军等[5]通过拆卸过渡矩阵和拆卸继承矩阵描述了所有可能的拆卸过程。郭磊等[6]提出了一种零件层次划分方法，可以简化复杂产品拆卸序列的生成过程。

当零件数目较多时会产生大量的可行拆卸序列，难以从中挑选出最优解或次优解，而启发式算法可以很好的解决这一问题，因此在这一方面众多学者也做了大量的研究。例如：REN等[7]考虑拆卸操作的相关时间，通过遗传算法求解了异步并行拆卸计划。吴昊等[8]提出了一种结合二叉树算法的遗传算法，并通过此算法获得最优或次优选择性拆卸序列。TSENG等[9]提出了一种混合双向蚁群算法（HybridBACO），增加了路径选择的优势，并避免了极端信息素值的影响。张秀芬等[10]等通过粒子群算法解决了复杂机械产品的目标选择性拆卸序列规划问题。

上述研究成果多为针对机械设备或是大型家电产品，并没有适合于废旧手机拆卸模型。因此，对废旧手机进行拆卸回收研究具有一定实际意义。

手机相比于机械设备和大型家电产品零件较为密集，一个零件往往同时与多个零件连接。针对这一特点采用有向图表达零件间的约束关系，而零件之间的连接关系通过连接元胞数组表示。这种表达方式使后续手机零件拆解序列的生成更贴合实际拆解。以单位时间内产生的利润为优化目标，采用蚁群算法进行寻优，最终获得最优或次优解。

2 目标拆卸模型

拆解产品之前必须获知它的装配结构信息，只有完全清楚产品的装配结构信息，才能制定出可靠准确的拆卸模型。为表达产品的装配结构及其拆解信息，需要借助拆解示意图来描述。现有的拆卸示意图主要有无向图、有向图、与或图、Petri网等。其中有向图是一种简单有效的拆解示意图，通过零部件之间的约束关系表达零部件拆卸任务之间的先后顺序。因此本论文采用有向图作为拆解示意图。

2.1 定义有向图

图1 有向图

2.2 定义约束矩阵

基于有向图生成约束矩阵C=cij。设总零件个数为N，约束矩阵C为N×N的方阵。约束矩阵的每一行和每一列均代表相应的零件。当零件i对零件j有约束时cij=1；当零件i对零件j无约束或i=j时，cij=0。

根据图1，按上述原则得出对应的约束矩阵为：

2.3 拆卸序列的生成步骤

定义总体零件集合Ω：集合Ω为包含所有零件的集合。

定义可拆卸零件集合Φ：集合Φ为包含当前所有可拆卸零件的集合。

步骤一：计算约束矩阵中每一个列向量的模。

步骤三：在可拆卸零件集合Φ与总体零件集合Ω的交集中按概率挑选出一个零件j作为被拆零件放入拆卸序列S中。

步骤四：更新总体零件集合Ω（在Ω中将零件j删除）。

步骤五：更新约束矩阵（将约束矩阵中零件j的所在行归零）。

步骤六：若目标零件全部被拆除则转步骤七，否则转步骤一。

步骤七：输出拆卸序列S，结束。

3 优化目标

在废旧手机拆卸商业化的过程中，拆卸利润与拆卸效率应为着重点，因此以单位时间内产生的利润RERATE为优化目标进行寻优。

3.1 拆卸时间计算模型

针对已生成的拆卸序列建立拆卸时间模型计算其对应的拆卸时间。在手机拆卸的过程中拆卸时间TZ为断开被拆卸零件与其他零件之间连接所需要的时间。

由于废旧手机零件具有一个零件同时与多个零件连接或一个零件与另一个零件同时存在多处连接的特点。针对这一特点，创新性地利用了连接元胞数组这一模型表达零件之间的连接关系，并依此计算拆卸时间。

其中，Si为序列S中第i个零件；di-1为更新i-1次后的连接元胞数组；N为总零件个数；m为序列S中的零件总个数。

3.2 拆卸利润计算模型

拆卸利润R由总收益IN与成本EX组成。总收益IN包括元器件收益INA和材料收益INM；成本EX为废旧手机购买成本。

（1）元器件收益INA

元器件收益为已生成的拆卸序列中的零件以元器件的方式回收时的总收益。

其中：E为元器件收益矩阵，是维度为总元器件个数的行向量，各元素为相应元器件的回收价格。

（2）材料收益INM

材料收益为已生成的拆卸序列中的零件以材料的方式回收时的总收益。

其中：M为废旧手机的总质量；K为元器件质量矩阵，是维度为总元器件个数的行向量，各元素为相应元器件的质量；p为单位质量的废旧手机零件以材料的方式回收时的价格。

（3）废旧手机购买成本EXB

废旧手机购买成本即为从二手市场购买废旧手机的成本。

利润计算模型为：

4 蚁群算法寻优

当待拆卸废旧手机零件较多时，将会有大量可行拆卸序列，这将给寻优工作带来巨大的计算量。而启发式算法很好的解决了这一问题，对于拆卸序列的寻优，现有的文献多采用遗传算法、粒子群算法、蝙蝠算法等。由于目标拆卸的拆卸序列长度不一，而蚁群算法对于序列的长度并无要求，因此采用蚁群算法求解。

4.1 蚁群算法的原理

蚁群算法是模拟自然界蚂蚁觅食的行为。蚂蚁在觅食时，会在路径上留下信息素，并能感知到其他蚂蚁留下的信息素，并以较大概率选择信息素浓度高的路径，这样会形成一个正反馈。最终蚂蚁能够找到一条从巢穴到食物源最短的路径。值得一提的是信息素会随着时间的推移而挥发。蚁群算法最典型的应用是在解决旅行商问题上，而废旧手机拆卸零件序列规划问题十分类似旅行商问题，但也存在差异。所以本论文算法进行了相应的改动，以适应废旧手机拆卸零件序列规划问题。

4.2 蚁群算法在废旧手机拆卸序列优化中的应用

（1）个体适应度

在优化算法中个体适应度一般与优化目标相关联。单位时间内产生的利润为优化目标，可以将其直接作为个体适应度。因此个体适应度计算模型为：

（2）信息素矩阵

当每代拆卸序列生成完成后会在信息素矩阵中对适应度值最高的拆卸序列增加额外的信息素，而较高的信息素又会进一步指引下一代适应度值高的拆卸序列的生成，形成一个正反馈。经过多代寻优最终收敛到最优拆卸序列。信息素更新模型为：

（3）算法总体流程

相对应的流程图如图2所示。该算法既有随机性也有确定性。随机性保证了路径的多样性，使算法不易出现局部最优。确定性保证了算法朝着预定的目标发展。

图2 蚁群算法流程图

5 案例研究

下面以华为P7手机为例验证上述计算模型。参考行业的经验及手工拆机实践，华为P7可拆卸出16个零部件，分别是后盖、卡槽1、卡槽2、上盖板、下盖板、射频线、振动马达、后摄、前摄、接口保护罩、音量键、主板、听筒、屏幕、主体和电池。表1为华为P7各零件与序号的对应关系及具体信息。

表1 华为P7手机零件信息表

由深圳市爱博绿环保科技有限公司提供的回收价格信息显示，具有回收价值的零件主要为主板、电池、前摄、后摄和屏幕，其回收价格分别为45元、1.5元、2元、2元和1.5元，其余零件按其重量和其材料的当前市场回收单价计算。每个零件的重量来自于拆机实测。对于购买成本则取决于当前二手手机回收市场价格，价格会随着行情的变化具有不确定性。华为P7废旧手机购买成本约为30元/台。材料收益的价格由青岛宏盈旺再生资源有限公司提供，为3000元/吨。

根据华为P7手机的实际情况做如图3所示的有向图。

图3 华为P7零件有向图

华为P7零件之间共有6种连接方式分别为胶连、螺钉连接、卡扣连接、搭扣连接、嵌入连接和插入连接，每种连接对应的拆卸时间如表2所示。其中各种连接方式的拆卸时间是由人工重复5次拆机实验求取的平均值。

表2 各连接方式的拆卸时间

根据有向图生成华为P7的约束矩阵C。

华为P7的连接元胞数组D为：

其中，d0=[0 0 0 0 0 0]；d1=[1 0 0 0 0 0]；d2=[0 0 0 0 0 1]；d3=[0 0 0 0 0 1]；d4=[0 9 0 0 0 0]；d5=[0 3 0 0 0 0]；d6=[0 0 0 1 0 0]；d7=[0 0 0 1 0 0]；d8=[0 0 0 1 0 0]；d9=[1 0 0 0 0 0]；d10=[0 0 0 1 0 0]；d11=[0 0 0 0 1 0]；d12=[0 0 0 1 0 0]；d13=[0 0 0 0 1 0]；d14=[0 1 0 0 0 0]；d15=[0 0 0 1 0 0]；d16=[0 0 0 0 1 0]；d17=[0 0 0 1 0 0]；d18=[0 2 2 0 0 0]；d19=[0 0 0 1 0 0]；d20=[0 0 0 0 1 0]；d21=[1 0 0 0 0 0]；d22=[1 0 0 0 0 0]。

6 结果与分析

根据表1中的信息可以看出在目前市场条件下具有回收价值的零件有主板、后摄像头、前摄像头、电池和屏幕，其中主板的价值远超其他零件，因此主板应为必拆件。电池含有有害物质，也应为必拆件。因此以主板和电池为目标零件进行优化，结果如图4和表3所示。

图4 目标拆卸收敛过程

通过图4可以看出在未优化之前单位时间内产生的利润为0.0485元，经过蚁群算法优化后为0.0500元，提高了3.09%。从表3的数据中可以看出，以主板和电池为目标零件拆解一台华为P7所需要的时间为381.8秒，产生的利润为19.04元，单位时间内产生的利润为0.0500元。以每天8小时的工作时间计算，一个拆解工位通过拆解华为P7一天可以产生1440元的利润。

表3 目标拆卸优化结果

7 结论

（1）本文用混合图直观的描述了各手机零件之间的约束关系，基于有向图建立拆卸模型，推导出可行的拆卸序列，并与蚁群算法结合有助于可行拆卸序列的快速生成和优化。

（2）针对手机零件结构紧凑、一个零件往往同时与多个零件连接的特点，创新性的采用连接元胞数组全面的表达了零件间的连接关系，建立了适用于手机零件连接的表达方法。

（3）以华为P7为案例验证上述拆解模型和蚁群算法发现，单位时间内产生的利润从未优化之间的0.0485元提高到优化后的0.0500元，提高了3.09%；以每天8小时的工作时间计算，一个拆解工位通过拆解华为P7一天可以产生1440元的利润。

我国手机品牌众多，同一品牌手机旗下也有不同的型号，其结构都有差异。并且手机零件回收价格也随市场波动。根据本文所提出的方法，只需将不同型号的手机的约束矩阵、连接元胞数组以及手机零件信息输入到算法中即可快速地确定哪种型号的手机最具有拆卸回收价值以及以哪些零件作为目标零件产生的利润最高。面对当前废旧手机存有量巨大且该数字呈不断上涨趋势的情况，本文所提出的方法有利于解决废旧手机拆卸回收问题，可以为废旧手机拆卸的商业化提供理论判断标准，具有较强的实用性。