多目标件选择性拆卸序列规划数学模型

王菊梅　杨建新

摘 要：废旧汽车总体存量大、资源价值高，对其进行零部件回收拆卸，可以有效地减少环境污染以及资源浪费。选择性拆卸作为满足产品再制造，再利用的实用性环节，可实现废旧资源利用最大化。拆卸序列规划研究可以有效降低拆卸成本、提高效率，为拆卸过程提供具体科学有效的序列规划方案，避免拆卸的盲目性，因而逐渐受到愈加广泛的关注。由此，以合理、高效地拆卸废旧汽车中的零部件为目标件，研究面向多目标件的选择性拆卸序列规划问题。为满足序列的可行性，在保证各约束的前提下，提出了拆卸成本最小化的整数规划模型。最后基于GAMS平台进行了实例分析，验证了其可行性和实用性。

关键词：拆卸序列规划 选择性拆卸 多目标件

1 引言

随着制造业的快速发展，废旧汽车产品所带来的环境問题和其蕴含的经济价值，凸显了拆卸在理论研究和实践中的重要性。同时，复杂汽车产品的零部件数量呈指数形式增长，复杂度增加，如何以较低代价实现拆卸序列规划（Disassembly Sequence Planning，DSP）问题的快速求解已经成为了近年来的研究热点。

选择性拆卸（Selective DSP，SDSP）是指基于产品结构、装配关系、装配过程等信息，从产品上拆卸下一个或多个指定的零部件。在制造业中面向再制造和再利用的目标拆卸是一种选择性拆卸，其快速高效地获取拆卸序列是现今大多数学者的研究重点[1]。薛俊芳等[2]基于拆卸有向图，使用时间乘以拆卸复杂度作为有向图权重，并通过优化有向图模型的路径得到了目标件的最优拆卸序列;张秀芬等[3]针对局部破坏情况，重建拆卸加权混合图模型，结合图模型和几何推理得到了拆卸序列;赵树恩等[4]基于Petri网建立了拆卸模型，通过求解Petri网获得拆卸序列;王昊等[5]基于层次关系和关联关系建模，并且引入跳跃拆卸路径的概念进行了完善和优化。Ziqiang Zhang等[6]定义了重构混合EOL产品图规则来获取选择性拆卸序列;郭希旺等[7]考虑了零部件之间的相互依赖关系约束，建立了以最小拆卸时间和最大拆卸收益为目标的多目标优化模型;邢宇飞等[8]提出利用拆卸邻接矩阵推导拆卸的可行条件，实现了拆卸序列的优化;崔永等[9]通过了CAD设计信息建立了节点间的邻接矩阵来获得拆卸序列。

综合以上的研究现状，学者们各自虽然都取得了阶段性的成果，但在废旧汽车零部件产品DSP问题的求解中仍存在着一些不足之处：大多数的研究还是处在完全拆卸（Complete DSP，CDSP）和部分拆卸（Partial DSP，PDSP）上，针对SDSP的数学建模求解准确度不尽人意。

本文深入挖掘目标零部件相关信息，优化拆卸效率，旨在合理、高效地拆卸回收零部件，最大限度地降低回收成本，最大化资源的可持续利用。

2 拆卸信息模型构建

在建立产品CAD模型之后，可通过人机交互的方式由模型中的装配关系得出零件和约束关系。连接关系是指零件间的拆卸邻接关系，如两零件之间通过螺纹、螺钉、焊接等等连接;拆卸优先关系是指零件间拆卸的先后顺序（包括接触约束和非接触约束）。本文主要结合人工推导，从产品和零部件的三维模型中直接提取零部件配合约束等装配相关的信息。

混合图是图论中具有最基本表现形式的信息模型，主要由非空节点集合P、无向边集合E和有向边PE这个三元组构成，本文对于拆卸关系混合图表示为：EG={P，E，PE}。其中，P={p1，p2，…，pn}是零件集合，n表示产品中零件的个数;E={e1，e2，…，em}是无向边集合，m表示产品零件间连接关系的总个数;PE={pe1， pe2，…，pez}是有向边集合，z表示零件间空间约束的总个数。由于给边赋予了方向，那么对于有向边pez将与两个相关联的节点产生有序偶peij。

本文考虑了各零部件间的接触和非接触几何空间约束，从中读取零件和连接关系，生成节点与约束信息，据此构建混合图EG。基于混合图，EG可分解为连接关系图Ge={P，E}和优先关系图Gpe={P， PE}，可以直观地观察出待零件间的连接关系和拆卸优先关系。

