基于蟻群算法的廢舊手機目標拆卸序列規(guī)劃研究

王曉東 劉廣闊 李泓瑞 孫華棟 符永高 李林

1.青島科技大學機電工程學院 山東青島 266061；2.中國電器科學研究院股份有限公司 廣東廣州 510300

1 引言

隨著科技的進步和居民消費水平的提高，電器電子產(chǎn)品更新速度不斷加快。2020年每個月的手機產(chǎn)量均保持在13000萬臺左右，并且隨著5G時代的來臨必將帶來一波換機潮，初步估計2020年將會有3.4億部廢舊手機。在如此大的手機保有量，且手機產(chǎn)品更新?lián)Q代的速度不斷加快，產(chǎn)品不斷地推陳出新的情況下，必然產(chǎn)生大量淘汰的廢舊手機[1]。據(jù)中國工業(yè)和信息化部的數(shù)據(jù)顯示，現(xiàn)在每年產(chǎn)生的廢舊手機大約有2億部。廢棄的電氣和電子設(shè)備（Waste Electrical and Electronic Equipment，WEEE）既有可能成為有價值的材料來源，又是有害物質(zhì)的潛在來源[2]。作為WEEE其中的一類，廢舊手機同樣如此。如果妥善處理這部分資源一方面會降低生產(chǎn)成本，帶來巨大的經(jīng)濟收益；另一方面會減少對環(huán)境的危害，實現(xiàn)綠色發(fā)展。近年來，拆解分離廢舊手機回收其中的元器件以及提取貴金屬的做法逐漸發(fā)展流行起來[3]。拆卸零件的順序?qū)τ诓鹦稄U舊手機商業(yè)化是至關(guān)重要的。

近年來，學者們對于拆卸序列進行了廣泛的研究。在拆卸模型方面，周喜梅等[4]提出了可以生成可行拆卸序列的分層模塊劃分模型。聶應(yīng)軍等[5]通過拆卸過渡矩陣和拆卸繼承矩陣描述了所有可能的拆卸過程。郭磊等[6]提出了一種零件層次劃分方法，可以簡化復雜產(chǎn)品拆卸序列的生成過程。

當零件數(shù)目較多時會產(chǎn)生大量的可行拆卸序列，難以從中挑選出最優(yōu)解或次優(yōu)解，而啟發(fā)式算法可以很好的解決這一問題，因此在這一方面眾多學者也做了大量的研究。例如：REN等[7]考慮拆卸操作的相關(guān)時間，通過遺傳算法求解了異步并行拆卸計劃。吳昊等[8]提出了一種結(jié)合二叉樹算法的遺傳算法，并通過此算法獲得最優(yōu)或次優(yōu)選擇性拆卸序列。TSENG等[9]提出了一種混合雙向蟻群算法（HybridBACO），增加了路徑選擇的優(yōu)勢，并避免了極端信息素值的影響。張秀芬等[10]等通過粒子群算法解決了復雜機械產(chǎn)品的目標選擇性拆卸序列規(guī)劃問題。

上述研究成果多為針對機械設(shè)備或是大型家電產(chǎn)品，并沒有適合于廢舊手機拆卸模型。因此，對廢舊手機進行拆卸回收研究具有一定實際意義。

手機相比于機械設(shè)備和大型家電產(chǎn)品零件較為密集，一個零件往往同時與多個零件連接。針對這一特點采用有向圖表達零件間的約束關(guān)系，而零件之間的連接關(guān)系通過連接元胞數(shù)組表示。這種表達方式使后續(xù)手機零件拆解序列的生成更貼合實際拆解。以單位時間內(nèi)產(chǎn)生的利潤為優(yōu)化目標，采用蟻群算法進行尋優(yōu)，最終獲得最優(yōu)或次優(yōu)解。

2 目標拆卸模型

