摘 要

无论是电子废弃物的回收，还是产品为维修再制造，拆卸序列规划都是其中最重要的步骤。拆卸序列规划究其根本就是为了降低拆卸成本，在此基础上，使用尽可能简单且能完成目的的工具来对产品进行符合预期目标的拆卸方案。但影响拆卸序列的因素有很多，包括拆卸所得效益、拆卸时间等。如何将这些因素纳入拆卸序列生成的考量之中是一个难以解决的问题。

近年来新起的粒子群优化算法为拆卸序列规划问题求解提供了新方案。拆卸约束图是一种早期提出的基于图论的方法，在此基础上，将产品零部件之间的工程因素加入其中，并且赋予这些工程属性不同的权重，从而生成了拆卸赋权混合图。详细描述了粒子群算法的原理，并通过映射将粒子群算法与混合图模型对应起来，在深入研究粒子群算法原理后，根据实际情况，列写了解决DPS的算法流程。根据拆卸序列规划的特点，重写了算法中粒子位置和速度等属性的进化规则。定义了粒子适应度函数，用于评价结果的优劣。最后以某款机用虎钳作为实例，使用粒子群算法来求解该产品的拆卸序列，并实验了在不同参数情况下拆卸序列的求解情况，达到了验证粒子群算法高效简洁特点的目的。

关键词：拆卸序列规划；粒子群算法；拆卸混合图

Abstract

Whether it is the recycling of electronic waste, or the product is remanufactured for maintenance, the planning of the disassembly sequence is the most important step. The fundamental of disassembly sequence planning is to reduce the cost of disassembly. On this basis, use the tools that are as simple as possible and can accomplish the purpose to carry out the disassembly program that meets the expected goals for the product. However, there are many factors that affect the demolition sequence, including the benefits of demolition and the time of demolition. How to incorporate these factors into the consideration of disassembly sequence generation is an intractable problem.

In recent years, the new particle swarm optimization algorithm provides a new solution to the problem of disassembly sequence planning. Disassembly constraint graph is a graph theory-based method proposed earlier. On this basis, engineering factors between product parts are added to it, and these engineering attributes are given different weights, thus generating a disassembly weighting mixed graph. The principle of the particle swarm optimization algorithm is described in detail, and the particle swarm optimization algorithm is mapped to the mixed graph model through mapping. After deeply studying the principle of the particle swarm optimization algorithm, the algorithm flow for solving the DPS is listed according to the actual situation. According to the characteristics of disassembly sequence planning, the evolution rules of particle position and velocity attributes in the algorithm are rewritten. The particle fitness function is defined and used to evaluate the pros and cons of the results. Finally, using a machine vise as an example, to solve the disassembly sequence of the product, and the solution of the disassembly sequence under different parameters is tested, which achieves the purpose of verifying the efficient and concise characteristics of the particle swarm algorithm.

Key Words：Disassembly Sequence Plan-ning；Particle Swarm Optimization；disassembly hybrid graph

目 录

第1章 绪论 1

1.1 研究目的与意义 1

1.2 国内外研究现状 2

1.3 论文内容安排 3

第2章 拆卸序列规划问题 4

2.1 拆卸的概念与分类 4

2.1.1 拆卸的概念 4

2.1.2 拆卸的分类 5

2.2 拆卸相关信息及一般原则 6

2.2.1 拆卸信息 6

2.2.2 产品零件约束类型 7

2.2.3 拆卸一般原则 8

第3章 产品拆卸信息建模 9

3.1拆卸赋权混合图模型的建立 9

3.1.1 拆卸混合图模型 9

3.1.2 约束关系数学表达 11

3.1.3 拆卸混合图应用 12

第4章 粒子群算法在DSP中的应用 15

4.1 粒子群算法 15

4.1.1 粒子群算法模型和思想 15

4.1.2 PSO原理及模型映射 16

4.2 拆卸序列的适应度函数 18

第5章 拆卸序列规划实例 19

5.1 实例应用 19

第六章 总结与展望 23

6.1 全文总结 23

6.2 未来展望 23

参考文献 25

致谢 28

第1章 绪论

1.1 研究目的与意义

21世纪以来，伴随着电子科学的持续发展和人们消费水平的提升，各式各样的电器和数码产品的产量在逐年增加，但随之其来的废弃量也在不断上涨。据联合国在统计的相关数据，2016年期间，全世界电子废弃物的产量高达4470万吨，预测到2022年其产量将高达5220吨。而2016年全球被记录、招收聚集和回收再利用的电子废弃物仅有890万吨，而这只是2016年电子产品产量的百分之20不到。

