李姍姍

摘 要：分析了產品回收流程，指出在回收檢驗中心對產品進行質量檢測并分類處理，有助于降低逆向物流總運營成本。針對到這一特點，結合流量平衡與生產能力等特有約束，建立了新的3階段逆向物流網絡混合整數規(guī)劃模型，以確定回收檢驗中心、修復中心與垃圾處理中心的位置、數量與規(guī)模，以及對各網絡路徑上的物流流量進行分配?？紤]到其NP-hard特性，開發(fā)了遺傳算法，以獲得大規(guī)模問題的近似解。大規(guī)模實驗表明，所構建的混合整數規(guī)劃模型與遺傳算法是有效的，且遺傳算法的求解效率與求解質量也優(yōu)于LINGO軟件。

關鍵詞：質量檢測；逆向物流；數學模型；最優(yōu)解

中圖分類號：F713.2 文獻標識碼：A

Abstract： Through the analysis of handling procedure for returned product， it is suggested returned products should be disposed differently after quality inspection， so as to minimize the total costs. Considering the flow balance capacity limit and capacity limit constraints， a new mixed integer programming model for three-stage reverse logistics network is proposed， in order to obtain the quantity of various infrastructures， the scales and locations. Because it is NP-hard， a genetic algorithm is proposed. Random experiments show that the algorithm and model are effective. Meanwhile， when the experiments are larger， the genetic algorithm outperforms LINGO software on solving efficiency.

Key words： quality inspection； reverse logistics； mathematics model； optimal solution

0 引 言

物流網絡設計是供應鏈管理的一項重要內容，其以確定網絡中的設施數量、位置與規(guī)模，以及各類設施間的合理物流量為主要目的。由于在較短時間內很難改變一個現有設施的位置與規(guī)模，且需要付出較大的成本代價，因此物流網絡設計是一項戰(zhàn)略性決策，對其進行優(yōu)化的回報要遠遠大于其它戰(zhàn)術性與作業(yè)性決策問題。近年來，關于物流網絡設計的研究層出不窮，大致可分為三類：一是從正向角度進行優(yōu)化[1-3]；二是從逆向角度進行研究；三是對正向物流網絡與逆向物流網絡的整合性研究[4-5]。本文主要是面向第二類的研究。

逆向物流網絡可使一些有價值的產品得到回收再利用，并取得降低環(huán)境污染、提高資源利用率的目的?，F有研究中，何波等[6]研究了由客戶、回收點、回收中心組成的兩階段逆向物流網絡設計問題，以最小化總運營成本為目標，建立了數學規(guī)劃模型，并設計了模擬退火算法用于求解；熊中楷等[7]以回收中心利潤最大化為目標，建立了混合整數規(guī)劃模型，并通過粒子群算法求解；Demirel等[8]研究了由客戶、回收中心、拆解中心、再制造廠組成的逆向物流網絡問題，構建了混合整數規(guī)劃模型，并采用CPLEX求解；Lee等[9]以總運營成本最小化為目標，構建了數學規(guī)劃模型，求解方面采用了模擬退火算法；董景峰等[10]分析了由初級收集點、集中回收中心與回收處理工廠組成的逆向物流網絡優(yōu)化問題，以總運營成本最小化為目標，構建了數學規(guī)劃模型，并設計了相應的遺傳算法；黃錚[11]研究了由工廠、回收中心、客戶組成的三級逆向物流網絡，考慮到總成本最小化，建立了數學規(guī)劃模型，并設計了啟發(fā)式算法求解。

綜觀上述文獻，在回收產品的處理方式方面與現實情況存在一定的差距。文獻[6]與[7]均未對回收產品的處理情況進行規(guī)劃，其所設計的逆向物流網絡僅能保證產品會被送到回收中心，忽略了下一步的處理工作；文獻[8]至[11]雖考慮了回收產品的下一步處理情況，但其均假定回收產品必須被送到工廠進行再制造，這一點并不符合實際情況。實際上，回收產品的質量有好有壞，甚至有些已經是報廢品，將質量較低的產品送到工廠，從運輸資源、成本角度來看完全是一種浪費。因此在回收中心對產品質量進行檢測，并對不同類別的產品采用不同的處理方式是一項基本而重要的工作。

1 數學規(guī)劃

1.1 問題描述

本文所設計的逆向物流網絡結構如圖1所示，由客戶區(qū)域、回收檢驗中心、修復中心與垃圾處理中心組成，分為3個階段。回收產品由回收檢驗中心從客戶區(qū)域進行收集，并在回收檢驗中心進行質量檢測，從而被分為兩類產品：可再利用產品與廢棄品。前者將被送到修復中心進行質量修復，并重新進入銷售市場；而后者則被送到垃圾處理中心，以進行焚燒、填埋等處理工作。如前所述，該逆向物流網絡有助于避免產生額外的運輸成本，并可將合適的產品分配給合適的處理設施。

1.2 參數設置

