一种自适应人工蜂群算法求解U型顺序相依拆卸线平衡问题

王书伟， 郭秀萍， 刘 佳

(1.西南交通大学 经济管理学院，四川 成都 610031； 2.青岛理工大学 商学院，山东 青岛 266520)

0 引言

信息技术的革新与激烈的市场竞争，促使电子产品更新换代速度加快，而消费者不断变化的个性化需求，更是加剧了电子产品的淘汰速度。作为目前增速最快的一类固体垃圾，电子废弃物对人体和环境都具有较大危害，但同时也蕴藏着大量可回收利用资源，若能有效提取和利用将给社会带来巨大的经济和环境效益。因此，电子废弃物的回收再制造问题备受关注。

面对大规模废旧产品，为了提高拆卸效率，采用流水线作业方式已成为企业的最佳选择[1]，但通过流水线对废旧产品进行作业时，会发生零部件的作业任务分配不平衡问题。针对该问题，Gupta和Gungor[2,3]于2001年首次提出拆卸线平衡问题(DLBP)，并建立了DLBP数学优化模型。随后，一些启发式算法最先被应用到DLBP中以获取近似最优解，如：贪婪算法[4,5]、2-opt启发式算法[6]。启发式算法构造简单、求解速度快，但不具通用性且求解质量不高。因此，分段线性规划[7]、分支定界[8]、最短路径[9]和整数规划[10]等数学方法被用于求解DLBP以获得问题的精确解，但DLBP是NP-complete问题[11]，其无法应对大规模DLBP。因此，一些研究者将智能算法，如蚁群算法[12]、变邻域搜索算法[13]、人工鱼群算法[14]、人工蜂群算法[15]等应用于DLBP以获得问题的满意解。

以上研究的DLBP都是针对产品在直线型布局拆卸线进行作业，且零部件间仅考虑优先关系约束。然而，当面对回收数量不定，品种多样的产品拆卸时，拆卸线采用U型布局效率更高。针对拆卸时间不确定的多产品混流拆卸，Agrawal等[16]对随机混流U型DLBP进行了研究。以精益生产为准则，李明等[17]提出了多目标U型DLBP。对于一些结构复杂的产品，在拆卸时，部分零件之间虽然不存在拆卸优先关系，但也会相互干扰，妨碍对方的作业操作，从而导致零件作业时间增加，影响拆卸线平衡，此类问题被定义为顺序相依问题。Kalayci和Gupta[18]于2013年首次将顺序相依问题引入直线型DLBP中，提出了顺序相依拆卸线平衡问题(SDDLBP)。随后，Kalayci与其合作者[18～20]分别采用混合遗传算法、禁忌算法和人工蜂群算法求解直线型SDDLBP。

受信息技术快速革新的影响，电子废弃物的回收数量波动较大，且种类繁多、构造复杂。因此，分配更灵活、效率更高的U型线更适合用于废旧电子产品拆卸[21]。鉴于上述分析，本文针对拆卸线以U型模式布局，考虑拆卸过程中任务间的优先关系和顺序相依关系约束，构建了多目标U型顺序相依拆卸线平衡问题(USDDLBP)模型，并提出一种自适应人工蜂群算法(SAABC)。在局部搜索过程中采用了动态邻域搜索方法，以提高算法局部开发“Exploration”效率；在全局搜索过程中采用基于当前最优解的变异操作，以加速跳出局部最优，从而增强算法的探索“Exploitation”能力。

图1 产品任务关系图

1 问题描述与数学模型

图1为一个含有8个零部件产品任务关系图，圆内数字表示零件(任务)编号，圈外数字对应该零件的作业时间，实箭头为拆卸过程中零件之间的优先关系，灰色背景表示有危害零件。虚箭头为零件间的相互干扰，虚线上数字为干扰时间增量。通过图1可以看出，零件2/3、6/7之间无拆卸优先关系但存在顺序相依关系。以零件6/7拆卸为例，若零件6先于零件7拆卸，零件7将干扰零件6的作业操作，导致零件6实际拆卸作业时间增至8+1=9s(秒)，增量为1s；反之，若零件7在零件6之前拆卸，零件7作业时间将增加5s。