如果能回收电子废弃物中蕴含的大量资源，就可以创造出巨大的经济效益，不仅能减少不可再生资源的采集，还能保护环境，实现可持续发展，使资源短缺的现象得到有效缓解。电子废弃物中不仅存在铜、铅、钨、镁、铝等有色金属，还包含锂、铂、钛、金、锗等稀有金属。在一吨废旧手机中，可以回收大约105千克铜、0.14千克金和3千克银。但随之而来的，汞及汞化合物、六价铬化合物、镉及镉化合物等有毒有害污染物质也存在于电子废弃物中，如果对其处理不当（如进行填埋、高温焚烧等）不仅会对农田、水资源、空气质量造成污染，还会对民众的生活质量及健康造成不良影响。2005年欧盟出台的废弃电子电器设备指令（Waste Electrical and Electronic Equipment）使得欧盟的各类电器产业开启了绿色再制造的新局面，更多企业将电子废弃物纳入回收的计划之中。如今，我们面临着资源的日益匮乏，以及大量电子废弃物不能进行回收再利用，人们面临着越来越大的资源及环境保护的压力。为了进行合理的资源循环以及长远的可持续发展战略，减轻大量的电子废弃物对环境造成的压力，将电子废弃物再利用、资源化，形成绿色产业链已经势在必行了。

各类电子产品都具有其生命周期。包括智能辅助制造、智能辅助规划、计算机辅助车间优化等在内的传统制造领域进行的研究，大部分都是针对产品生命周期导入期即产品方案设计和制造工艺及方案的研究。如今，世界各国都面临着严峻的环境及资源问题，可持续制造受到了各个领域的重视，产品生命周期末端处理技术已经成为技术人员的研究重点。

使用生命周期末端处理技术来处理废弃电子电器时，最关键的就是进行预处理，而预处理中最重要的部分就是拆卸。拆卸是从电子电器废弃物中卸下可回收部件或有害部件的过程，拆卸的意义在于能够将有害零件从废弃物中分离，有利于进行下一步的填埋、焚烧，从而达到保护环境、提高电子废弃物利用率的目的。为了提高拆卸的效率、减少拆卸成本、减轻二次污染，拆卸序列规划是重中之重，优秀的可行序列不仅能够提高整体的效率，更能减轻企业的负担，使电子废弃物的再利用得到普及。近年来，DSP问题受到了可持续制造领域和生命周期末端处理研究领域的广泛关注，国内外研究人员对此展开了大量研究。

DSP问题属于NP完全问题，国内外学者近十年来研究出了各种求解DSP问题的方法，但不同的DSP问题具有不同的条件和目标，若不对其进行一定的限制，拆卸序列的数目将随着产品零件数量的不断增加呈现指数式的增长，即使规定了相关的约束，包括零件之间接触类型、拆卸工具类型、拆卸方向个数、拆卸优先关系、拆卸成本等，可以组合出的拆卸序列数量还是很多。在没有经过有效计划的情况下进行拆卸会浪费许多的人力物力，甚至导致拆卸失败。本文的目的就是深入研究DSP问题，探讨各种工程因素对序列的影响，如接触关系、拆卸方向等，寻找有效解决DSP问题的方法，以计算出最佳的拆卸序列来解决电子废弃物的拆卸问题。

电子废弃物的拆卸效率和成本与拆卸序列的优劣有着很大的关系。寻求最优拆卸序列的目的是为了在满足产品零件约束关系的条件下，使用最合适的拆卸工具，在最短的时间内完成拆卸，并降低拆卸人力资源的使用。当前求解DSP问题使用较多的思路是：使用图的方法，将产品中零件之间的几何关系、约束条件用图模型表达，然后得到产品的拆卸序列，最后使用进化算法对其进行优化，得到最优拆卸序列。进化算法能够适应各种类型的问题，处理困难问题时不容易发生错误，具有容易实现、效率高的特点，拆卸序列规划问题受到许多因素影响，进化算法特别适合用来解决类似问题。本文将基于进化算法中的粒子群优化算法，来求解DSP问题。

1.2 国内外研究现状

随着环境保护行业需求的日益增长，研究人员对DSP问题进行了广泛而系统的研究，包括其建模方法、评价指标、优化求解方法，并且取得不菲的成果。早在20世纪90年代，就有学者开始了DSP问题的研究，在研究DSP问题的早期，用线性规划方法对拆卸序列进行精确求解和对拆卸序列的规划建模与评价指标是主流方向；随着智能优化算法的普及，越来越多的学者开始使用优化算法来进行DSP问题的求解。

