一種自適應人工蜂群算法求解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型和直線型布局結果對比