U型拆卸线是将工作站按“U”型排列，其布局更紧凑、更柔性，如图2所示。U型线入口与出口在同一端，拆卸时任务在满足优先关系约束前提下，可从前向、后向或双向分配至工作站。与直线型相比，U型线上任务分配更加灵活，因此，问题解规模更大。本文所提出的USDDLBP是在拆卸产品时，考虑零部件间的优先关系和顺序相依关系，在满足节拍时间条件下，将所有零部件的作业任务平衡分配到U型线所开启的工作站上，以满足相关目标需求。按照目标重要程度不同，由高到低依次考虑以下4个目标：

(1)最小化工作站开启数量。拆卸过程中所需工作站数量越少，产品拆卸固定成本也将越低。

(1)

式中zk为0-1变量，表示工作站k是否开启。

(2)最小化平滑指数。为保证拆卸线高效运行，应平衡各工作站空闲时间即作业负荷。

(2)

(3)尽早移除有危害零部件，以降低危害，如主板和键盘底片上的铍，电脑显示器阴极射线管荧屏上的钡，电路板中的溴化阻燃物等，该类有危害零部件应优先拆卸，以将危害降至最低。

(3)

式中PSl表示拆卸序列中第l个位置对应的零件编号，例如序列{1,5,2,3,6,7,4}，第2个位置PS2=5，hi为零件i的危害性，有危害则hi=1，否则hi=0。

(4)尽早拆卸需求高的零部件。价值高、需求大的零部件应优先拆卸，以满足市场需求。

(4)

式中di为零件i的需求量。

图2 U型布局拆卸线

2 自适应人工蜂群算法

Karaboga[22]在2005年首次提出人工蜂群算法，其包含雇佣蜂、观察蜂和侦察蜂三种角色蜜蜂，三者分工协作搜索蜜源，最终获得问题的(近似)最优解。ABC算法参数设置少、鲁棒性强、易于实现，已经广泛应用于多种优化问题，但也存在局部搜索效率较低、易早熟等缺陷。针对USDDLBP，本文提出一种自适应人工蜂群算法，从初始解生成、雇佣蜂局部开发、观察蜂跟随以及侦察蜂全局搜索等环节进行改进，以提高算法的搜索性能，具体实现如下。

2.1 编码与解码

为了更有效描述U型线可双向分配任务的特点，引入影子约束[23]至图1产品拆卸示例，如图3所示。从虚节点0开始，可向后在满足优先关系前提下分配任务至U型线入口工作站上，或向前满足影子关系前提下分配任务至U型线出口工作站上。USDDLBP是将零件的作业任务平衡分配至拆卸线所开启的工作站上，属于离散组合优化问题，针对其特点，采用一种整数排列编码方式。数字表示任务(零件)编号，正、负号分别表示作业任务从入口、出口分配至U型线，整数排列顺序表示任务拆卸前后顺序。以排列{1,-8,2,3,-6,-7,5,4}(正号省略)为例，其表示先将任务1从U型线入口分配，然后再从出口方向分配任务8，以此类推，直至所有任务拆卸完毕，其满足图1拆卸优先关系，是一个可行的拆卸方案。

表1 解码结果(CT=17s)

2.2 初始化种群

在ABC算法中，一个蜜源对应问题的一个可行解，且每个蜜源仅能被一个雇佣蜂或观察蜂开采，因此，蜜源数量(SN)与雇佣蜂、观察蜂数量一致。为了保证初始种群的生成质量与多样性，采用最大处理时间(LPT)启发式方法与单点左操作随机生成法相结合的初始化策略。LPT在任务选择分配时赋予作业时间最长的任务最高权重，即作业时间最长的任务将优先分配。单点左操作是在可行解序列上随机产生一点，该点左侧在满足优先关系前提下重新生成，右侧则不变(图4d)。在初始化种群时，首先通过LPT生成一个较高质量的初始解x，然后在x基础上通过单点左操作生成种群中其余的SN-1个解，具体生成过程如图4所示。