拆解產(chǎn)品之前必須獲知它的裝配結(jié)構(gòu)信息，只有完全清楚產(chǎn)品的裝配結(jié)構(gòu)信息，才能制定出可靠準確的拆卸模型。為表達產(chǎn)品的裝配結(jié)構(gòu)及其拆解信息，需要借助拆解示意圖來描述。現(xiàn)有的拆卸示意圖主要有無向圖、有向圖、與或圖、Petri網(wǎng)等。其中有向圖是一種簡單有效的拆解示意圖，通過零部件之間的約束關(guān)系表達零部件拆卸任務(wù)之間的先后順序。因此本論文采用有向圖作為拆解示意圖。

2.1 定義有向圖

圖1 有向圖

2.2 定義約束矩陣

基于有向圖生成約束矩陣C=cij。設(shè)總零件個數(shù)為N，約束矩陣C為N×N的方陣。約束矩陣的每一行和每一列均代表相應(yīng)的零件。當零件i對零件j有約束時cij=1；當零件i對零件j無約束或i=j時，cij=0。

根據(jù)圖1，按上述原則得出對應(yīng)的約束矩陣為：

2.3 拆卸序列的生成步驟

定義總體零件集合Ω：集合Ω為包含所有零件的集合。

定義可拆卸零件集合Φ：集合Φ為包含當前所有可拆卸零件的集合。

步驟一：計算約束矩陣中每一個列向量的模。

步驟三：在可拆卸零件集合Φ與總體零件集合Ω的交集中按概率挑選出一個零件j作為被拆零件放入拆卸序列S中。

步驟四：更新總體零件集合Ω（在Ω中將零件j刪除）。

步驟五：更新約束矩陣（將約束矩陣中零件j的所在行歸零）。

步驟六：若目標零件全部被拆除則轉(zhuǎn)步驟七，否則轉(zhuǎn)步驟一。

步驟七：輸出拆卸序列S，結(jié)束。

3 優(yōu)化目標

在廢舊手機拆卸商業(yè)化的過程中，拆卸利潤與拆卸效率應(yīng)為著重點，因此以單位時間內(nèi)產(chǎn)生的利潤RERATE為優(yōu)化目標進行尋優(yōu)。

3.1 拆卸時間計算模型

針對已生成的拆卸序列建立拆卸時間模型計算其對應(yīng)的拆卸時間。在手機拆卸的過程中拆卸時間TZ為斷開被拆卸零件與其他零件之間連接所需要的時間。

由于廢舊手機零件具有一個零件同時與多個零件連接或一個零件與另一個零件同時存在多處連接的特點。針對這一特點，創(chuàng)新性地利用了連接元胞數(shù)組這一模型表達零件之間的連接關(guān)系，并依此計算拆卸時間。

其中，Si為序列S中第i個零件；di-1為更新i-1次后的連接元胞數(shù)組；N為總零件個數(shù)；m為序列S中的零件總個數(shù)。

3.2 拆卸利潤計算模型

拆卸利潤R由總收益IN與成本EX組成。總收益IN包括元器件收益INA和材料收益INM；成本EX為廢舊手機購買成本。

（1）元器件收益INA

元器件收益為已生成的拆卸序列中的零件以元器件的方式回收時的總收益。

其中：E為元器件收益矩陣，是維度為總元器件個數(shù)的行向量，各元素為相應(yīng)元器件的回收價格。

（2）材料收益INM

材料收益為已生成的拆卸序列中的零件以材料的方式回收時的總收益。

其中：M為廢舊手機的總質(zhì)量；K為元器件質(zhì)量矩陣，是維度為總元器件個數(shù)的行向量，各元素為相應(yīng)元器件的質(zhì)量；p為單位質(zhì)量的廢舊手機零件以材料的方式回收時的價格。

（3）廢舊手機購買成本EXB

廢舊手機購買成本即為從二手市場購買廢舊手機的成本。

利潤計算模型為：

4 蟻群算法尋優(yōu)

