基于逆向物流的拆卸和恢復(fù)策略優(yōu)化算法

史 云，陳勁杰

（1.上海瀚資軟件咨詢有限公司，上海 200050；2.上海理工大學(xué)，上海 200093）

0 引 言

對(duì)回收的廢舊產(chǎn)品或部件進(jìn)行拆卸和再利用是逆向物流的重要組成部分。它是逆向物流研究中的技術(shù)難點(diǎn)，涉及到產(chǎn)品的幾何結(jié)構(gòu)的可拆卸分析，多種拆卸工藝，產(chǎn)品的優(yōu)化拆卸路徑和過(guò)程分析，以及恢復(fù)策略等方面。

本文主要采用最短路徑算法解決產(chǎn)品的最優(yōu)拆卸路徑的選擇問(wèn)題，隨后采用隨機(jī)動(dòng)態(tài)規(guī)劃算法解決產(chǎn)品回收后綜合各種因素的恢復(fù)策略優(yōu)化問(wèn)題。

1 一維拆卸最短路徑算法

該算法主要解決組件在同一個(gè)產(chǎn)品中具有不同的拆卸路徑以及組件可以由多個(gè)產(chǎn)品拆卸后提供，即擁有多拆卸提供源的情況下的拆卸路徑的優(yōu)化選擇。

1.1 算法基本思想。本文用有向圖模型建立產(chǎn)品的拆卸樹(shù)狀結(jié)構(gòu)：把產(chǎn)品及其組件看作節(jié)點(diǎn)，把弧看作拆卸路徑，弧的方向表示了被拆卸件從拆卸基體上拆離的這種關(guān)系。權(quán)表示拆卸時(shí)間，按照不同要求也可以換成拆卸成本等參數(shù)。由于樹(shù)就是無(wú)圈連通圖，是同一個(gè)理論體系，因此，采用圖論中的最短路徑算法對(duì)拆卸樹(shù)進(jìn)行分析。

目前，公認(rèn)的較好的最短路徑計(jì)算方法是Dijkstra方法。該方法的基本思路是：從起始點(diǎn)出發(fā)，逐步地向外探索最短路徑。執(zhí)行過(guò)程中，與每個(gè)點(diǎn)對(duì)應(yīng)，記錄標(biāo)號(hào)，標(biāo)號(hào)或表示從起始點(diǎn)到該點(diǎn)的最短路徑權(quán)，或者從起始點(diǎn)到該點(diǎn)最短路的權(quán)上限。方法的每一步是去修改T標(biāo)號(hào)，并且把某一個(gè)具有T標(biāo)號(hào)的點(diǎn)改變?yōu)榫哂蠵標(biāo)號(hào)的點(diǎn)，從而使圖中的具有P標(biāo)號(hào)的點(diǎn)多一個(gè)。因此，經(jīng)過(guò)多步迭代就可以得到從起始點(diǎn)到各點(diǎn)的最短路。

按照該算法計(jì)算一次就可以得到從產(chǎn)品拆卸任一個(gè)組件的最短路徑，即得到拆卸需要耗費(fèi)的時(shí)間和拆卸的先后順序。

2 隨機(jī)動(dòng)態(tài)規(guī)劃算法[1]

拆卸和恢復(fù)策略定義了回收產(chǎn)品的拆卸深度、拆卸順序、拆卸工藝和被拆卸的組件的恢復(fù)類型。

為了優(yōu)化拆卸和恢復(fù)策略，必須考慮質(zhì)量因素。實(shí)際應(yīng)用中，回收產(chǎn)品的質(zhì)量往往影響它的拆卸和恢復(fù)策略。例如，計(jì)算機(jī)的回收利用。目前，計(jì)算機(jī)的更新速度非?？?，如過(guò)一臺(tái)計(jì)算機(jī)的出廠日期在半年以內(nèi)，那么可以對(duì)其實(shí)施再制造策略，否則只能實(shí)施拆用配件或整修策略。