图4中的可选任务集C*根据引入影子约束的任务优先关系图进行构建。若任务i未分配，且其无前驱或前驱任务已经分配，则将+i添加到C*以表示入口任务；若任务j未分配，且其无后继或后继任务已经分配，则将-j添加到C*表示出口任务。可分配任务集A*是从C*中选择实际拆卸时间不超过当前工作站所剩余空闲时间的任务组成。

图3 引入影子约束的产品任务优先关系

图4 初始解生成过程

2.3 局部开发

步骤1初始化。确定邻域集Nk(k=1,…,K)，设置Sk(k=1,…,K)，选定初始解x。

步骤2邻域选择。根据自适应选择机制动态选择邻域结构k。

步骤3扰动。随机选择一点x′∈Nk(x)。

步骤4局部搜索。在x′邻域Nk(x′)的子集内进行局部搜索获得解x″。

步骤5更新最优解。若x″优于x，则x=x″，Sk=Sk+1。

步骤6重复步骤2～5，直至结束。

根据USDDLBP的问题特征和编码特点，选择由突变、逆序和插入三种邻域操作组成SADNS的邻域结构集(图5a～图5c)。

(1)突变操作。在可行解上选择一点，将该点上的任务符号变为其相反符号，然后重新分配。

(2)逆序操作。在可行解上随机选择两个位置，将两个位置间的任务逆序排列。

(3)插入操作。在可行解上选择两个位置i、j，将位置i的任务插入到位置j，然后将j至i-1间的任务向后依次移动。

图5 邻域结构

2.4 蜜源选择评价

在采蜜过程中，随着搜索的不断深入，雇佣蜂所寻得蜜源质量差异将逐渐缩小，因此无论选取哪一个目标函数作为适应值评价函数，观察蜂都不能在整个迭代过程中对蜜源进行有效评价。为了解决该问题，采用分段选择法，在迭代前期，选用平滑指数作为适应值评价函数，并以轮盘赌法选择雇佣蜂跟随[18,20]；随着迭代的深入，当所有雇佣蜂携带蜜源的平滑指数相同时，则以锦标赛法选择雇佣蜂跟随。观察蜂确定雇佣蜂跟随后，将采用与其相同的方法对蜜源进行深度开发。

2.5 全局探索

在搜索过程中，若蜜源经过upLimit次迭代后质量仍未提高则视为开发已尽将被丢弃(该蜜源所对应的解陷入局部最优)，此时，侦察蜂将在全局范围内探索新蜜源。USDDLBP是NP-complete问题，解空间通常是无界的，因此，在整个解空间随机探索新蜜源，效率低且不易跳出局部最优。而在搜索时，当前最优解的邻域周边往往蕴藏着更为丰富的蜜源，因此，对其周边邻域进行探索效率会更高。鉴于此，在该阶段，基于当前最优解采用单点右操作实现新蜜源的搜索(图4e)以加速跳出局部最优。

2.6 SAABC算法流程

所提算法采用启发式方法与随机生成法构造初始化种群。种群初始化后，雇佣蜂采用SADNS方法对蜜源周边进行开发；然后，观察蜂采用分段方式选择雇佣蜂跟随，并采用与其相同的方法继续开发蜜源；当蜜源开发完毕，侦察蜂采用基于当前最优解的变异操作探索新蜜源。三种角色蜜蜂分工协作，完成最优蜜源的搜索，算法流程如图6所示。

图6 SAABC算法流程

3 算例验证

为了有效测试所提算法的求解性能，采用一组基准算例和2个实例进行验证，同时与ABC[20]和PVNS[24]两种算法求解结果进行对比。所有测试均用C++编码，在Core I7-7500U 2.7Hz，8G内存电脑上运行。

3.1 基准测试

目前已发表文献中，尚无U型顺序相依问题基准测试算例，为了验证所提SAABC算法的有效性，在此设计了USDDLBP的一组基准算例。具体如下：算例规模(零件数量)分布在12到87之间，从由12个零件组成开始每次增加15，节拍时间设为26s(CT=26)。每个零件的拆卸时间由式(5)所得，其中拆卸第一个耗时7s的零件有危害，第一个耗时5s的零件有市场需求。零件之间的拆卸优先关系和顺序相依关系分别由式(6)和(7)确定。