當待拆卸廢舊手機零件較多時，將會有大量可行拆卸序列，這將給尋優(yōu)工作帶來巨大的計算量。而啟發(fā)式算法很好的解決了這一問題，對于拆卸序列的尋優(yōu)，現(xiàn)有的文獻多采用遺傳算法、粒子群算法、蝙蝠算法等。由于目標拆卸的拆卸序列長度不一，而蟻群算法對于序列的長度并無要求，因此采用蟻群算法求解。

4.1 蟻群算法的原理

蟻群算法是模擬自然界螞蟻覓食的行為。螞蟻在覓食時，會在路徑上留下信息素，并能感知到其他螞蟻留下的信息素，并以較大概率選擇信息素濃度高的路徑，這樣會形成一個正反饋。最終螞蟻能夠找到一條從巢穴到食物源最短的路徑。值得一提的是信息素會隨著時間的推移而揮發(fā)。蟻群算法最典型的應(yīng)用是在解決旅行商問題上，而廢舊手機拆卸零件序列規(guī)劃問題十分類似旅行商問題，但也存在差異。所以本論文算法進行了相應(yīng)的改動，以適應(yīng)廢舊手機拆卸零件序列規(guī)劃問題。

4.2 蟻群算法在廢舊手機拆卸序列優(yōu)化中的應(yīng)用

（1）個體適應(yīng)度

在優(yōu)化算法中個體適應(yīng)度一般與優(yōu)化目標相關(guān)聯(lián)。單位時間內(nèi)產(chǎn)生的利潤為優(yōu)化目標，可以將其直接作為個體適應(yīng)度。因此個體適應(yīng)度計算模型為：

（2）信息素矩陣

當每代拆卸序列生成完成后會在信息素矩陣中對適應(yīng)度值最高的拆卸序列增加額外的信息素，而較高的信息素又會進一步指引下一代適應(yīng)度值高的拆卸序列的生成，形成一個正反饋。經(jīng)過多代尋優(yōu)最終收斂到最優(yōu)拆卸序列。信息素更新模型為：

（3）算法總體流程

相對應(yīng)的流程圖如圖2所示。該算法既有隨機性也有確定性。隨機性保證了路徑的多樣性，使算法不易出現(xiàn)局部最優(yōu)。確定性保證了算法朝著預定的目標發(fā)展。

圖2 蟻群算法流程圖

5 案例研究

下面以華為P7手機為例驗證上述計算模型。參考行業(yè)的經(jīng)驗及手工拆機實踐，華為P7可拆卸出16個零部件，分別是后蓋、卡槽1、卡槽2、上蓋板、下蓋板、射頻線、振動馬達、后攝、前攝、接口保護罩、音量鍵、主板、聽筒、屏幕、主體和電池。表1為華為P7各零件與序號的對應(yīng)關(guān)系及具體信息。

表1 華為P7手機零件信息表

由深圳市愛博綠環(huán)保科技有限公司提供的回收價格信息顯示，具有回收價值的零件主要為主板、電池、前攝、后攝和屏幕，其回收價格分別為45元、1.5元、2元、2元和1.5元，其余零件按其重量和其材料的當前市場回收單價計算。每個零件的重量來自于拆機實測。對于購買成本則取決于當前二手手機回收市場價格，價格會隨著行情的變化具有不確定性。華為P7廢舊手機購買成本約為30元/臺。材料收益的價格由青島宏盈旺再生資源有限公司提供，為3000元/噸。

根據(jù)華為P7手機的實際情況做如圖3所示的有向圖。

圖3 華為P7零件有向圖

華為P7零件之間共有6種連接方式分別為膠連、螺釘連接、卡扣連接、搭扣連接、嵌入連接和插入連接，每種連接對應(yīng)的拆卸時間如表2所示。其中各種連接方式的拆卸時間是由人工重復5次拆機實驗求取的平均值。

表2 各連接方式的拆卸時間

