基于改進(jìn)人工蜂群算法的廢舊產(chǎn)品拆卸規(guī)劃

馬淑梅 陸星潤 徐立云

（同濟(jì)大學(xué) 機(jī)械與能源工程學(xué)院，上海 201804）

拆解回收再利用廢舊產(chǎn)品可以有效減少環(huán)境污染，助力實(shí)現(xiàn)“雙碳”目標(biāo)，對(duì)節(jié)能減排和資源再生具有重要意義。選擇性拆解規(guī)劃（Selective Disassembly Planning，SDP）問題作為拆解回收階段的難點(diǎn)，極大地影響了拆解效率和收益，因而受到人們的廣泛關(guān)注。

1 考慮碳排放的SDP模型

1.1 SDP問題描述

現(xiàn)階段SDP問題的研究主要包括拆解度、拆卸序列以及拆卸單元的回收方式3個(gè)方面。傳統(tǒng)SDP模型在跨度上僅僅考慮拆解回收階段而忽略對(duì)其他階段的影響，因此文章從產(chǎn)品生命周期的角度出發(fā)，分析不同回收方式對(duì)零部件原材料獲取和制造階段的影響，構(gòu)建考慮碳排放的SDP模型。合理回收廢舊產(chǎn)品的零部件，能夠抵消或減少因重新生產(chǎn)零部件和加工原材料產(chǎn)生的碳排放。

1.2 碳排放拆卸混合圖模型

圖模型主要有無向圖、有向圖、與或圖以及混合圖模型。其中，有向圖具有建模簡單和易于求解的特點(diǎn)，但功能相對(duì)單一，無法完整表述產(chǎn)品的拆卸信息。因此，本文在有向圖的基礎(chǔ)上加入聯(lián)接特征的碳排放信息，提出了碳排放拆卸混合圖模型[1]。

碳排放拆卸混合圖可以表示為G={VP,VC,DE}，其中頂點(diǎn)VP={vp1,vp2,…,vpn}表示拆卸單元，n為拆卸單元總數(shù)，聯(lián)接特征VC={vc1,vc2,…,vcs}表示拆卸單元之間的聯(lián)接件和聯(lián)接方式，s為拆卸特征總數(shù)，聯(lián)接特征通過虛線連接兩端的拆卸單元。優(yōu)先約束表示圖的邊，兩者之間存在強(qiáng)制性的拆卸優(yōu)先關(guān)系，記為DE={de1,de2,…,dew}，用實(shí)線箭頭表示。有向邊由優(yōu)先級(jí)低的拆卸單元指向優(yōu)先級(jí)高的拆卸單元。如圖1所示，該碳排放拆卸混合圖中包含8個(gè)拆卸單元和5個(gè)聯(lián)接特征。

圖1 碳排放拆卸混合圖

1.3 模型優(yōu)化目標(biāo)

1.3.1 拆卸時(shí)間最小

拆卸時(shí)間主要包括拆卸單元從拆卸主體分離的時(shí)間ti、常規(guī)拆卸聯(lián)接特征的時(shí)間tcm、破壞式拆卸聯(lián)接特征的時(shí)間tdm和工具變換消耗的時(shí)間ttoolpq。因此，最小化拆卸時(shí)間f1min可以表示為

1.3.2 拆卸利潤最大

拆卸利潤由回收拆卸單元和聯(lián)接特征的總收益Rvp、Rvc去拆卸成本f3、拆卸單元和聯(lián)接件回收過程中的做工成本RCvp、RCvc得到，因此最大化拆卸利潤f2max可以表示為

拆卸成本主要包括拆卸過程中消耗的人工成本Swf1、常規(guī)拆卸工具消耗成本Cr以及破壞式拆卸工具消耗成本Cr*，故拆卸成本f3min可以表示為

式中：Cr、Cr*可參考文獻(xiàn)[1]進(jìn)行估算。

1.3.3 減少的碳排放最多

產(chǎn)品拆解回收對(duì)不同階段碳排放的影響主要包括拆解過程中因拆卸操作產(chǎn)生、回收過程中因回收再加工產(chǎn)生以及通過不同回收方式回收拆卸單元而抵消或減少的碳排放量。最大化減少的碳排放f4max表示為

拆解過程中產(chǎn)生的碳排放量Gd是拆卸聯(lián)接特征產(chǎn)生碳排放的總和，即

因回收減少的碳排放量Gr為

拆卸單元vpi在不同的回收方式下減少的碳排放量Gik的計(jì)算為

