一種自適應(yīng)人工蜂群算法求解U型順序相依拆卸線平衡問題

王書偉， 郭秀萍， 劉 佳

(1.西南交通大學 經(jīng)濟管理學院，四川 成都 610031； 2.青島理工大學 商學院，山東 青島 266520)

0 引言

信息技術(shù)的革新與激烈的市場競爭，促使電子產(chǎn)品更新?lián)Q代速度加快，而消費者不斷變化的個性化需求，更是加劇了電子產(chǎn)品的淘汰速度。作為目前增速最快的一類固體垃圾，電子廢棄物對人體和環(huán)境都具有較大危害，但同時也蘊藏著大量可回收利用資源，若能有效提取和利用將給社會帶來巨大的經(jīng)濟和環(huán)境效益。因此，電子廢棄物的回收再制造問題備受關(guān)注。

面對大規(guī)模廢舊產(chǎn)品，為了提高拆卸效率，采用流水線作業(yè)方式已成為企業(yè)的最佳選擇[1]，但通過流水線對廢舊產(chǎn)品進行作業(yè)時，會發(fā)生零部件的作業(yè)任務(wù)分配不平衡問題。針對該問題，Gupta和Gungor[2,3]于2001年首次提出拆卸線平衡問題(DLBP)，并建立了DLBP數(shù)學優(yōu)化模型。隨后，一些啟發(fā)式算法最先被應(yīng)用到DLBP中以獲取近似最優(yōu)解，如：貪婪算法[4,5]、2-opt啟發(fā)式算法[6]。啟發(fā)式算法構(gòu)造簡單、求解速度快，但不具通用性且求解質(zhì)量不高。因此，分段線性規(guī)劃[7]、分支定界[8]、最短路徑[9]和整數(shù)規(guī)劃[10]等數(shù)學方法被用于求解DLBP以獲得問題的精確解，但DLBP是NP-complete問題[11]，其無法應(yīng)對大規(guī)模DLBP。因此，一些研究者將智能算法，如蟻群算法[12]、變鄰域搜索算法[13]、人工魚群算法[14]、人工蜂群算法[15]等應(yīng)用于DLBP以獲得問題的滿意解。

以上研究的DLBP都是針對產(chǎn)品在直線型布局拆卸線進行作業(yè)，且零部件間僅考慮優(yōu)先關(guān)系約束。然而，當面對回收數(shù)量不定，品種多樣的產(chǎn)品拆卸時，拆卸線采用U型布局效率更高。針對拆卸時間不確定的多產(chǎn)品混流拆卸，Agrawal等[16]對隨機混流U型DLBP進行了研究。以精益生產(chǎn)為準則，李明等[17]提出了多目標U型DLBP。對于一些結(jié)構(gòu)復(fù)雜的產(chǎn)品，在拆卸時，部分零件之間雖然不存在拆卸優(yōu)先關(guān)系，但也會相互干擾，妨礙對方的作業(yè)操作，從而導(dǎo)致零件作業(yè)時間增加，影響拆卸線平衡，此類問題被定義為順序相依問題。Kalayci和Gupta[18]于2013年首次將順序相依問題引入直線型DLBP中，提出了順序相依拆卸線平衡問題(SDDLBP)。隨后，Kalayci與其合作者[18～20]分別采用混合遺傳算法、禁忌算法和人工蜂群算法求解直線型SDDLBP。

受信息技術(shù)快速革新的影響，電子廢棄物的回收數(shù)量波動較大，且種類繁多、構(gòu)造復(fù)雜。因此，分配更靈活、效率更高的U型線更適合用于廢舊電子產(chǎn)品拆卸[21]。鑒于上述分析，本文針對拆卸線以U型模式布局，考慮拆卸過程中任務(wù)間的優(yōu)先關(guān)系和順序相依關(guān)系約束，構(gòu)建了多目標U型順序相依拆卸線平衡問題(USDDLBP)模型，并提出一種自適應(yīng)人工蜂群算法(SAABC)。在局部搜索過程中采用了動態(tài)鄰域搜索方法，以提高算法局部開發(fā)“Exploration”效率；在全局搜索過程中采用基于當前最優(yōu)解的變異操作，以加速跳出局部最優(yōu)，從而增強算法的探索“Exploitation”能力。