根據(jù)有向圖生成華為P7的約束矩陣C。

華為P7的連接元胞數(shù)組D為：

其中，d0=[0 0 0 0 0 0]；d1=[1 0 0 0 0 0]；d2=[0 0 0 0 0 1]；d3=[0 0 0 0 0 1]；d4=[0 9 0 0 0 0]；d5=[0 3 0 0 0 0]；d6=[0 0 0 1 0 0]；d7=[0 0 0 1 0 0]；d8=[0 0 0 1 0 0]；d9=[1 0 0 0 0 0]；d10=[0 0 0 1 0 0]；d11=[0 0 0 0 1 0]；d12=[0 0 0 1 0 0]；d13=[0 0 0 0 1 0]；d14=[0 1 0 0 0 0]；d15=[0 0 0 1 0 0]；d16=[0 0 0 0 1 0]；d17=[0 0 0 1 0 0]；d18=[0 2 2 0 0 0]；d19=[0 0 0 1 0 0]；d20=[0 0 0 0 1 0]；d21=[1 0 0 0 0 0]；d22=[1 0 0 0 0 0]。

6 結(jié)果與分析

根據(jù)表1中的信息可以看出在目前市場條件下具有回收價值的零件有主板、后攝像頭、前攝像頭、電池和屏幕，其中主板的價值遠超其他零件，因此主板應(yīng)為必拆件。電池含有有害物質(zhì)，也應(yīng)為必拆件。因此以主板和電池為目標零件進行優(yōu)化，結(jié)果如圖4和表3所示。

圖4 目標拆卸收斂過程

通過圖4可以看出在未優(yōu)化之前單位時間內(nèi)產(chǎn)生的利潤為0.0485元，經(jīng)過蟻群算法優(yōu)化后為0.0500元，提高了3.09%。從表3的數(shù)據(jù)中可以看出，以主板和電池為目標零件拆解一臺華為P7所需要的時間為381.8秒，產(chǎn)生的利潤為19.04元，單位時間內(nèi)產(chǎn)生的利潤為0.0500元。以每天8小時的工作時間計算，一個拆解工位通過拆解華為P7一天可以產(chǎn)生1440元的利潤。

表3 目標拆卸優(yōu)化結(jié)果

7 結(jié)論

（1）本文用混合圖直觀的描述了各手機零件之間的約束關(guān)系，基于有向圖建立拆卸模型，推導出可行的拆卸序列，并與蟻群算法結(jié)合有助于可行拆卸序列的快速生成和優(yōu)化。

（2）針對手機零件結(jié)構(gòu)緊湊、一個零件往往同時與多個零件連接的特點，創(chuàng)新性的采用連接元胞數(shù)組全面的表達了零件間的連接關(guān)系，建立了適用于手機零件連接的表達方法。

（3）以華為P7為案例驗證上述拆解模型和蟻群算法發(fā)現(xiàn)，單位時間內(nèi)產(chǎn)生的利潤從未優(yōu)化之間的0.0485元提高到優(yōu)化后的0.0500元，提高了3.09%；以每天8小時的工作時間計算，一個拆解工位通過拆解華為P7一天可以產(chǎn)生1440元的利潤。

我國手機品牌眾多，同一品牌手機旗下也有不同的型號，其結(jié)構(gòu)都有差異。并且手機零件回收價格也隨市場波動。根據(jù)本文所提出的方法，只需將不同型號的手機的約束矩陣、連接元胞數(shù)組以及手機零件信息輸入到算法中即可快速地確定哪種型號的手機最具有拆卸回收價值以及以哪些零件作為目標零件產(chǎn)生的利潤最高。面對當前廢舊手機存有量巨大且該數(shù)字呈不斷上漲趨勢的情況，本文所提出的方法有利于解決廢舊手機拆卸回收問題，可以為廢舊手機拆卸的商業(yè)化提供理論判斷標準，具有較強的實用性。