同時(shí)，眾多的拆卸工藝（破壞性的、非破壞性的）以及部分拆卸的情況也必須在算法中考慮，針對(duì)高恢復(fù)利潤(rùn)的部件的部分拆卸要比完全拆卸更加經(jīng)濟(jì)。因此，算法應(yīng)該考慮回收產(chǎn)品和拆卸子件的質(zhì)量狀態(tài)，不同的拆卸工藝（種類），并且允許部分拆卸。

2.1 算法假設(shè)條件和符號(hào)說(shuō)明。本文采用隨機(jī)動(dòng)態(tài)規(guī)劃算法，并認(rèn)為以下條件已知：（1）拆卸結(jié)構(gòu)。第0層，即樹(shù)的根節(jié)點(diǎn)表示回收的產(chǎn)品，其他層表示它的部件、零件等。在拆卸過(guò)程中，產(chǎn)品本身、部件、零件被統(tǒng)稱為組件。如果一個(gè)組件不能被進(jìn)一步拆卸，則稱為原子型組件，否則稱為非原子型組件。拆卸結(jié)構(gòu)包含的弧表示從一個(gè)組件到其所有自建的連接。（2）隨拆卸工藝而定的質(zhì)量分布狀態(tài)。對(duì)于拆卸結(jié)構(gòu)的每一條弧，和組件質(zhì)量有關(guān)的其子件的質(zhì)量分布對(duì)于每一種拆卸工藝是給定的。（3）隨質(zhì)量而定的修復(fù)策略和利潤(rùn)。對(duì)于每個(gè)組件，隨質(zhì)量而定的修復(fù)策略以及相關(guān)利潤(rùn)，對(duì)于總體上的組件和拆卸后的任何可能子件的集合都是確定的。（4）根據(jù)產(chǎn)品的拆卸樹(shù)狀結(jié)構(gòu)模型，非原子型組件的可行恢復(fù)和處理策略集合包含5中恢復(fù)策略和2種處理策略及拆卸；而原子型組件的策略只包括可行恢復(fù)和處理策略，不包括拆卸。

下表對(duì)算法中使用的符號(hào)進(jìn)行了說(shuō)明：

符號(hào)符號(hào)的意義l 拆卸層次，l=0,1,…,L,l=0表示產(chǎn)品本身j 組件編碼，j=0,1,…,J,j=0表示產(chǎn)品本身l（）j 組件j的拆卸層次Q（）j 組件j的質(zhì)量種類集合D（）j 組件j的拆卸工藝集合S（）j 組件j的拆卸后獲得的子件集合，對(duì)于原子型組件j，S（）j＝Φ R j,q（）1 質(zhì)量q1的組件j的恢復(fù)策略集合，q1∈Q（）j R（j,q1,S,）（）的恢復(fù)策略集合，S是由質(zhì)量為q1的組件j使用d拆卸工藝后獲得c（j,q1,S,）d 非空的子件集合S S?S（）j d 從組件j上采用d拆卸工藝獲得子件集合S S?S（）j（）而花費(fèi)的拆卸成本p（j,q1,）r 使用策略r對(duì)質(zhì)量為q1的組件j進(jìn)行恢復(fù)后獲得的凈利潤(rùn)p（j,q1,S,）r 質(zhì)量為q1的組件j拆除子集S S?S（）j（）后，使用策略r對(duì)剩余部分進(jìn)行恢復(fù)獲得的凈利潤(rùn)，r∈R（j,q1,）S,q1∈Q（）j Pr s,q2,j,q1,（d 采用拆卸工藝d從質(zhì)量為q1的組件j上拆下子件s，并使s具有質(zhì)量q2的概率，s∈S（）j）

