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

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

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

1 引言

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

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

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

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

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

2 目標拆卸模型

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

2.1 定義有向圖

圖1 有向圖

2.2 定義約束矩陣

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

根據圖1，按上述原則得出對應的約束矩陣為：

2.3 拆卸序列的生成步驟

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

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

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

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

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

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

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

步驟七：輸出拆卸序列S，結束。

3 優化目標

在廢舊手機拆卸商業化的過程中，拆卸利潤與拆卸效率應為著重點，因此以單位時間內產生的利潤RERATE為優化目標進行尋優。

3.1 拆卸時間計算模型

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

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

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

3.2 拆卸利潤計算模型

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

（1）元器件收益INA

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

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

（2）材料收益INM

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

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

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

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

利潤計算模型為：

4 蟻群算法尋優

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

4.1 蟻群算法的原理

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

4.2 蟻群算法在廢舊手機拆卸序列優化中的應用

（1）個體適應度

在優化算法中個體適應度一般與優化目標相關聯。單位時間內產生的利潤為優化目標，可以將其直接作為個體適應度。因此個體適應度計算模型為：

（2）信息素矩陣

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

（3）算法總體流程

相對應的流程圖如圖2所示。該算法既有隨機性也有確定性。隨機性保證了路徑的多樣性，使算法不易出現局部最優。確定性保證了算法朝著預定的目標發展。

圖2 蟻群算法流程圖

5 案例研究

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

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

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

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

圖3 華為P7零件有向圖

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

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

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

華為P7的連接元胞數組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 結果與分析

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

圖4 目標拆卸收斂過程

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

表3 目標拆卸優化結果

7 結論

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

（2）針對手機零件結構緊湊、一個零件往往同時與多個零件連接的特點，創新性的采用連接元胞數組全面的表達了零件間的連接關系，建立了適用于手機零件連接的表達方法。

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

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