U型不完全多目标拆卸线平衡问题建模与优化

张则强 ，蒋 晋 ，尹 涛 ，许培玉

（1. 西南交通大学机械工程学院，四川 成都 610031；2. 西南交通大学轨道交通运维技术与装备四川省重点实验室，四川 成都 610031）

拆卸线是实现废旧机电产品规模化和自动化生产的重要组织方式，而如何提高拆卸效率和生产线平衡率，引起学者们的广泛关注，由此提出拆卸线平衡问题（disassembly line balancing problem，DLBP)[1].

关于DLBP问题的研究多集中于直线型DLBP问题优化[1-4]. 在实际的生产作业中，相较于直线型布局方式，最大的不同之处在于U型拆卸线在设计过程中可从前后双向搜索可分配作业任务，并可将首尾两个作业任务分配到同一个工作站. 此外，U型布局具有生产柔性强、占地面积小、效率高等特点[5].肖钦心等[6]考虑U型布局下拆卸过程存在的多种约束限制，以最小化拆卸节拍时间和工作站空闲时间指标为优化目标，采用改进的并行邻域搜索算法进行求解. 张则强等[7]提出一种Pareto蚁群遗传算法，对多目标U型拆卸线平衡问题进行协同优化，以弥补传统求解方法的不足. 拆卸作业过程中，由于部分零件存在需求性或危害性，需要后续相关处理操作，因此必须拆卸，其余零部件则可选择性进行拆卸，由此能节约成本，提高拆卸效率. Ren等[3]建立了以利润为导向的不完全拆卸线问题模型，并通过引力搜索算法求解. Bentaha等[4]利用AND/OR优先关系图，通过基于拉格朗日松弛和蒙特卡洛采样技术的求解方法，解决以利润为最高要求的不完全拆卸线平衡问题. 因此，本文综合考虑U型布局的柔性生产特点和不完全拆卸的高效性，提出U型不完全拆卸线平衡问题（U-shaped partial disassembly line balance problem，UPDLBP）.

对于DLBP问题的求解方法研究，Güngör等[8]首次证明DLBP是NP-hard问题，其解空间随着问题规模的增长呈指数增长，因此，数学规划方法[9-10]不适用于求解大规模DLBP. 而启发式算法[11-12]依赖启发式规则，采用先决策后优化的形式，将多目标转化为单目标进行计算，只能获得一个容易受决策者主观因素影响的解. 目前，群智能算法例如人工蜂群算法[13]、变邻域搜索算法[14]、蚁群算法[15]等由于全局寻优能力强和适用范围广等特点，在DLBP中得到广泛应用.

与其他算法相比，狼群算法（wolfpack algorithm，WPA)[16]受参数设置影响性较低，在求解速度和求解质量上更具优势. 本文提出一种自适应反向学习多目标狼群算法（adaptive opposition-based learning multiobjective wolfpack algorithm，AOBL-MWPA），通过对算法进行离散化操作，利用轮盘赌操作划分狼群；采用自适应游走行为，在迭代前期增强全局寻优能力，后期增强局部搜索能力，加强探狼间信息交互，其余人工狼通过奔袭行为和召唤行为向当前迭代次数的全局最优解靠拢；引入反向学习策略（oppositionbased learning，OBL)[17]避免算法陷入局部最优解；通过精英保留策略记录全局最优解，最后引入Pareto解集思想[18]和非支配排序遗传算法Ⅱ（non-dominated sorting genetic algorithm Ⅱ，NSGA-Ⅱ）拥挤距离机制[19]获得分布均匀的非劣解集.

1 U型不完全DLBP问题

1.1 问题描述

本文从实际角度出发，考虑采用U型布局和不完全拆卸方式，如图1所示，工人同时对U型入口侧和出口侧零部件进行拆卸，非必须拆卸的零部件直接进行粉碎处理，降低拆卸成本，提高拆卸效率.对UPDLBP展开研究，并作出以下假定：1） 待拆卸产品单一，且能保证长期供应不中断；2） 零部件完整，且拆卸作业时间为标准定值；3） 忽略任何突发情况；4） 为简化问题，不考虑工人行走、物料运输等其他因素影响.

图1 U型不完全拆卸线Fig. 1 U-shaped partial disassembly line

