李姍姍

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

關(guān)鍵詞：質(zhì)量檢測；逆向物流；數(shù)學模型；最優(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 引 言

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

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

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

1 數(shù)學規(guī)劃

1.1 問題描述

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

1.2 參數(shù)設(shè)置

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

r：回收產(chǎn)品中可回收再利用的比率，即經(jīng)回收檢驗中心到達修復中心的比率；

d：客戶區(qū)域l回收產(chǎn)品的供應(yīng)數(shù)量；

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

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

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

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

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

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

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

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

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

caf：回收檢驗中心i的最大產(chǎn)能；

cav：修復中心j的最大產(chǎn)能；

cag：垃圾處理中心k的最大產(chǎn)能。

決策變量：

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

z：從回收檢驗中心i送達修復中心j的產(chǎn)品數(shù)量；

w：從回收檢驗中心i送達垃圾處理中心k的產(chǎn)品數(shù)量；

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

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

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

1.3 數(shù)學模型

目標函數(shù)：

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

2 遺傳算法

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

2.1 染色體編碼

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

2.2 染色體解碼

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

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

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

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

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

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

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

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

子染色體1解碼結(jié)果如圖3所示：

2.3 初始種群與適值函數(shù)

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

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

2.4 交叉運算

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

2.5 變異運算

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

3 算例實驗

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

3.1 具體算例

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

3個階段逆向物流網(wǎng)絡(luò)單位運輸成本如表3所示。

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

3.2 大規(guī)模實驗

設(shè)計10組算例，相關(guān)參數(shù)如表5所示：

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

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

4 結(jié)束語

逆向物流網(wǎng)絡(luò)設(shè)計是供應(yīng)鏈管理的一項重要內(nèi)容。本文基于對回收產(chǎn)品質(zhì)量檢驗并分類處理的基礎(chǔ)上，建立了新的3階段逆向物流網(wǎng)絡(luò)數(shù)學規(guī)劃模型?？紤]到其屬于NP-hard問題，有針對性地設(shè)計了遺傳算法，以求解其大規(guī)模優(yōu)化問題。實驗結(jié)果驗證了模型與算法的有效性。在未來的研究中，可融入資金預算、供應(yīng)不穩(wěn)定性等現(xià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)東. 產(chǎn)品回收逆向物流網(wǎng)絡(luò)設(shè)計問題的兩階段啟發(fā)式算法[J]. 運籌與管理，2010，19（1）：73-79.

[7] 熊中楷，方衍，張聰譽. 以舊換新收購方式下的逆向物流網(wǎng)絡(luò)優(yōu)化設(shè)計[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] 董景峰，王剛，呂民，等. 產(chǎn)品回收多級逆向物流網(wǎng)絡(luò)優(yōu)化設(shè)計模型[J]. 計算機集成制造系統(tǒng)，2008，14（1）：33-38.

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