2.2 算法原理和流程。把產(chǎn)品回收后按照產(chǎn)品的拆卸樹(shù)結(jié)構(gòu)，進(jìn)行層層拆卸和恢復(fù)的過(guò)程，可以看作是一個(gè)多階段決策問(wèn)題。在它的每一個(gè)階段都需要做出決策，從而使整個(gè)過(guò)程達(dá)到最好的活動(dòng)效果。各個(gè)階段決策的選取不是任意確定的，它依賴于當(dāng)前面臨的狀態(tài)，且影響以后發(fā)展。當(dāng)各個(gè)階段決策確定后，就組成了一個(gè)決策序列，因而也就決定了整個(gè)過(guò)程的一個(gè)完整最優(yōu)解決方案。而動(dòng)態(tài)規(guī)劃恰恰是用來(lái)解決多階段決策問(wèn)題的利器，因此，本文采用動(dòng)態(tài)規(guī)劃原理構(gòu)建算法模型。

首先從產(chǎn)品結(jié)構(gòu)的最底層L開(kāi)始，即只包含原子型組件的層，對(duì)該層的所有組件（質(zhì)量狀態(tài)是已知的），比較所有可行的恢復(fù)策略所產(chǎn)生利潤(rùn)，從中選取最優(yōu)的策略。然后，遞推到上一層L-1，類似的，得到該層上的所有原子型組件的最優(yōu)修復(fù)策略和對(duì)應(yīng)的利潤(rùn)。而對(duì)于L-1層上的非原子型組件，比較直接恢復(fù)利潤(rùn)（不拆卸）和拆卸后子件集的恢復(fù)利潤(rùn)之和，然后選取最大值作為該組件的利潤(rùn)，同時(shí)得到了該非原子組件的策略，即是整體采用恢復(fù)策略還是進(jìn)一步拆卸？如果進(jìn)一步拆卸，應(yīng)從該組件上拆卸哪些子件下來(lái)進(jìn)行恢復(fù)。這樣一直遞推到根節(jié)點(diǎn)產(chǎn)品一級(jí)，從而決定了整個(gè)產(chǎn)品的再利用策略。

對(duì)于原子型組件，根據(jù)具體質(zhì)量狀態(tài)的產(chǎn)品或組件的恢復(fù)利潤(rùn)，按照公式（1）和（2）選擇最大利潤(rùn)的恢復(fù)策略。對(duì)于非原子型組件，按照公式（3）和（4）比較該組件的整體恢復(fù)利潤(rùn)和拆卸后再恢復(fù)利潤(rùn)，如果公式（3）通過(guò)w（j,q）獲得最大值，那么它的最優(yōu)策略是把組件j作為整體進(jìn)行恢復(fù)，實(shí)現(xiàn)最大值的恢復(fù)策略r就是最優(yōu)策略。否則，就應(yīng)該對(duì)組件j進(jìn)行進(jìn)一步的拆卸，決定拆卸哪些組件，并對(duì)該子件集合進(jìn)行恢復(fù)。這時(shí)的最大利潤(rùn)值由拆卸的子集中子件恢復(fù)后利潤(rùn)（注意：是利潤(rùn)而不是收入，這里已經(jīng)是該子件在l-1層上的最優(yōu)利潤(rùn)值，已經(jīng)扣除了成本）之和加上剩余部分的恢復(fù)后利潤(rùn)減去拆卸成本。

達(dá)到最大值的d和S以及 C（j,q1|d,）S 的r分別是最優(yōu)拆卸工藝（種類），最優(yōu)拆卸目標(biāo)子件集合和最優(yōu)恢復(fù)策略。

最后給出的拆卸和恢復(fù)優(yōu)化策略就是一套有條件的規(guī)則。對(duì)于一個(gè)回收的廢舊產(chǎn)品，由算法根據(jù)每個(gè)組件的質(zhì)量狀態(tài)，組件及其子件間的質(zhì)量轉(zhuǎn)換概率來(lái)決定拆卸深度，拆卸集合以及每個(gè)組件的采用的策略。例如，對(duì)回收的廢舊液壓油泵。初步拆卸后，如果齒輪支座和齒輪工作正常，則只需進(jìn)行清洗和潤(rùn)滑；否則繼續(xù)拆卸或替換。