1.2 符号说明

i,j：任务编号，i,j= 1,2,···,N；

k：工作站编号，k= 1,2,···,K；

TC：拆卸节拍时间；

Tk：第k个工作站的实际工作时间；

ti：任务i作业时间；

hi：若任务i具有危害性，hi=1 ，否则hi=0；

di：若任务i具有需求性，di=1 ，否则di=0；

wk：若工作站k的拆卸任务集中存在危害性零部件，wk=1 ，否则wk=0；

Pij：若任务i为任务j的紧前任务，Pij=1，否则Pij=0. 优先关系矩阵P= (Pij)N×N；

Ci：任务i单位时间作业成本；

Ch：工作站单位时间附加无害化处理成本；

Cs：工作站单位时间待机成本；

xik：决策变量，若任务i分配到工作站k的入口侧，xik=1，否则xik= 0 ；

yik：决策变量，若任务i分配到工作站k的出口侧，yik=1，否则yik= 0；

Sk：决策变量，若开启工作站k，Sk=1，否则Sk=0 .

1.3 优化目标

实际DLBP问题中，决策者希望同时优化多个目标，既能保证企业的经济效益，降低企业成本，还能保证拆卸线的平衡性. 因此，本文考虑协同优化以下4个目标：最小化工作站数量f1、最小化空闲时间均衡指标f2、最小化拆卸深度f3及最小化拆卸成本f4，分别如式（1） ～ （4）所示，其中，拆卸成本由拆卸作业成本、工作站待机空闲成本及附加无害化处理成本三部分组成.

1.4 约束条件

约束条件包括节拍时间约束，任务分配约束，优先关系约束，需求、危害指标约束和工作约束.

节拍时间约束为

由于采用不完全拆卸方式，允许存在部分零部件不拆卸，但拆卸任务有且仅能分配到一个工作站.任务分配约束如式（6）所示.

采用U型布局形式，待拆卸零部件可在入口侧或出口侧进行拆卸，分别加以优先关系约束. 优先关系约束如式（7）所示.

具有危害属性和经济效益的零部件必须拆卸.需求、危害指标约束如式（8）所示.

需要开启的工作站存在理论上下阈值约束，且不允许开启空的工作站内无任务分配. 工位约束如式（9）、（10）所示.

2 AOBL-MWPA算法设计

本文结合DLBP实际问题特点，提出一种自适应反向学习多目标狼群算法进行求解计算，由于DLBP问题中需要优化多个存在一定制衡性的目标，很难同时达到最优值，因此考虑去除头狼作用，保留其他算法机制. 采用实数编码方式生成可行拆卸序列，通过对算法操作进行离散化操作，并引入反向学习策略跳出局部最优，通过Pareto解集和NSGA-Ⅱ拥挤距离机制评价非劣解集，引入精英保留策略加快算法向全局最优解靠拢.

2.1 编码及解码设计

在拆卸线设计过程中通过人工识别确定零部件的组成结构、拆卸作业时间、危害和需求属性等拆卸信息，并整合形成优先关系矩阵P和拆卸信息矩阵B，以便作为算法求解计算所能识别处理的问题参数输入，在满足特定约束条件下通过编码操作生成可行解，通过解码操作将拆卸任务合理分配到各工作站内并计算目标适应度值，为实现废旧产品的大规模拆卸奠定数据基础.

采用基于实数编码方式生成可行拆卸序列，将优先关系矩阵P中无紧前约束任务放入可选任务集中，随机挑选其中的一个任务i放入当前拆卸序列位置m中，将P中任务i所在行全部置为0，以释放对其他任务的约束关系，同时将任务i所在列全部置为1，以加强自身约束，保证不会重复选取到该任务，然后m=m+1，重复以上步骤，直至所有任务均分配完成，由此得到的实数序列即为可行拆卸序列.

由于在U型不完全拆卸过程中，并不是所有任务都需要进行拆卸，只要零部件存在需求性或危害性这两种特性中的其中一个，就必须要拆卸该零部件，但也会存在某一个零部件同时存在需求性与危害性的情况，在解码时仅需确保必须拆卸零部件总数满足要求即可，不会影响算法性能. 因此，将解码过程分为两个阶段，第一阶段是得到实际需要拆卸的任务序列，第二阶段是将所得的拆卸序列在满足所有约束情况下分配到工作站中，具体步骤如下：