拆卸單元再利用和再制造時(shí)，減少的碳排放Gi1和Gi2為抵消的原材料獲取階段的碳排放制造階段的碳排放GEi減去因回收產(chǎn)生的碳排放GCiK；對(duì)拆卸單元進(jìn)行材料回收時(shí)，減少的碳排放Gi3為抵消的原材料獲取階段的碳排放減去因回收產(chǎn)生的碳排放；進(jìn)行廢棄處理時(shí)，減少的碳排放Gi4為0。再利用、再制造和材料回收過程中產(chǎn)生的碳排放量Gi1、Gi2和Gi3可以從回收作業(yè)中獲取。拆卸單元制造階段產(chǎn)生的碳排放GEi以文獻(xiàn)[2]提出的制造過程碳排放量化方法進(jìn)行估算[2]。

2 改進(jìn)人工蜂群算法

人工蜂群算法在多目標(biāo)優(yōu)化問題求解中表現(xiàn)出求解高效和結(jié)果理想等特點(diǎn)，因此提出改進(jìn)的多目標(biāo)人工蜂群算法（Improved Artificial Multi-objective Bee Colony Algorithm，IMOABC），可用于求解多目標(biāo)SDP問題。

IMOABC算法的詳細(xì)運(yùn)算流程如下。

步驟1：設(shè)定蜜源個(gè)數(shù)PS、最大迭代次數(shù)、蜜源開采次數(shù)上限limit以及外部檔案容量Q。

步驟2：初始化蜜源，通過非支配排序和擁擠度計(jì)算初始化外部檔案Q。

步驟3：通過交叉操作在雇傭蜂的領(lǐng)域內(nèi)產(chǎn)生新的蜜源。

步驟4：判斷新蜜源是否被原蜜源支配，若被支配則將原蜜源分配給雇傭蜂，否則將新蜜源分配給雇傭蜂，并將開采度設(shè)為0。

步驟5：重復(fù)步驟3和步驟4，更新PS個(gè)雇傭蜂的蜜源。

步驟6：按錦標(biāo)賽規(guī)則從雇傭蜂中選取2個(gè)較好的個(gè)體進(jìn)行交叉操作產(chǎn)生新的蜜源。

步驟7：判斷新蜜源是否被原蜜源支配，若被支配則繼續(xù)開采原蜜源分配，并將其開采度加1，否則將新蜜源分配給觀察蜂，將開采度設(shè)為0。

步驟8：重復(fù)步驟7和步驟8，更新PS個(gè)觀察蜂的蜜源。

步驟9：檢查各蜜源的開采次數(shù)是否大于開采上限，若大于則轉(zhuǎn)化為偵查蜂尋找新的蜜源，并將開采度設(shè)為0。

步驟10：檢查是否有重復(fù)的蜜源，若有，對(duì)重復(fù)的蜜源進(jìn)行重構(gòu)。

步驟11：進(jìn)行非支配排序和擁擠度計(jì)算，更新外部檔案Q。

步驟12：重復(fù)步驟4至步驟12，直到迭代次數(shù)達(dá)到最大迭代數(shù)，得到問題的Preto解集。

采用三鏈表結(jié)構(gòu)對(duì)蜜源進(jìn)行編碼，記為v={v1,v2,v3}。v1={a1,ai,…,an}表示拆卸序列，ai為第i個(gè)被拆卸的拆卸單元。v2={b1,b2,…,bn}表示v1中對(duì)應(yīng)拆卸單元的拆卸方式，其值代表拆卸方式編號(hào)。v3={c1,c2,…,cn}標(biāo)記v1中對(duì)應(yīng)拆卸單元的回收方式，其值代表回收方式編號(hào)。根據(jù)文獻(xiàn)[2]中可行解的方法隨機(jī)生成PS個(gè)完全拆卸序列，定義變量hlast表示完全拆解序列v1中最靠后的目標(biāo)拆卸單元的編號(hào)，保證實(shí)際拆解序列長度L不小于hlast，即可生成符合約束要求的不完全拆解序列，其計(jì)算公式為

依據(jù)上述操作得到可行的拆解方案，將生成的蜜源記為v′={v1,v2,v3,L}。

為確保雇傭蜂階段交叉后生成的新v1仍能滿足優(yōu)先約束關(guān)系，采用優(yōu)先保存交叉（Precedence Preservative Crossover，PPX）的方法對(duì)2個(gè)個(gè)體方案進(jìn)行交叉操作。PPX交叉操作流程：隨機(jī)生產(chǎn)一條由2個(gè)父代個(gè)體編號(hào)組成的序列，長度與個(gè)體長度相等；根據(jù)隨機(jī)生成的序列，依次從各自父代個(gè)體上選取子代基因?qū)⑵洳迦胱哟鷤€(gè)體，并在父代個(gè)體上刪除該基因。重復(fù)該過程，直到所有子代基因選擇完畢[3]。

圖2描述了一個(gè)簡單的PPX交叉過程。執(zhí)行PPX的父代個(gè)體均為完全拆卸序列。為拆除所有目標(biāo)拆卸單元，每個(gè)交叉后的子代個(gè)體需要根據(jù)式（8）隨機(jī)生成對(duì)應(yīng)的L。