定義I為可選的回收檢驗中心的集合，?i∈I；J為可選的修復中心的集合，?j∈J；K為可選的垃圾處理中心的集合，?k∈K；L為客戶區(qū)域的集合，?l∈L。

r：回收產品中可回收再利用的比率，即經回收檢驗中心到達修復中心的比率；

d：客戶區(qū)域l回收產品的供應數量；

c：客戶區(qū)域l至回收檢驗中心i的單位運輸成本；

f：回收檢驗中心i的年固定運營成本；

a：回收檢驗中心i至修復中心j的單位運輸成本；

v：修復中心j的年固定運營成本；

g：垃圾處理中心k的年固定運營成本；

h：回收檢驗中心i的單位處理成本；

n：垃圾處理中心k的單位處理成本；

m：修復中心j的單位修復成本；

t：回收檢驗中心i至垃圾處理中心k的單位運輸成本；

caf：回收檢驗中心i的最大產能；

cav：修復中心j的最大產能；

cag：垃圾處理中心k的最大產能。

決策變量：

q：從客戶區(qū)域l到回收檢驗中心i的產品數量；

z：從回收檢驗中心i送達修復中心j的產品數量；

w：從回收檢驗中心i送達垃圾處理中心k的產品數量；

s：0-1變量，若選中修復中心j，s=1，否則為0；

p：0-1變量，若選中回收檢驗中心i，p=1，否則為0；

y：0-1變量，若選中垃圾處理中心k，y=1，否則為0；

1.3 數學模型

目標函數：

目標函數式（1）為逆向物流網絡總成本最小，包括回收檢驗中心、修復中心與垃圾處理中心的固定成本、可變成本，以及3個階段間的運輸成本；式（2）表示每個客戶區(qū)域的回收產品必須被作業(yè)；式（3）與式（4）對經過回收檢驗中心前后的產品數量進行了平衡約束；式（5）、式（6）、式（7）為產能約束；式（8）與式（9）限定了決策變量的取值范圍。

2 遺傳算法

從所建模型可以看出，該問題屬于NP-hard問題，通過傳統的精確算法，如分支定界算法，解決其大規(guī)模優(yōu)化問題的效果較差。同時，鑒于遺傳算法的并行計算效率與全局搜索能力較高，因此本文采用遺傳算法求解。

2.1 染色體編碼

根據模型特點，本文采用帶優(yōu)先權的整數編碼規(guī)則。圖2所示為4個客戶區(qū)域、2個回收檢驗中心、4個修復中心與3個垃圾處理中心組成的染色體，分為3個子染色體，分別代表3個階段的物流運作方案。其中，子染色體1由4個客戶與2個回收檢驗中心組成，子染色體2由2個回收檢驗中心與4個修復中心組成，子染色體3由2個回收檢驗中心與3個垃圾處理中心組成，各子染色體的基因值分別代表該節(jié)點的優(yōu)先權，基因值越大，優(yōu)先權也就越大，則該節(jié)點的供給（或需求）情況也應該被優(yōu)先處理。

2.2 染色體解碼

3個子染色體的解碼過程相同。解碼時，依序分別對3個子染色體進行，即首先對子染色體1進行解碼，然后是子染色體2的解碼，最后是子染色體3的解碼。以圖2所示子染色體1為例，過程如下：

步驟1：選擇子染色體1中基因值最大的節(jié)點，并對該節(jié)點的集合歸屬做出判斷。如該染色體中最大的基因值為6，其對應客戶區(qū)域2。

步驟2：從運輸成本c矩陣中找出該節(jié)點對應的運輸成本最小的另一集合節(jié)點，組成一個節(jié)點對。如在客戶區(qū)域2對應的各回收檢驗中心的運輸成本分別為13 15，則對應的節(jié)點為回收檢驗中心1，此時，（客戶區(qū)域2，回收檢驗中心1）便組成了一個節(jié)點對。

步驟3：對該節(jié)點對的供應量與產能進行比較，選擇兩者中較小的量作為該節(jié)點對的物流量。如客戶區(qū)域2的供應量為150，回收檢驗中心1的產能為200，則客戶區(qū)域2到回收檢驗中心1的物流量為150。

步驟4：更新該節(jié)點對的相關信息。如客戶區(qū)域2的供應量更新為0，回收檢驗中心的產能更新為50。

步驟：5：當該基因值對應節(jié)點的供應量（或產能）被完全滿足時，將該基因值更新為0，并轉步驟6執(zhí)行；否則轉步驟2繼續(xù)執(zhí)行。

步驟6：當客戶區(qū)域的所有供應量均得到滿足后，解碼程序結束；否則轉步驟1繼續(xù)執(zhí)行。

子染色體1染色體解碼過程如表1所示。

子染色體1解碼結果如圖3所示：

2.3 初始種群與適值函數