步骤1输入可行拆卸序列X，计算拆卸产品中必须拆除的零部件总数Nnum，设置开启工作站序号ks=1，工作站空闲时间TR=TC，危害性或需求性零部件计数iex=1；

步骤2从解序列位置编号m= 1开始遍历X，若某位置m上的任务i∈{i|di+hi≥1}，则iex=iex+1；若iex=Nnum，则将对应位置编号m及之前的序列单独取出，作为新的不完全拆卸序列Yp输出，序列长度为l，解码第一阶段完成；

步骤3初始化序列位置编号，入口位置p=1，出口位置q=l；

步骤4判断位置p、q上的任务i、j的作业时间是否小于当前工作站空闲时间TR，若条件成立，则将满足条件的任务放入可分配任务集合S中；

步骤5确定可分配任务集合大小NS,num，若NS,num=0 ，则开启新的工作站ks=ks+1 ，重置空闲时间TR=TC；否则将拆卸作业时间较长的零部件作为待分配任务；

步骤6确定待分配任务的编号，若为i，则分配到入口侧，p=p+1 ；否则，分配到出口侧，q=q−1； 修改工作站剩余空闲时间TR=TR−ti；

步骤7重复步骤4～6，直至序列Yp中任务分配完毕.

2.2 “轮盘赌”选择操作

本文采用“轮盘赌”法进行种群划分，根据个体适应度值计算个体选择概率及累加概率选取As匹人工狼组成探狼群，具体计算如下：

式中：NW为种群规模；f(Xi)、p(Xi)分别为第i个个体Xi的适应度值和选择概率；P(Xi)为累加概率，其值越大，个体选中机率越大，由此选择探狼个体.

2.3 自适应游走行为

探狼在解空间内朝R个方向分别进行游走搜索猎物，根据猎物气味浓度（可认定为目标适应度值）自主决策前进方向，具体表示为

式中：xie,r为探狼i在第e（e= 1,2,···,E）维空间朝第r（r= 1,2,···,R）个方向前进后的位置；xie为探狼i在第e维空间的位置；sa为游走步长.

为了使算法在迭代前期扩大全局搜索寻优能力，同时在迭代后期有更大概率朝全局最优解靠拢，加强稳定性. 考虑随着迭代次数的增加，减少游走方向数R，加快算法收敛速度. 计算方法如下：

式中：Rmax、Rmin分别为游走方向数的最大、最小值；g为当前迭代次数；Mgen为算法最大迭代次数.

结合DLBP编码特点，设计一种基于随机扰动的自适应游走行为，产生若干邻域解，具体步骤如下：

步骤1输入拆卸序列X，设置游走次数kt= 1，游走方向计数r= 1，游走次数阈值为kt,max，根据式（13）计算游走方向数R；

步骤2生成表示序列位置的随机整数u（u∈{1,2,···,U})，确定u上的任务编号iask；

步骤3利用优先关系矩阵确定iask相邻的紧前任务Ptask和紧后任务Stask，将紧前紧后任务间的序列作为可操作序列片段Yo；

步骤4生成与序列Y相同长度的单调递增随机数组，将iask对应的随机数rnum按式（12）进行计算，并将随机数组按递增顺序重排，对应的iask位置发生变动，生成新的序列片段Z；

步骤5用序列片段Z代替Yo，放入序列X中，生成新的邻域解XNew并保存，更新游走方向计数r=r+1；

步骤6若r

步骤7若kt

2.4 召唤行为

结合DLBP实际特点，利用基于交叉操作接收召唤信息，并通过生成随机整数确定变异点，基于变异操作执行猛狼向头狼奔袭行为. 具体步骤如下：

步骤1输入探狼序列X，猛狼序列Y，生成两个表示序列位置的随机整数p、q；

步骤2确定序列Y中位置p、q间的序列片段Z，并遍历序列X，若某位置上的任务编号在序列Z中存在，则依次存放到新的序列片段ZNew中；

步骤3用ZNew替换Y中原拆卸序列片段Z，生成新的拆卸序列YNew1，完成召唤信息传递；