如果有向边peij存在，采用gij（PE）（i=1，2，…，n;j=1，2，…，n）表示元素的拆卸约束，gij（PE）=1，即零件i优先于零件j拆卸;如果有向边peij不存在，则gij（PE）=0，即零件i、j之间不存在优先关系。即

（1）

如果无向边eij存在，采用gij（E）（i=1，2，…，n;j=1，2，…，n）表示元素的连接关系，gij（E）=1，即零件i与零件j连接;如果无向边eij不存在，则gij（E）=0，即零件i和零件j之间不存在连接关系。即

（2）

3 数学模型的构建

SDSP问题是根据建立的信息模型，生成满足拆卸约束的最优目标拆卸的离散组合优化问题。本节作为以往CDSP研究的延伸，考虑获取多个目标零件的情况。同时，为满足拆卸实际的生产需求，本文以最小拆卸成本作为优化拆卸序列的评价指标，建立了多目标件选择性拆卸序列规划模型，

3.1 模型假设

为便于求解，需要对问题进行一定的简化处理，考虑了如下假设：

1）拆卸顺序表示为拆卸任务（零件）的顺序，当进行一次拆卸操作，要保证从产品中拆除一个零件或组件，一次移除多个零部件视为非法操作。

2）待拆卸零部件均作为刚体，整个拆卸过程中不会产生受损或变形;紧固件等认为是拆卸约束和消耗品，忽略其剩余价值。

3）当某一零件拆卸操作完成，不会引起装配体结构的不稳定，其它相关联零件位置也不会发生变化。

4）任务的基本操作时间、基本操作成本已知。在拆卸的过程中采取非破坏性的拆卸方式，尽可能地保证零部件的完整性，以期拆卸后得到零部件的质量和效益。

3.2 符号说明

根据上节对拆卸信息模型的构建，分析了拆卸过程的相关信息和考虑了连接关系和优先关系的拆卸约束信息。其符号说明如下：

集合：

N：产品拆卸零件（操作）数集合，其中N={i=1，2，…，n}，n为零件数;

O：目标零件集合，其中O={o1，o2，…}。

参数：

i，j，k：零件号;

dij：零件i和零件j的优先关系;

ti：零件i的基本拆卸时间;

Tij：零件i和零件j的拆卸工具转换时间;

Dij：零件i和零件j的拆卸方向转换时间;

ci：零件i的基本拆卸成本;

rij：零件i和零件j的辅助拆卸成本;

max：一个极大数。

0-1变量：

xij：如果i和j都拆卸且i在j前拆卸，则xij为1，否则为0;

yi：如果零件i被拆卸，则yi為1，否则为0;

hij：如果i和j都被拆卸，则hij为1，否则为0。

连续变量：

Si：零件i拆卸的开始时间。

3.3 模型建立

拆卸成本是拆卸序列规划问题中的重要指标，也是企业在拆卸实践中的重要需求，其目标函数如下。

（3）

式（3）表示了拆卸成本主要包含了基本拆卸成本和辅助拆卸成本。

（4）

式（4）表示了拆卸目标为最小化最大拆卸成本。拆卸成本越低，拆卸回收效益越好。为保证拆卸序列的可行性，还需要满足下面的约束条件：

1） 拆卸优先关系约束

（5）

式（5）表示拆卸零件（操作）的优先关系，零件i是j的前序，当前序进行了拆卸操作，后续才可能进行拆卸。

（6）

（7）

式（6）和（7）表示拆卸零件（操作）的优先关系，当零件i是零件j的操作前序，零件j不能在零件i前面进行拆卸。当零件i和零件j都拆卸且i在j前拆卸，则xij、yi和yj都为1，xji为0，等号成立;反之，不等号成立。

（8）

式（8）保证了序列中所有拆卸操作必须满足优先关系约束，且不能形成“闭环”关系。

（9）

式（9）表示拆卸零件（操作）的优先关系，当零件i和零件j都进行拆卸且i在j前拆卸，xij、yi、yj和dij都为1，等号成立;反之，不等号成立。

2）拆卸操作分配约束：

（10）

（11）

式（10）和（11）表示了当零件i或j有一个未被分配进行拆卸操作，则不能满足hij为1，即零件i或j都被拆。