圖1 產(chǎn)品任務(wù)關(guān)系圖

1 問題描述與數(shù)學模型

圖1為一個含有8個零部件產(chǎn)品任務(wù)關(guān)系圖，圓內(nèi)數(shù)字表示零件(任務(wù))編號，圈外數(shù)字對應(yīng)該零件的作業(yè)時間，實箭頭為拆卸過程中零件之間的優(yōu)先關(guān)系，灰色背景表示有危害零件。虛箭頭為零件間的相互干擾，虛線上數(shù)字為干擾時間增量。通過圖1可以看出，零件2/3、6/7之間無拆卸優(yōu)先關(guān)系但存在順序相依關(guān)系。以零件6/7拆卸為例，若零件6先于零件7拆卸，零件7將干擾零件6的作業(yè)操作，導(dǎo)致零件6實際拆卸作業(yè)時間增至8+1=9s(秒)，增量為1s；反之，若零件7在零件6之前拆卸，零件7作業(yè)時間將增加5s。

U型拆卸線是將工作站按“U”型排列，其布局更緊湊、更柔性，如圖2所示。U型線入口與出口在同一端，拆卸時任務(wù)在滿足優(yōu)先關(guān)系約束前提下，可從前向、后向或雙向分配至工作站。與直線型相比，U型線上任務(wù)分配更加靈活，因此，問題解規(guī)模更大。本文所提出的USDDLBP是在拆卸產(chǎn)品時，考慮零部件間的優(yōu)先關(guān)系和順序相依關(guān)系，在滿足節(jié)拍時間條件下，將所有零部件的作業(yè)任務(wù)平衡分配到U型線所開啟的工作站上，以滿足相關(guān)目標需求。按照目標重要程度不同，由高到低依次考慮以下4個目標：

(1)最小化工作站開啟數(shù)量。拆卸過程中所需工作站數(shù)量越少，產(chǎn)品拆卸固定成本也將越低。

(1)

式中zk為0-1變量，表示工作站k是否開啟。

(2)最小化平滑指數(shù)。為保證拆卸線高效運行，應(yīng)平衡各工作站空閑時間即作業(yè)負荷。

(2)

(3)盡早移除有危害零部件，以降低危害，如主板和鍵盤底片上的鈹，電腦顯示器陰極射線管熒屏上的鋇，電路板中的溴化阻燃物等，該類有危害零部件應(yīng)優(yōu)先拆卸，以將危害降至最低。

(3)

式中PSl表示拆卸序列中第l個位置對應(yīng)的零件編號，例如序列{1,5,2,3,6,7,4}，第2個位置PS2=5，hi為零件i的危害性，有危害則hi=1，否則hi=0。

(4)盡早拆卸需求高的零部件。價值高、需求大的零部件應(yīng)優(yōu)先拆卸，以滿足市場需求。

(4)

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

圖2 U型布局拆卸線

2 自適應(yīng)人工蜂群算法

Karaboga[22]在2005年首次提出人工蜂群算法，其包含雇傭蜂、觀察蜂和偵察蜂三種角色蜜蜂，三者分工協(xié)作搜索蜜源，最終獲得問題的(近似)最優(yōu)解。ABC算法參數(shù)設(shè)置少、魯棒性強、易于實現(xiàn)，已經(jīng)廣泛應(yīng)用于多種優(yōu)化問題，但也存在局部搜索效率較低、易早熟等缺陷。針對USDDLBP，本文提出一種自適應(yīng)人工蜂群算法，從初始解生成、雇傭蜂局部開發(fā)、觀察蜂跟隨以及偵察蜂全局搜索等環(huán)節(jié)進行改進，以提高算法的搜索性能，具體實現(xiàn)如下。

2.1 編碼與解碼