步骤4生成表示拆卸序列位置的随机整数m，确定YNew1中该位置的任务编号iask；

步骤5根据优先关系矩阵确定iask在YNew1中的相邻最近的紧前紧后任务位置a、b，将位置a和b之前的序列除去iask作为可操作序列，在其中随机插入iask，由此生成新的拆卸序列YNew2；

步骤6比较拆卸序列Y、YNew1及YNew2的适应度值，更新猛狼位置.

2.5 目标驱动围攻行为

为快速收敛，本文考虑将单个目标最优的人工狼作为驱动解按式（14）执行围攻行为，为算法每次的迭代寻优提供单目标参考值.

式中：λ为 [−1,1]间的随机数；sc为围攻步长；和分别为第k次迭代时人工狼与猎物在第e维空间所处位置.

步骤1计算交换序列对数ENum，生成ENum个不大于拆卸序列长度N的互不相等的随机整数，用以确定交换对位置集EPos；

步骤2根据EPos逐个确定G、xi对应位置上的任务交换对{GTask,xi,Task}；

步骤3基于DLBP实数编码的特点，同一任务有且仅能分配一次，因此确定GTask在拆卸序列xi中的位置，并交换序列对GTask与xi,Task的位置；

步骤4判断交换序列对位置后是否满足优先关系约束，条件成立的交换对如图2中实线表示的交换对{5,4}、{3,2}，将其予以保留，将不满足条件的如图2中虚线表示的交换对{10,7}舍弃.

图2 目标驱动围攻行为Fig. 2 Goal-driven besieging behavior

2.6 反向学习策略

反向学习策略[17]基本思想是为扩大种群搜索范围，基于当前个体在可行域范围内生成一个对应的反向解个体，比较两个个体的适应度值，选择较优的个体进入下一次迭代优化. 具体定义如下：设解Xi={xi1,xi2,···,xie}为e维空间中的一个可行解，xie为第e维空间的变量，其定义域为 [ae,be]，

式中：rn为 [0,1] 间的随机数.

在满足DLBP优先关系约束情况下，生成人工狼反向种群，从中挑选适应度值较优的人工狼替换原种群中较差的个体，保证种群的优越性.

2.7 多目标处理方法

由于DLBP问题涉及多个量纲不同的目标优化，不能简单的将其转化为单目标问题求解，同时缺少决策者的个人偏好等关键信息，需要采取先优化再决策的方式，因此考虑引入Pareto解集理论获得多个具有不同侧重点的非劣解.

对于最小化多目标优化问题，给定两个可行解X1、X2，其第w个目标适应度值分别为fw(X1)，fw(X2)，若满足式（16）则称解X1Pareto支配解X2，记为X1≺X2.

本文考虑采用基于外部档案的精英保留策略，将每次迭代寻优获得的Pareto解存放于外部档案中，并不断更新外部档案，使算法加速朝全局最优解收敛. 当非劣解个数超过设置的外部档案容量时，通过NSGA-Ⅱ拥挤距离机制[19]筛选去除部分非劣解.定义边界个体的拥挤距离为∞，其余解X对应的单目标值fw(X)分别按升序排列后，计算如式（17）所示.

式中：L(X)为解X的拥挤距离；Xg−1、Xg+1分别为X排序前、后的解.

2.8 算法流程

AOBL-MWPA具体算法流程如图3所示.

图3 BL-MWPA算法流程Fig. 3 AOBL-MWPA flowchart

3 算法性能验证和实例应用

在硬件配置为Intel(R) Core(TM) i5-9500 CPU，3.00 GHz主频，8.00 GB内存的计算机上，通过Win10系统上的MATLAB 2018开发算法程序. 为验证所以算法的性能，将其应用于不同规模的算例中求解计算，并与现有文献中的算法结果进行对比.

3.1 基准算例验证