（12）

式（12）表示了当零件i和j都被分配进行拆卸操作，则满足hij为1，即零件i或j都被拆。

（13）

式（13）确保了所有的目标零件都必须进行拆卸操作。

（14）

（15）

式（14）和（15）表示对两个决策变量进行线性化处理，当零件i和j都被分配进行拆卸，xij或xji才能成立。

3） 时间关系约束：

（16）

式（16）表示了只有在前序零件已经被拆卸完成才能开始下一个零件的拆卸操作。

公式（3）-（16）共同构成了多目标件选择性拆卸序列规划的数学模型。

4 实例研究

为了验证所提出方法的可行性及有效性，本文实例分析主要选自于文献[10]所示案例，如图1所示。同时针对该装配体搜集了拆卸相关信息，其中优先关系、拆卸成本等基本拆卸相关信息如表1所示。该装配体主要包含了21个零件，2号和11号零件是目标零件。

1.泵盖分部件2.主动轴分部件3.螺栓M8（s） 4.垫圈中Φ8（s） 5.调整垫片6.半圆键（s） 7.销Φ3.2（s） 8.螺母M14（s） 9.垫圈Φ14（s） 10.齿轮11.泵体分部件12.销A5（s） 13.中间泵壳14.固定轴15.调整垫片（同5） 16.销A5（s） 17.从动齿轮分部件18.盖板19.垫圈中Φ6（s） 20.螺栓M6（s） 21.垫片，其中标有s的是标准件。

根据前面拆卸信息模型的构建方法，其混合图EG如图2所示。

通常，拆卸时间与拆卸成本成正相关，本文假定其拆卸辅助成本是拆卸工具变换时间的0.1倍。其拆卸工具转换时间如表2所示。

在GAMS平台上通过开发模型求解程序。根据拆卸信息，拆卸序列结果如表3所示。从展示的结果可以看出最佳解决方案不止一个，这是因为复杂产品，存在很多同等拆卸优先关系和拆卸成本的零件，在拆卸过程中选择有多个，只要拆卸条件满足即可。

5 结论

针对回收再制造、再利用领域的拆卸序列规划问题，本文通过分析国内外现有的研究成果，考虑实际生产过程中的需求，建立了最小化拆卸成本下的多目标件拆卸序列规划数学模型，同时基于GAMS平台求解得出可行性方案，求解效率高。实践证明，该方法能够快速地得到具有工程实践意义的最优拆卸序列。

基金项目：广安职业技术学院2021年度校级科研项目（GAZYKY-2021B06）

广安职业技术学院2020年度校级科研项目（GAZYKY-2020A06）。

参考文献：

[1]赖霞虹. 产品再制造拆卸规划方法与零件再制造性评估方法的研究[D]. 浙江大学， 2012.

[2]薛俊芳， 张新建， 张英利. 基于Floyd 算法的目标拆卸序列优化[J]. 现代制造工程， 2014（2）：83-87.

[3]张秀芬， 张树有. 基于粒子群算法的产品拆卸序列规划方法[J]. 计算机集成制造系统， 2009， 15（3）：508-514.

[4]赵树恩， 李玉玲. 模糊推理Petri网及其在产品拆卸序列决策中的应用[J]. 控制与决策， 2005， 20（10）：1181-1184.

[5]王昊， 曾鸿， 张均东，等. 基于目标拆卸的虚拟拆装过程建模[J]. 图学学报， 2015， 36（6）：903-908.

[6]Ziqiang Z， Guohong D， Xiangyan Z， et al. Research of Partial Destructive based Selective Disassembly Sequence Planning[J]. The Open Mechanical Engineering Journal， 2015， 9： 605-612.

[7]郭希旺， 刘士新， 王大志. 多目标选择性拆卸序列优化问题的分散搜索算法[J]. 系统工程学报， 2016， 31（3）：307-316.

[8]邢宇飞， 王成恩， 柳强. 基于Pareto解集蚁群算法的拆卸序列规划[J]. 机械工程学报， 2012， 48（9）：186-192.

[9]崔永， 赵良才. 基于相似线索二叉树的汽车零部件拆卸序列生成及其回收模糊评价[J]. 现代制造工程， 2007（2）：66-70.

[10]周开俊， 李东波. 基于遗传模拟退火算法的产品装配序列规划方法[J]. 计算机集成制造系统， 2006， 12（7）：1037-1041.