為了更有效描述U型線可雙向分配任務(wù)的特點，引入影子約束[23]至圖1產(chǎn)品拆卸示例，如圖3所示。從虛節(jié)點0開始，可向后在滿足優(yōu)先關(guān)系前提下分配任務(wù)至U型線入口工作站上，或向前滿足影子關(guān)系前提下分配任務(wù)至U型線出口工作站上。USDDLBP是將零件的作業(yè)任務(wù)平衡分配至拆卸線所開啟的工作站上，屬于離散組合優(yōu)化問題，針對其特點，采用一種整數(shù)排列編碼方式。數(shù)字表示任務(wù)(零件)編號，正、負號分別表示作業(yè)任務(wù)從入口、出口分配至U型線，整數(shù)排列順序表示任務(wù)拆卸前后順序。以排列{1,-8,2,3,-6,-7,5,4}(正號省略)為例，其表示先將任務(wù)1從U型線入口分配，然后再從出口方向分配任務(wù)8，以此類推，直至所有任務(wù)拆卸完畢，其滿足圖1拆卸優(yōu)先關(guān)系，是一個可行的拆卸方案。

表1 解碼結(jié)果(CT=17s)

2.2 初始化種群

在ABC算法中，一個蜜源對應(yīng)問題的一個可行解，且每個蜜源僅能被一個雇傭蜂或觀察蜂開采，因此，蜜源數(shù)量(SN)與雇傭蜂、觀察蜂數(shù)量一致。為了保證初始種群的生成質(zhì)量與多樣性，采用最大處理時間(LPT)啟發(fā)式方法與單點左操作隨機生成法相結(jié)合的初始化策略。LPT在任務(wù)選擇分配時賦予作業(yè)時間最長的任務(wù)最高權(quán)重，即作業(yè)時間最長的任務(wù)將優(yōu)先分配。單點左操作是在可行解序列上隨機產(chǎn)生一點，該點左側(cè)在滿足優(yōu)先關(guān)系前提下重新生成，右側(cè)則不變(圖4d)。在初始化種群時，首先通過LPT生成一個較高質(zhì)量的初始解x，然后在x基礎(chǔ)上通過單點左操作生成種群中其余的SN-1個解，具體生成過程如圖4所示。

圖4中的可選任務(wù)集C*根據(jù)引入影子約束的任務(wù)優(yōu)先關(guān)系圖進行構(gòu)建。若任務(wù)i未分配，且其無前驅(qū)或前驅(qū)任務(wù)已經(jīng)分配，則將+i添加到C*以表示入口任務(wù)；若任務(wù)j未分配，且其無后繼或后繼任務(wù)已經(jīng)分配，則將-j添加到C*表示出口任務(wù)?？煞峙淙蝿?wù)集A*是從C*中選擇實際拆卸時間不超過當前工作站所剩余空閑時間的任務(wù)組成。

圖3 引入影子約束的產(chǎn)品任務(wù)優(yōu)先關(guān)系

圖4 初始解生成過程

2.3 局部開發(fā)

步驟1初始化。確定鄰域集Nk(k=1,…,K)，設(shè)置Sk(k=1,…,K)，選定初始解x。

步驟2鄰域選擇。根據(jù)自適應(yīng)選擇機制動態(tài)選擇鄰域結(jié)構(gòu)k。

步驟3擾動。隨機選擇一點x′∈Nk(x)。

步驟4局部搜索。在x′鄰域Nk(x′)的子集內(nèi)進行局部搜索獲得解x″。

步驟5更新最優(yōu)解。若x″優(yōu)于x，則x=x″，Sk=Sk+1。

步驟6重復(fù)步驟2～5，直至結(jié)束。

根據(jù)USDDLBP的問題特征和編碼特點，選擇由突變、逆序和插入三種鄰域操作組成SADNS的鄰域結(jié)構(gòu)集(圖5a～圖5c)。

(1)突變操作。在可行解上選擇一點，將該點上的任務(wù)符號變?yōu)槠湎喾捶?，然后重新分配?/p>

(2)逆序操作。在可行解上隨機選擇兩個位置，將兩個位置間的任務(wù)逆序排列。

(3)插入操作。在可行解上選擇兩個位置i、j，將位置i的任務(wù)插入到位置j，然后將j至i-1間的任務(wù)向后依次移動。

圖5 鄰域結(jié)構(gòu)

2.4 蜜源選擇評價