為增強種群中個體的多樣性，采用隨機生成的方法，以提高遺傳算法的全局搜索能力。在本文中，目標函數值越小，個體的適應度應該越大，因此，適值函數如下：

此外，采用輪盤賭的種群選擇方式與精英保留策略。

2.4 交叉運算

交叉運算是生成種群新個體的一種重要方式，本文分別在各子染色體采用均勻交叉方式，見圖4。

2.5 變異運算

通過變異運算，遺傳算法可避免陷入局部優(yōu)化情況，從而達到全局優(yōu)化。針對染色體的特點，本文采用內部換位的變異方法，見圖5。

3 算例實驗

遺傳算法采用MATLAB7.0編程實現，遺傳算法與LINGO11.0軟件均在2GB內存，intel Core i5-3210M 2.50GHz的處理器的計算機上進行測試。

3.1 具體算例

某城市有8個居民區(qū)域的產品需要回收，可回收再利用比率分別為50%，回收檢驗中心、修復中心與垃圾處理中心的相關數據如表2所示。

3個階段逆向物流網絡單位運輸成本如表3所示。

算法參數通過多次實驗獲得：種群規(guī)模、交叉與變異概率、迭代次數分別為100，0.9，0.1，1 000。在MATLAB平臺上設計遺傳算法，程序運行133.52秒，目標函數值為81 190。求解結果見表4。

3.2 大規(guī)模實驗

設計10組算例，相關參數如表5所示：

這10組算例均可通過LINGO11.0軟件編程求解得出最優(yōu)結果，以評價遺傳算法的求解質量。遺傳算法的基本參數設置同上節(jié)所示，迭代次數更新為50 000次，同時加入一個求解時間約束，即將求解時間設定為5分鐘，時間到后算法即停止運算，并輸出最優(yōu)結果，并通過指標GAP=100%*（啟發(fā)式算法優(yōu)化解-LINGO最優(yōu)解）/LINGO最優(yōu)解，來對遺傳算法求解效果進行評價，見表6。

從表6可以看出，10組測試算例中，本文所設計的遺傳算法的GAP為0.36%～3.61%，求解效果非常理想。同時，從“計算時間”一項可以看出，隨著算例規(guī)模的增大，LINGO軟件的計算時間大大增加。在第10組算例中，求解時間用了將近16個小時，遠遠高于遺傳算法求解時間。而第10組算例的GAP僅為3.61%，可見遺傳算法的求解效率與求解質量都非常理想。

4 結束語

逆向物流網絡設計是供應鏈管理的一項重要內容。本文基于對回收產品質量檢驗并分類處理的基礎上，建立了新的3階段逆向物流網絡數學規(guī)劃模型?？紤]到其屬于NP-hard問題，有針對性地設計了遺傳算法，以求解其大規(guī)模優(yōu)化問題。實驗結果驗證了模型與算法的有效性。在未來的研究中，可融入資金預算、供應不穩(wěn)定性等現實因素。

參考文獻：

[1] Altiparmak F， Gen M， Lin L， et al. A genetic algorithm approach for multi-objective optimization of supply chain networks[J]. Computers & Industrial Engineering， 2006，51：196-215.

[2] Lee D H， Dong M. A heuristic approach to logistics network design for end-of-lease computer products recovery[J]. Transportation Research Part E， 2008，44：455-474.

[3] Costa A， Celano G， Fichera S， et al. A new efficient encoding/decoding procedure for the design of a supply chain network with genetic algorithms[J]. Computers & Industrial Engineering， 2010，59：986-999.

[4] El-Sayed M， Afia N， El-Kharbotly A. A stochastic model for forward-reverse logistics network design under risk[J]. Computer & Industrial Engineering， 2010，58：423-431.

[5] Ramezani M， Bashiri M， Tavakkoli-Moghaddam R. A new multi-objective stochastic model for a forward/reverse logistic network design with responsiveness and quality level[J]. Applied Mathematical Modelling， 2013，37：328-344.

[6] 何波，孟衛(wèi)東. 產品回收逆向物流網絡設計問題的兩階段啟發(fā)式算法[J]. 運籌與管理，2010，19（1）：73-79.

[7] 熊中楷，方衍，張聰譽. 以舊換新收購方式下的逆向物流網絡優(yōu)化設計[J]. 中國管理科學，2011，19（6）：65-72.

[8] Demirel O N， Gokcen H. A mixed-integer programming model for remanufacturing in reverse logistics environment[J]. International Journal of Advanced Manufacturing Technology， 2008，39：1197-1206.

[9] Lee D H， Dong M. Dynamic network design for reverse logistics operations under uncertainty[J]. Transportation Research Part E， 2009，45：61-71.

[10] 董景峰，王剛，呂民，等. 產品回收多級逆向物流網絡優(yōu)化設計模型[J]. 計算機集成制造系統，2008，14（1）：33-38.

[11] 黃錚. 廢棄物回收逆向物流網絡優(yōu)化設計[J]. 系統工程，2009，27（7）：49-53.