在拆卸序列规划问题研究的早期，研究人员主要通过图论技术来开展研究，随着科技的不断进步，智能仿真技术也取得了飞速的发展。Bourjault^[1]最早提出了使用图模型来表达产品结构的方法，他研究了产品的组装顺序，并试图以此来将零件的结构表示在图模型中，通过将产品信息输入到图模型中，结合仿真处理技术，以搜索出所有可行的序列，并进一步优化这些序列。Lambert^[2]最早使用基于图论的方法，他将产品零件分为一个个最小拆卸单元，让后将这些最小拆卸单元视为图中的顶点，并且按照从左到右的顺序进行拆卸，不过这种方法需要使用继承计算机辅助设计工具，所以建模难度相对较大。这种方法类似于AND/OR图方法，使用线性规划来对搜索出来的可行序列进行下一步优化，以产品的最大收益为目标来得到最优的拆卸序列。Srinivasan和Gadah^[3,4]将产品的邻接关系和空间约束关系引入到图论中，他们使用了两种不同的图论方法表示这些关系，如通过有向边表示两个顶点之间存在强物理约束和接触约束关系。Moore^[5]通过使用Petri网，研究了DSP问题中的数学表达式与图论的关系。Gungor和Gupta^[6]等人提出了通过生成邻接矩阵与拆卸约束矩阵的方法来解决拆卸NP问题。Woo和Dutta^[7]提出了一种面向产品拆卸处理的拆卸树模型，这种方法的局限性在于其只能用于产品零件无依赖拆卸的情况，而在实际拆卸过程中，无依赖拆卸的情况基本上不存在，所以这种方法没有实际意义。Johnson^[8]对拆卸树模型进行了优化，以解决拆卸过程中面临的材料问题，使得拆卸材料的归类、并行操作变得简易，他通过几种工程属性权重构成的函数编写了一种评价方法。Taleb^[9,10]深入研究了大型废弃物，这种类型的废弃物具有大量零件而难以进行拆卸。Zahed^[11]将智能领域与DSP问题的求解相结合起来。Onosato、Iwata^[12]等人通过可视化研究，开发了一种智能软件，来评估从该产品中拆卸下某一零件的可能性。Feldman^[13]提出了基于几何拓扑序列的拆卸序列规则。Siddique^[14]为了定量评估拆卸的难度，他计算了拆卸能量和拆卸熵角度，并据此进行评估。Vujosevic^[15]通过分析产品维护过程以降低拆卸时间、减少拆卸成本和人力物力损耗，从而实现拆卸序列的优化。Rajit^[16]为了对产品进行复杂性和拆卸费用的分析评估，研究出了一款用于产品拆卸和维护的虚拟软件。Zhang^[17]等人提出了层次图理论，将复杂产品的拆卸问题转化为了简单的图论问题，为解决DSP问题提供了新途径。Zussman^[18]将优先权的概念引入了零件拆卸中，他将各个最小拆卸单元赋予相应的等级，在拆卸时遵循从高到低的原则来进行拆卸。江吉彬^[19]等人优化了图论的方法，将原本庞大的图分为一个一个小型节点图，能够减少节点从而避免组合爆炸问题。高建刚^[20]等人在机电领域进行了深入研究，建立了机电废弃产品的拆卸模型，并使用计算机模拟软件模拟出了所有可行的拆卸序列。刘继红^[21]等人使用智能算法对DSP问题进行了研究。

1.3 论文内容安排

全文的内容结构安排如下：

1. ，绪论。详细地阐述了为什么要研究DSP问题，意义为何，通过大量举例来展示了近年来不同学者对DSP问题的研究进度。
2. ，从不同方面对拆卸序列规划问题进行了剖析，从拆卸的意义、拆卸的分类、拆卸所需相关信息等方面对拆卸序列规划进行了总结。
3. ，在简单的介绍了应用广泛的拆卸约束图的基础上，通过加入各种工程属性并对其进行赋权，将拆卸约束图扩展为了拆卸混合图。
4. ，讲述了粒子群算法的基本原理，将粒子群算法与拆卸混合图对应起来，阐述了算法的具体流程，并规定了粒子适应度函数。
5. ，为了体现粒子群算法的优越性，通过以某机用虎钳作为范例，得出了其拆卸混合图，然后使用粒子群算法进行求解，比较了在不同迭代次数、种群规模条件下的结果。
6. ，对整篇文章的内容进行了梳理，然后对文中的不足之处进行了总结。

第2章 拆卸序列规划问题

拆卸序列规划是新世纪绿色再制造产业和材料回收的重要步骤，是指根据已有资源和条件对产品零件的拆卸步骤和先后顺序进行合理安排，以达到使用最少的人物力资源，在最短的时间内使用尽可能少及简单的拆卸方法，对产品进行符合预期的拆卸。拆卸过程中因产品零件接触类型、装配方法等条件的差异，会产生大量的拆卸相关信息，这些信息直接影响着拆卸序列，因此对拆卸问题进行研究是有必要的。

2.1 拆卸的概念与分类

2.1.1 拆卸的概念

拆卸是指通过产品的结构与装配关系等信息，通过手动或自动的方法，使用各种工具和不同的方法，将满足一定约束条件的零件分离出来的过程。拆卸的应用领域近年来越来越广泛，涉及到零部件的回收和再利用、产品维护、稀有金属回收等领域。