在采蜜過程中，隨著搜索的不斷深入，雇傭蜂所尋得蜜源質(zhì)量差異將逐漸縮小，因此無論選取哪一個目標函數(shù)作為適應(yīng)值評價函數(shù)，觀察蜂都不能在整個迭代過程中對蜜源進行有效評價。為了解決該問題，采用分段選擇法，在迭代前期，選用平滑指數(shù)作為適應(yīng)值評價函數(shù)，并以輪盤賭法選擇雇傭蜂跟隨[18,20]；隨著迭代的深入，當所有雇傭蜂攜帶蜜源的平滑指數(shù)相同時，則以錦標賽法選擇雇傭蜂跟隨。觀察蜂確定雇傭蜂跟隨后，將采用與其相同的方法對蜜源進行深度開發(fā)。

2.5 全局探索

在搜索過程中，若蜜源經(jīng)過upLimit次迭代后質(zhì)量仍未提高則視為開發(fā)已盡將被丟棄(該蜜源所對應(yīng)的解陷入局部最優(yōu))，此時，偵察蜂將在全局范圍內(nèi)探索新蜜源。USDDLBP是NP-complete問題，解空間通常是無界的，因此，在整個解空間隨機探索新蜜源，效率低且不易跳出局部最優(yōu)。而在搜索時，當前最優(yōu)解的鄰域周邊往往蘊藏著更為豐富的蜜源，因此，對其周邊鄰域進行探索效率會更高。鑒于此，在該階段，基于當前最優(yōu)解采用單點右操作實現(xiàn)新蜜源的搜索(圖4e)以加速跳出局部最優(yōu)。

2.6 SAABC算法流程

所提算法采用啟發(fā)式方法與隨機生成法構(gòu)造初始化種群。種群初始化后，雇傭蜂采用SADNS方法對蜜源周邊進行開發(fā)；然后，觀察蜂采用分段方式選擇雇傭蜂跟隨，并采用與其相同的方法繼續(xù)開發(fā)蜜源；當蜜源開發(fā)完畢，偵察蜂采用基于當前最優(yōu)解的變異操作探索新蜜源。三種角色蜜蜂分工協(xié)作，完成最優(yōu)蜜源的搜索，算法流程如圖6所示。

圖6 SAABC算法流程

3 算例驗證

為了有效測試所提算法的求解性能，采用一組基準算例和2個實例進行驗證，同時與ABC[20]和PVNS[24]兩種算法求解結(jié)果進行對比。所有測試均用C++編碼，在Core I7-7500U 2.7Hz，8G內(nèi)存電腦上運行。

3.1 基準測試

目前已發(fā)表文獻中，尚無U型順序相依問題基準測試算例，為了驗證所提SAABC算法的有效性，在此設(shè)計了USDDLBP的一組基準算例。具體如下：算例規(guī)模(零件數(shù)量)分布在12到87之間，從由12個零件組成開始每次增加15，節(jié)拍時間設(shè)為26s(CT=26)。每個零件的拆卸時間由式(5)所得，其中拆卸第一個耗時7s的零件有危害，第一個耗時5s的零件有市場需求。零件之間的拆卸優(yōu)先關(guān)系和順序相依關(guān)系分別由式(6)和(7)確定。

為了有效比較，SAABC、ABC和PVNS三種算法均在相同的時間內(nèi)求解每個算例。算例P12和P27求解時間為5s，P42和P57為25s，P72和P87為125s。每個算例求解25次，得到的最優(yōu)解、均值和標準差如表2、表3所示。

(5)

(6)

(7)

對于算例P12和P27，二者解空間規(guī)模相對較小，ABC、PVNS和SAABC三種算法在指定時間內(nèi)每次都可搜索到問題的最優(yōu)解。然而隨著問題規(guī)模增大，解空間呈指數(shù)增加，搜尋問題最優(yōu)解變的愈加困難。對于P42算例，三種算法在25次求解中僅可尋得問題的近似最優(yōu)解。通過表3可以看出，SAABC算法在工作站數(shù)量f1和平滑指數(shù)f2兩個目標的平均值方面明顯好于ABC和PVNS。雖然在標準差方面要比二者稍差，原因在于SAABC能夠搜索到更多比ABC和PVNS兩種算法更優(yōu)的解(見表2)，從而導(dǎo)致其標準差波動略大，這也恰好說明SAABC具有更好的搜索性能。

