基于逆向物流的拆卸和恢復策略優化算法

史 云，陳勁杰

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

0 引 言

對回收的廢舊產品或部件進行拆卸和再利用是逆向物流的重要組成部分。它是逆向物流研究中的技術難點，涉及到產品的幾何結構的可拆卸分析，多種拆卸工藝，產品的優化拆卸路徑和過程分析，以及恢復策略等方面。

本文主要采用最短路徑算法解決產品的最優拆卸路徑的選擇問題，隨后采用隨機動態規劃算法解決產品回收后綜合各種因素的恢復策略優化問題。

1 一維拆卸最短路徑算法

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

1.1 算法基本思想。本文用有向圖模型建立產品的拆卸樹狀結構：把產品及其組件看作節點，把弧看作拆卸路徑，弧的方向表示了被拆卸件從拆卸基體上拆離的這種關系。權表示拆卸時間，按照不同要求也可以換成拆卸成本等參數。由于樹就是無圈連通圖，是同一個理論體系，因此，采用圖論中的最短路徑算法對拆卸樹進行分析。

目前，公認的較好的最短路徑計算方法是Dijkstra方法。該方法的基本思路是：從起始點出發，逐步地向外探索最短路徑。執行過程中，與每個點對應，記錄標號，標號或表示從起始點到該點的最短路徑權，或者從起始點到該點最短路的權上限。方法的每一步是去修改T標號，并且把某一個具有T標號的點改變為具有P標號的點，從而使圖中的具有P標號的點多一個。因此，經過多步迭代就可以得到從起始點到各點的最短路。

按照該算法計算一次就可以得到從產品拆卸任一個組件的最短路徑，即得到拆卸需要耗費的時間和拆卸的先后順序。

2 隨機動態規劃算法[1]

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

為了優化拆卸和恢復策略，必須考慮質量因素。實際應用中，回收產品的質量往往影響它的拆卸和恢復策略。例如，計算機的回收利用。目前，計算機的更新速度非常快，如過一臺計算機的出廠日期在半年以內，那么可以對其實施再制造策略，否則只能實施拆用配件或整修策略。

同時，眾多的拆卸工藝（破壞性的、非破壞性的）以及部分拆卸的情況也必須在算法中考慮，針對高恢復利潤的部件的部分拆卸要比完全拆卸更加經濟。因此，算法應該考慮回收產品和拆卸子件的質量狀態，不同的拆卸工藝（種類），并且允許部分拆卸。

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

下表對算法中使用的符號進行了說明：

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

2.2 算法原理和流程。把產品回收后按照產品的拆卸樹結構，進行層層拆卸和恢復的過程，可以看作是一個多階段決策問題。在它的每一個階段都需要做出決策，從而使整個過程達到最好的活動效果。各個階段決策的選取不是任意確定的，它依賴于當前面臨的狀態，且影響以后發展。當各個階段決策確定后，就組成了一個決策序列，因而也就決定了整個過程的一個完整最優解決方案。而動態規劃恰恰是用來解決多階段決策問題的利器，因此，本文采用動態規劃原理構建算法模型。

首先從產品結構的最底層L開始，即只包含原子型組件的層，對該層的所有組件（質量狀態是已知的），比較所有可行的恢復策略所產生利潤，從中選取最優的策略。然后，遞推到上一層L-1，類似的，得到該層上的所有原子型組件的最優修復策略和對應的利潤。而對于L-1層上的非原子型組件，比較直接恢復利潤（不拆卸）和拆卸后子件集的恢復利潤之和，然后選取最大值作為該組件的利潤，同時得到了該非原子組件的策略，即是整體采用恢復策略還是進一步拆卸？如果進一步拆卸，應從該組件上拆卸哪些子件下來進行恢復。這樣一直遞推到根節點產品一級，從而決定了整個產品的再利用策略。

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

達到最大值的d和S以及 C（j,q1|d,）S 的r分別是最優拆卸工藝（種類），最優拆卸目標子件集合和最優恢復策略。

最后給出的拆卸和恢復優化策略就是一套有條件的規則。對于一個回收的廢舊產品，由算法根據每個組件的質量狀態，組件及其子件間的質量轉換概率來決定拆卸深度，拆卸集合以及每個組件的采用的策略。例如，對回收的廢舊液壓油泵。初步拆卸后，如果齒輪支座和齒輪工作正常，則只需進行清洗和潤滑；否則繼續拆卸或替換。

3 數值例子

考慮一個數字計算的例子，用來說明該算法的優化過程。

以下圖表示一個回收的廢舊品的拆卸樹，是一個3層可以拆卸成5個組件的產品。

計算中使用的符號說明如表3.8解釋。用1表拆卸的層次，l=0,1,2，l=0表示產品本身。表示每個組件的編號，j=0,1,2,3,4，j=0表示產品。

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

對于產品結構中的非原子組件，有兩種拆卸的方法：破壞性和非破壞性的，對于實際中有更多的拆卸方法，每一種拆卸方法所對應的損耗率各不同的情況。也可以對此方法進行擴展，并沒有根本性的不同。用d=1，d=2分別代表破壞性和非破壞性拆卸。表2反映了兩種方法下的被拆卸件質量完好率。不同的拆卸方法，其拆卸成本也不相同，考慮到這一點，表3反映了不同拆卸方法，不同拆卸目標的拆卸成本情況。

表1 利潤（整體恢復或拆卸后剩余部分進行恢復）

表2 質量轉化率

表3 拆卸成本

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

由此，得到了產品及組件在拆卸過程中各種情況下的處理對策。

4 結束語

文章采用圖論理論構建了最短路徑算法，介紹了拆卸多提供源時的拆卸路徑問題。隨后采用隨機動態規劃理論，設計了產品的恢復優化策略算法，較好地解決了多拆卸方法，多種恢復策略的問題。

[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.