圖2 PPX過程

在觀察蜂階段采取錦標(biāo)賽選擇策略，選取2個(gè)局部最優(yōu)個(gè)體進(jìn)行PPX交叉操作，結(jié)合貪心策略將比較后較優(yōu)的蜜源分配給觀察蜂進(jìn)行采蜜工作，以提高蜂群的尋優(yōu)能力[4]。第一，確定選取的個(gè)體數(shù)量N。第二，從種群中隨機(jī)選擇N個(gè)個(gè)體。個(gè)體被選擇的概率相同，根據(jù)個(gè)體的非支配等級(jí)和擁擠距離進(jìn)行排序，選擇最優(yōu)者作為PPX交叉操作的父代之一。第三，重復(fù)第二步的操作選取另一個(gè)父代，執(zhí)行PPX交叉操作生成新個(gè)體。將產(chǎn)生的新個(gè)體與原種群個(gè)體比較，取代種群中表現(xiàn)較差的個(gè)體。第四，重復(fù)第二步和第三步的操作，直到所有觀察蜂均被分配完畢。

3 實(shí)例應(yīng)用

結(jié)合SDP模型和IMOABC算法，以某廢舊變速箱為案例進(jìn)行拆解規(guī)劃。

3.1 案例數(shù)據(jù)收集

某雙離合變速箱對(duì)應(yīng)的拆卸混合圖如圖3所示。該變速箱主要由23個(gè)拆卸單元構(gòu)成。變速箱內(nèi)部單元的拆卸信息如表1所示。從拆卸單元的回收收益和危害性角度考慮，將編號(hào)為4、8、18和20的拆卸單元作為選擇性拆卸的目標(biāo)。

圖3 碳排放拆卸混合圖

其他無法直接收集和獲取的SDP模型輸入數(shù)據(jù)采用以下方式進(jìn)行估算。查詢相關(guān)設(shè)計(jì)手冊中對(duì)應(yīng)聯(lián)接特征的參數(shù)，文獻(xiàn)[5]中螺栓聯(lián)接裝配碳排放的計(jì)算方法，對(duì)拆卸螺栓聯(lián)接產(chǎn)生的碳排放量進(jìn)行GEol-m估算[5]。根據(jù)變速箱的BOM表，參考表1估算拆卸單元和聯(lián)接特征原材料獲取階段產(chǎn)生的碳排放GMi。

表1 變速箱內(nèi)部單元的拆卸信息

3.2 試驗(yàn)結(jié)果分析

為驗(yàn)證IMOABC算法的全局性，與未改進(jìn)的多目標(biāo)MOABC、多目標(biāo)快速非支配排序遺傳算法（Non-dominant Sorting Genetic Algorithm-Ⅱ，NSGA-Ⅱ）以及人工魚群算法（Artificial Fish-Swarm Algorithm，AFSA）進(jìn)行比較。所有算法種群規(guī)模均設(shè)為100，迭代100次。各算法的參數(shù)設(shè)定如下：國際數(shù)學(xué)奧林匹克競賽（International Mathematical Olympiad ABC，IMOABC）的選擇個(gè)體數(shù)為35，蜜源開采上限為5；NSGA-Ⅱ的交叉概率為0.9，變異率為0.1；AFSA中覓食行為最大嘗試次數(shù)為5，視野visual=50，擁擠度設(shè)為0.8。涉及的所有算法均在C++中編程，運(yùn)行環(huán)境配置為Intel（R） Core（TM）i5-7 300HQ CPU處 理 器，NVIDIA GeForce GTX 1 050 2 GB顯卡，2.50 GHz主頻，12.0 GB內(nèi)存。4種算法迭代后的Pareto前沿如圖4所示，結(jié)果觀察到IMOABC的Pareto前沿在分布、收斂和數(shù)量上都比其他算法更理想。IMOABC的Pareto解集如表2所示，可見拆卸利潤越高的拆卸方案減少的碳排放越多，但要花費(fèi)的拆卸時(shí)間越久。合適的拆卸方案可以根據(jù)決策者的期望選擇，通常可以人為對(duì)優(yōu)化目標(biāo)設(shè)置權(quán)重進(jìn)行排序選擇。

圖4 不同算法的Pareto前沿

4 結(jié)語

針對(duì)廢舊產(chǎn)品的拆解回收再利用，建立考慮碳排放的SDP模型，將拆卸利潤、拆卸時(shí)間和減少的碳排放作為優(yōu)化目標(biāo)，采用IMOABC算法對(duì)該模型進(jìn)行求解，獲得高質(zhì)量的Pareto解集，最后結(jié)合某雙離合變速箱的拆解案例，驗(yàn)證模型和算法的可行性和高效性。