隨著問題規(guī)模的繼續(xù)增加，對于P57、P72和P87三個算例，三種算法除了在P57和P87上的目標函數(shù)f1一致外，SAABC在目標函數(shù)f1、f2和f3的平均值與標準差上均優(yōu)于ABC和PVNS，且優(yōu)勢顯著。表明SAABC在25次求解中，解的波動性更小，穩(wěn)定性更好，整體效果更佳。

此外，在所能搜索到的最優(yōu)解方面，如表2所示，除了在算例P12和P27上三種算法均可搜索到問題最優(yōu)解，以及在P57算例SAABC與PVNS最優(yōu)解相同外，在其它算例上SAABC算法所能搜索到的最優(yōu)解質(zhì)量更高，體現(xiàn)出更強的尋優(yōu)能力。

通過以上對比表明SAABC算法具備良好的尋優(yōu)能力和更高的搜索穩(wěn)定性，在求解USDDLBP過程中，可尋得USDDLBP更優(yōu)解，在中大規(guī)模問題上其優(yōu)越的搜索性能體現(xiàn)的更加充分。

表2 ABC、PVNS和SAABC求得最優(yōu)解對比

3.2 實例分析

以含有10個零件的P10產(chǎn)品和25個零件的P25手機拆卸實例[24]為例，分別在U型和直線型拆卸線進行拆卸，采用所提SAABC算法進行求解，以獲得最優(yōu)拆卸方案。

對于P10實例，理論解空間為10！，規(guī)模較小，可搜索到問題最優(yōu)解：f1=5，f2=61，f3=6，f4=8880，該最優(yōu)解對應(yīng)的拆卸方案如表4所示。圖7(b)為此拆卸方案在U型線上各工作站的作業(yè)任務(wù)分配情況，在整個拆卸過程中，任務(wù)6對任務(wù)9、任務(wù)4對任務(wù)1和5、任務(wù)5對任務(wù)6、任務(wù)3對任務(wù)2造成了干擾，導(dǎo)致任務(wù)9、1、5、6、2的作業(yè)時間分別增加了3s、4s、4s、2s、3s。對于P25拆卸實例，相比于P10其解規(guī)模顯著增大，算法在指定的100s內(nèi)所能尋得問題的當前最優(yōu)解為：f1=10，f2=9，f3=76，f4=909，所對應(yīng)的拆卸任務(wù)方案如表4所示。

表4為直線型和U型兩種布局下，拆卸P10和P25最優(yōu)方案對比。在兩種模式下所開啟的工作站數(shù)量未發(fā)生變化。除了P10算例，采用U型布局的危害指數(shù)增加1以外，在平滑指數(shù)、危害指數(shù)和需求指數(shù)方面，U型布局均優(yōu)于直線型布局。圖7為P10實例在兩種拆卸線布局模式下的最優(yōu)序列作業(yè)任務(wù)分配情況對比，可以看出，U型線的布局設(shè)計更加柔性，可使拆卸任務(wù)更加靈活的在工作站上進行分配，因此U型布局通常比直線型布局具有更高的拆卸效率或更低的危害和需求指數(shù)。

表3 ABC、PVNS和SAABC求解基準算例均值、標準差對比

4 結(jié)論

在實際拆卸過程中，部分零部件之間會存在相互干擾，導(dǎo)致作業(yè)時間增加，從而影響拆卸線平衡，基于該現(xiàn)象，本文建立了U型SDDLBP多目標優(yōu)化模型。通過求解不同規(guī)模算例和拆卸實例，驗證了所提算法在求解USDDLBP的優(yōu)越性。與直線型拆卸線相比，U型線布局更加靈活柔性，可使拆卸任務(wù)更合理的進行分配。

后續(xù)研究可針對拆卸過程中零部件作業(yè)時間的不確定，考慮大型產(chǎn)品雙邊拆卸，以及多產(chǎn)品類型混合拆卸，此外還有以利潤等為目標的產(chǎn)品不完全或部分拆卸。

表4 U型和直線型布局結(jié)果對比