3 數(shù)值例子

考慮一個(gè)數(shù)字計(jì)算的例子，用來(lái)說(shuō)明該算法的優(yōu)化過(guò)程。

以下圖表示一個(gè)回收的廢舊品的拆卸樹(shù)，是一個(gè)3層可以拆卸成5個(gè)組件的產(chǎn)品。

計(jì)算中使用的符號(hào)說(shuō)明如表3.8解釋。用1表拆卸的層次，l=0,1,2，l=0表示產(chǎn)品本身。表示每個(gè)組件的編號(hào)，j=0,1,2,3,4，j=0表示產(chǎn)品。

以下各表給出了算法所需的生產(chǎn)數(shù)據(jù)。在這個(gè)算例中，假設(shè)有三種恢復(fù)策略可供選擇：處理，拆用配件和再制造，分別用r=1，r=2，r=3表示。為了貼近實(shí)際，假定并不是所有的組件都可以采取拆用配件和再制造策略，而且，再制造與組件的質(zhì)量狀態(tài)息息相關(guān)。表1反映了三種恢復(fù)策略下的利潤(rùn)情況。

對(duì)于產(chǎn)品結(jié)構(gòu)中的非原子組件，有兩種拆卸的方法：破壞性和非破壞性的，對(duì)于實(shí)際中有更多的拆卸方法，每一種拆卸方法所對(duì)應(yīng)的損耗率各不同的情況。也可以對(duì)此方法進(jìn)行擴(kuò)展，并沒(méi)有根本性的不同。用d=1，d=2分別代表破壞性和非破壞性拆卸。表2反映了兩種方法下的被拆卸件質(zhì)量完好率。不同的拆卸方法，其拆卸成本也不相同，考慮到這一點(diǎn)，表3反映了不同拆卸方法，不同拆卸目標(biāo)的拆卸成本情況。

表1 利潤(rùn)（整體恢復(fù)或拆卸后剩余部分進(jìn)行恢復(fù)）

表2 質(zhì)量轉(zhuǎn)化率

表3 拆卸成本

結(jié)論：（1）總是從產(chǎn)品0上拆卸1和2，并循環(huán)剩余部分。如果產(chǎn)品回收后是高質(zhì)量狀態(tài)，則采用非破壞性拆卸方法；否則采用破壞性拆卸方法。（2）由于w（1,1）=w（1,2）=2，所以對(duì)組件1始終采取循環(huán)恢復(fù)策略。（3）如果組件2在拆卸后是高質(zhì)量狀態(tài)，則拆卸組件3和4并循環(huán)剩余部分。如果組件2拆卸后是低質(zhì)量，則整體循環(huán)。（4）如果組件4在拆卸后是高質(zhì)量，則進(jìn)行再制造，否則進(jìn)行循環(huán)。（5）如果組件5在拆卸后是高質(zhì)量，則對(duì)其進(jìn)行再制造，否則進(jìn)行循環(huán)。

由此，得到了產(chǎn)品及組件在拆卸過(guò)程中各種情況下的處理對(duì)策。

4 結(jié)束語(yǔ)

文章采用圖論理論構(gòu)建了最短路徑算法，介紹了拆卸多提供源時(shí)的拆卸路徑問(wèn)題。隨后采用隨機(jī)動(dòng)態(tài)規(guī)劃理論，設(shè)計(jì)了產(chǎn)品的恢復(fù)優(yōu)化策略算法，較好地解決了多拆卸方法，多種恢復(fù)策略的問(wèn)題。

[1]H.R.KRIKKE.On a medium term product recovery and disposal strategy for durable assembly products[J].INT.J.PROD.RES,1998(36):111-139.