通过文献[20]的19个基准算例来验证AOBLMWPA算法的性能，定义任务拆卸数量N为首项为8，公差为4，末项为80的一组等比数列，不考虑零部件间的优先关系约束，任务拆卸作业时间ti∈{3,5,7,11} ，节拍时间TC= 26 s，定义最后一个作业时间为11 s的任务为危害性零部件，最后一个作业时间为7 s的任务为需求零部件. 优化目标有：最小化工作站数量f1、最小化空闲时间均衡指标f2、最小化拆卸深度f3及最小化拆卸成本f4，同时附加计算求解时间进行对比说明. 现有文献中的求解算法有蚁群算法（ant colony optimization，ACO）[20]、改进蚁 群算法（improved ant colony optimization，IACO）[15]、多目标免疫机制协作遗传算法（multi-objective immune mechanism cooperative genetic algorithm，MIGA）[21]及变邻域搜索算法（variable neighborhood search，VNS）[14]. 通过正交试验设计确定算法参数，因篇幅问题不展开说明，从求解时间和求解质量两方面综合考虑，设置算法参数为NW= 60，Mgen=120，sa=1.5，kt,max= 8，计算对比结果如图4所示.

图4 19个基准算例对比结果Fig. 4 Comparison results of 19 benchmark instances

由基准算例的构造方法可得，真实Pareto前沿解最优结果为{N/4,0,1,2}或{N/4,0,2,1}. 通过对所提算法和现有文献求解结果的均值进行对比，在工作站数量f1和空闲时间均衡指标f2上，所提AOBLMWPA算法和MIGA算法在小规模（N≤20）上均能求解到最优解f1=N/4，f2= 0，但在中规模（20

3.2 实例应用

现以某型报废汽车为对象，分析AOBL-MWPA算法在U型不完全拆卸线方案规划中的应用情况.现获得的拆卸信息包括零部件拆卸作业时间t（s），危害属性h，需求属性d，单位时间作业成本C（元/s），具体如表1所示，优先关系如图5所示.

图5 某汽车拆卸优先关系Fig. 5 Disassembly precedence relations of a car

表1 某汽车拆卸信息Tab. 1 Disassembly information of a car

根据实际生产情况，设置其生产节拍TC= 640 s.经过正交试验测试计算，综合考虑算法求解精度和求解时间，确定算法参数为NW= 60，Mgen= 120，sa=1.5，Tmax= 8，外部档案大小NQ= 10. 算法运行求解10次，取其中较好的一次结果如表2所示，拆卸方案中带负号的编号零件表示该零件在U型出口侧进行拆卸作业，反之，则在U型入口侧进行拆卸作业. 通用工作站需要对入口侧与出口侧的产品进行拆卸作业，专用工作站只需对流水线某一侧待拆产品进行作业.

从表2结果看出，根据Pareto解集思想，所提算法能求解得到10个非劣解，开启的工作站数量均为9个，拆卸零部件数量为38个，空闲时间均衡指标变化范围为28.142 5～33.015 1 s，拆卸成本变化范围为381.946 4～387.954 9 元/s，因此决策者可根据实际情况选择合适的拆卸方案，若决策者注重空闲时间均衡指标可选用方案2，该优化目标为28.142 5 s；若决策者注重企业的拆卸成本，则可选择方案1，最小成本为381.946 4元/s.

表2 U型汽车拆卸线任务分配方案Tab. 2 Task allocation plan for U-shaped car disassembly line

4 结 论

1）本文结合企业实际情况，对U型不完全拆卸线平衡问题展开研究，构建了以最小化工作站数量，空闲时间均衡指标，拆卸深度和拆卸成本为优化目标的数学模型.

2）针对问题特点，设计一种自适应反向学习多目标狼群算法，为兼顾算法前期的全局搜索能力和后期的稳定性，提出改进的自适应游走行为，同时引入反向精英学习策略有效避免算法陷入局部最优解，利用Pareto解集思想和NSGA-Ⅱ拥挤距离筛选评价机制，实现不同侧重点的精英解集的保留，指导算法搜索寻优方向，同时加快算法收敛速度.

3）通过将所提算法应用于不同规模问题的19个基准算例，并与现有文献中的求解算法进行对比，结果表明所提算法在不同评价指标上的求解结果优于其他算法，验证了其求解性能更优. 最后，将所提算法应用于采用U型布局不完全拆卸方式的具有40项任务的某汽车拆卸实例中，求解获得10个Pareto非劣解，为决策者提供了广泛的决策空间，验证了所提算法和模型的正确性和有效性.

致谢：中车“十四五”科技重大专项课题（2021CHZ010-3）.