为了有效比较，SAABC、ABC和PVNS三种算法均在相同的时间内求解每个算例。算例P12和P27求解时间为5s，P42和P57为25s，P72和P87为125s。每个算例求解25次，得到的最优解、均值和标准差如表2、表3所示。

(5)

(6)

(7)

对于算例P12和P27，二者解空间规模相对较小，ABC、PVNS和SAABC三种算法在指定时间内每次都可搜索到问题的最优解。然而随着问题规模增大，解空间呈指数增加，搜寻问题最优解变的愈加困难。对于P42算例，三种算法在25次求解中仅可寻得问题的近似最优解。通过表3可以看出，SAABC算法在工作站数量f1和平滑指数f2两个目标的平均值方面明显好于ABC和PVNS。虽然在标准差方面要比二者稍差，原因在于SAABC能够搜索到更多比ABC和PVNS两种算法更优的解(见表2)，从而导致其标准差波动略大，这也恰好说明SAABC具有更好的搜索性能。

随着问题规模的继续增加，对于P57、P72和P87三个算例，三种算法除了在P57和P87上的目标函数f1一致外，SAABC在目标函数f1、f2和f3的平均值与标准差上均优于ABC和PVNS，且优势显著。表明SAABC在25次求解中，解的波动性更小，稳定性更好，整体效果更佳。

此外，在所能搜索到的最优解方面，如表2所示，除了在算例P12和P27上三种算法均可搜索到问题最优解，以及在P57算例SAABC与PVNS最优解相同外，在其它算例上SAABC算法所能搜索到的最优解质量更高，体现出更强的寻优能力。

通过以上对比表明SAABC算法具备良好的寻优能力和更高的搜索稳定性，在求解USDDLBP过程中，可寻得USDDLBP更优解，在中大规模问题上其优越的搜索性能体现的更加充分。

表2 ABC、PVNS和SAABC求得最优解对比

3.2 实例分析

以含有10个零件的P10产品和25个零件的P25手机拆卸实例[24]为例，分别在U型和直线型拆卸线进行拆卸，采用所提SAABC算法进行求解，以获得最优拆卸方案。

对于P10实例，理论解空间为10！，规模较小，可搜索到问题最优解：f1=5，f2=61，f3=6，f4=8880，该最优解对应的拆卸方案如表4所示。图7(b)为此拆卸方案在U型线上各工作站的作业任务分配情况，在整个拆卸过程中，任务6对任务9、任务4对任务1和5、任务5对任务6、任务3对任务2造成了干扰，导致任务9、1、5、6、2的作业时间分别增加了3s、4s、4s、2s、3s。对于P25拆卸实例，相比于P10其解规模显著增大，算法在指定的100s内所能寻得问题的当前最优解为：f1=10，f2=9，f3=76，f4=909，所对应的拆卸任务方案如表4所示。

表4为直线型和U型两种布局下，拆卸P10和P25最优方案对比。在两种模式下所开启的工作站数量未发生变化。除了P10算例，采用U型布局的危害指数增加1以外，在平滑指数、危害指数和需求指数方面，U型布局均优于直线型布局。图7为P10实例在两种拆卸线布局模式下的最优序列作业任务分配情况对比，可以看出，U型线的布局设计更加柔性，可使拆卸任务更加灵活的在工作站上进行分配，因此U型布局通常比直线型布局具有更高的拆卸效率或更低的危害和需求指数。

表3 ABC、PVNS和SAABC求解基准算例均值、标准差对比

4 结论

在实际拆卸过程中，部分零部件之间会存在相互干扰，导致作业时间增加，从而影响拆卸线平衡，基于该现象，本文建立了U型SDDLBP多目标优化模型。通过求解不同规模算例和拆卸实例，验证了所提算法在求解USDDLBP的优越性。与直线型拆卸线相比，U型线布局更加灵活柔性，可使拆卸任务更合理的进行分配。

后续研究可针对拆卸过程中零部件作业时间的不确定，考虑大型产品双边拆卸，以及多产品类型混合拆卸，此外还有以利润等为目标的产品不完全或部分拆卸。

表4 U型和直线型布局结果对比