集成選址—路徑—庫(kù)存問題的逆向物流網(wǎng)絡(luò)優(yōu)化

李昌兵，張斐敏

（重慶郵電大學(xué) 經(jīng)濟(jì)管理學(xué)院管理工程系，重慶 400065）

0 引言

逆向物流指在供應(yīng)鏈管理中，生產(chǎn)者對(duì)從消費(fèi)者處回收到的全部或部分廢舊產(chǎn)品進(jìn)行再利用、再制造或直接廢棄處理的過程［1］。逆向物流系統(tǒng)具有高度復(fù)雜性、多樣性、供應(yīng)失衡性等特性，這些特性使得系統(tǒng)的運(yùn)作更依賴于物流網(wǎng)絡(luò)，因此在管理中的首要任務(wù)是優(yōu)化設(shè)計(jì)逆向物流網(wǎng)絡(luò)［2］。設(shè)施選址、運(yùn)輸線路安排和庫(kù)存策略是逆向物流網(wǎng)絡(luò)優(yōu)化中的三大關(guān)鍵問題，傳統(tǒng)上一般將其作為獨(dú)立的決策分別進(jìn)行研究［3-4］或者兩兩組合進(jìn)行研究［5-7］。但事實(shí)上，三者之間具有密切的聯(lián)系，任何一方的變動(dòng)都會(huì)影響其他兩方的決策。從系統(tǒng)的角度看，有必要對(duì)集成的“選址—路徑—庫(kù)存問題”（Location-Routing-Inventory Problem，LRIP）進(jìn)行研究。

目前，集成的物流網(wǎng)絡(luò)優(yōu)化研究多集中在正向LRIP［8-11］，只有少部分學(xué)者研究了逆向LRIP。文獻(xiàn)［12］提出多周期的廢舊汽車系統(tǒng)網(wǎng)絡(luò)優(yōu)化模型，該模型通過路徑優(yōu)化的方法計(jì)算回收的運(yùn)輸成本，并運(yùn)用混合整數(shù)規(guī)劃方法對(duì)配送進(jìn)行優(yōu)化，以確定最佳的處理中心位置和每周期庫(kù)存數(shù)量；文獻(xiàn)［13］建立了一個(gè)回收商管理庫(kù)存模式下的多周期逆向物流網(wǎng)絡(luò)優(yōu)化模型，根據(jù)客戶點(diǎn)的廢舊產(chǎn)品數(shù)量決定當(dāng)期是否對(duì)客戶點(diǎn)進(jìn)行回收，并設(shè)計(jì)了一種基于系統(tǒng)總成本最小的兩階段啟發(fā)式算法進(jìn)行求解；文獻(xiàn)［14］建立了一個(gè)企業(yè)閉環(huán)物流系統(tǒng)中的LRIP模型，綜合考慮了物流設(shè)施選址、車輛配送／回收路線安排和新產(chǎn)品／回收產(chǎn)品的庫(kù)存控制等問題；文獻(xiàn)［15］研究了垃圾回收系統(tǒng)的LRIP模型，集成考慮了回收中轉(zhuǎn)站選址、車輛路線安排和回收中轉(zhuǎn)站庫(kù)存控制問題，建立了一個(gè)多周期LRIP模型。

上述逆向LRIP 模型主要存在兩類不足：①多數(shù)研究?jī)H限于獨(dú)立的逆向物流系統(tǒng)，未將逆向物流系統(tǒng)與傳統(tǒng)的物流系統(tǒng)有機(jī)整合在一起；②多數(shù)研究都假設(shè)回收產(chǎn)品當(dāng)期均要回載完畢，未考慮回收產(chǎn)品回載的可分性。顯然，利用前向配送車輛的回程來回載回收產(chǎn)品，比派出車輛分別進(jìn)行配送和回收活動(dòng)節(jié)約成本；又由于回收產(chǎn)品沒有新產(chǎn)品那么強(qiáng)的時(shí)效性要求，可以根據(jù)實(shí)際運(yùn)載能力對(duì)回收產(chǎn)品進(jìn)行分批回收，從而降低成本。為此，本文對(duì)定位—運(yùn)輸路線安排問題進(jìn)行擴(kuò)展研究，建立了一個(gè)逆向物流的LRIP 模型。其中，在路徑優(yōu)化部分考慮正向配送和逆向回載相整合的運(yùn)輸策略，在庫(kù)存控制方面考慮回收產(chǎn)品的可分批運(yùn)輸特點(diǎn)，引入庫(kù)存限制和庫(kù)存成本懲罰，以解決更加復(fù)雜的逆向物流網(wǎng)絡(luò)布局問題，進(jìn)而合理設(shè)置物流網(wǎng)絡(luò)中的設(shè)施節(jié)點(diǎn)，優(yōu)化運(yùn)輸路線，調(diào)節(jié)各節(jié)點(diǎn)的庫(kù)存方案，從而有效降低逆向回收物流系統(tǒng)的運(yùn)作成本。

1 模型的建立

1.1 問題描述

建立一個(gè)同時(shí)考慮正向配送和回載可分的閉環(huán)物流網(wǎng)絡(luò)優(yōu)化系統(tǒng)，包括若干個(gè)配送中心和相對(duì)應(yīng)的客戶點(diǎn)。每個(gè)周期各車隊(duì)從配送中心出發(fā)，一一訪問服務(wù)范圍內(nèi)的客戶點(diǎn)，同時(shí)完成配送和回收任務(wù)，最終返回配送中心。各客戶點(diǎn)的?。拓浟坎荒艹^車輛的載重能力，同時(shí)受冗余庫(kù)存限制。根據(jù)冗余庫(kù)存限制，將回收產(chǎn)品分為兩部分：①為滿足冗余庫(kù)存必須回收的部分；②可當(dāng)期回收也可滯留下期回收的部分。當(dāng)期滯留的回收產(chǎn)品在客戶處有庫(kù)存成本。為使系統(tǒng)總成本最小，需要考慮的問題包括建立配送中心的數(shù)量、地址、每個(gè)周期運(yùn)輸車輛路徑安排，以及各客戶點(diǎn)的滯留回收產(chǎn)品的數(shù)量等。

1.2 假設(shè)條件

模型的假設(shè)條件如下：

（1）各類物流設(shè)施之間的距離已知。

（2）各個(gè)周期要回載的回收產(chǎn)品已經(jīng)從單個(gè)用戶回收到各客戶點(diǎn)，不考慮單個(gè)用戶到客戶點(diǎn)之間的運(yùn)輸費(fèi)用。

（3）各個(gè)客戶點(diǎn)每周期新產(chǎn)品的需求數(shù)量和新產(chǎn)生的回收產(chǎn)品數(shù)量滿足正態(tài)分布。

（4）新產(chǎn)品的配送必須在當(dāng)期完成，而回收產(chǎn)品除了為滿足冗余庫(kù)存必須回收的部分外，剩余部分可選擇部分回收或不回收。

（5）庫(kù)存費(fèi)用指當(dāng)期未被回收的回收產(chǎn)品的存儲(chǔ)費(fèi)用。

（6）產(chǎn)品的運(yùn)輸費(fèi)用與距離呈簡(jiǎn)單線性關(guān)系。

（7）各客戶點(diǎn)每周期的冗余庫(kù)存已知。

（8）運(yùn)輸車輛從配送中心發(fā)車時(shí)會(huì)產(chǎn)生發(fā)車費(fèi)用。

1.3 模型參數(shù)和變量

（1）模型參數(shù)

N為客戶點(diǎn)數(shù)量；

i為客戶點(diǎn)編號(hào)（1≤i≤N）；

M為候選配送中心數(shù)量；

j為配送中心編號(hào)（N+1≤j≤N+M）；

g為客戶點(diǎn)或配送中心編號(hào)（1≤g≤N+M）；

h為客戶點(diǎn)或配送中心編號(hào)（1≤h≤N+M）；

K為車輛數(shù)量；

k為車輛編號(hào)（1≤k≤K）；

T為計(jì)劃期長(zhǎng)度；

t為周期編號(hào)（1≤t≤T）；

NQit為i客戶點(diǎn)在t周期的新產(chǎn)品需求量；

RQit為i客戶點(diǎn)在t周期新產(chǎn)生的回收產(chǎn)品數(shù)量；

Sit為i客戶點(diǎn)在t周期末的待回收產(chǎn)品數(shù)量，Sit=Si，t-1+RQit-RDjtk；

Dgh為物流設(shè)施之間的距離；

Ctr為單位距離的運(yùn)輸成本；

Cs為單位周期單位數(shù)量的庫(kù)存成本；

Fj為j配送中心的建設(shè)費(fèi)用；

C為車輛的容量；

Ri為i客戶點(diǎn)的冗余庫(kù)存；

Vi為i客戶點(diǎn)的最大庫(kù)存容量。

（2）模型決策變量

NDtki為i客戶點(diǎn)在t周期由車輛k配送的新產(chǎn)品數(shù)量；

RDtki為i客戶點(diǎn)在t周期由車輛k回收的回收產(chǎn)品數(shù)量；

1.4 模型

根據(jù)以上分析，構(gòu)建一個(gè)混合整數(shù)非線性規(guī)劃的數(shù)學(xué)模型。

目標(biāo)函數(shù)：

目標(biāo)函數(shù)表示在滿足各種約束的情況下，使系統(tǒng)的總成本最小。其中：第一部分表示配送中心建設(shè)成本；第二部分表示發(fā)車費(fèi)；第三部分表示運(yùn)輸成本；第四部分表示未被回收的產(chǎn)品的庫(kù)存成本。

約束（2）和約束（3）是車容量限制。約束（2）保證車輛k在t周期所經(jīng)沿線的送貨量小于車容量；約束（3）保證從該客戶點(diǎn)回載的回收產(chǎn)品數(shù)量不超過當(dāng)前車輛的剩余運(yùn)載能力；約束（4）確保每個(gè)客戶點(diǎn)在每周期至少被訪問一次；約束（5）為線路的連續(xù)性限制；約束（6）表示車輛只能從所屬的配送中心出發(fā)，且每周期內(nèi)只能出發(fā)一次；約束（7）表示車輛只能服務(wù)所屬配送中心對(duì)應(yīng)的客戶點(diǎn)；約束（8）必須滿足每周期各客戶點(diǎn)的配送需求；約束（9）表示回載產(chǎn)品數(shù)量不能超過可回載數(shù)量；約束（10）表示剩余產(chǎn)品數(shù)必須滿足冗余庫(kù)存限制。

2 算法步驟

同時(shí)考慮正向配送和回載可分的閉環(huán)LRIP模型是一個(gè)NP難題，隨著問題規(guī)模的增大，可行解的數(shù)量呈指數(shù)增長(zhǎng)，用傳統(tǒng)的優(yōu)化方法求解將非常困難。參考文獻(xiàn)［8，16］，針對(duì)所建模型的特點(diǎn)，本文設(shè)計(jì)了一種兩階段啟發(fā)式算法：階段一采用先“選址—分配”、后安排運(yùn)輸路徑和庫(kù)存的方法，求得滿足問題約束條件的初始解；階段二在階段一所得初始解的基礎(chǔ)上采用改進(jìn)的搜索算法搜尋更優(yōu)解。算法如下：

（1）獲得初始解

步驟1 模型各參數(shù)初始化賦值，并令t=1；將各客戶點(diǎn)分配給離其最近的配送中心，將配送中心j對(duì)應(yīng)的客戶點(diǎn)放入集合Fj（t）中；令j=N+1。

步驟2 對(duì)Fj（t）中客戶點(diǎn)i計(jì)算bit=NQit-Pit。其中：Pit=Ri+Sit-Vi為i點(diǎn)在t周期必須回載的最小回收產(chǎn)品數(shù)量；bit為i點(diǎn)在t周期的正向配送數(shù)量與必須回收產(chǎn)品數(shù)量的差額。

步驟3 計(jì)算j回收中心在t周期的單車平均剩余量時(shí)原問 題有解；為j配送中心t周期需要的車輛數(shù)。

步驟4 將所有bit平均分成Kjt個(gè)子集θ1，θ2，…，θKjt。對(duì)每個(gè)子集都有：①為bit的標(biāo)準(zhǔn)差；②t≤T。在所有滿足這種條件的子集空間中尋找一條總路徑最短的子集集合，設(shè)為θ′1，θ′2，…，θ′Kjt，該集合即為綜合正向和逆向物流的最優(yōu)分組。

步驟5 進(jìn)一步優(yōu)化所得的最優(yōu)子集集合。集合中的單個(gè)子集表示單個(gè)車輛所要服務(wù)的客戶點(diǎn)集合，組內(nèi)優(yōu)化即相當(dāng)于一個(gè)旅行商問題（Traveling Saleman Problem，TSP），而某些客戶點(diǎn)受冗余庫(kù)存限制有bit＜0，因此解決TSP 問題的傳統(tǒng)方法不完全適用于本問題。這里設(shè)計(jì)一種插入啟發(fā)式算法來求解最優(yōu)路徑，然后運(yùn)用線性規(guī)劃求解最優(yōu)回載配置策略。關(guān)于子集中路徑和回載配置的詳細(xì)優(yōu)化方法請(qǐng)參見文獻(xiàn)［17］。將未被回載的回收產(chǎn)品滯留到下一周期回收。

步驟6 令j=j+1，若j＞N+M，則執(zhí)行步驟7；否則執(zhí)行步驟2。

步驟7 令t=t+1，若t≤T，則執(zhí)行步驟2；否則執(zhí)行步驟8。

步驟8 輸出求得的各周期最優(yōu)路徑安排和回載配置方案，計(jì)算此時(shí)的配送中心建設(shè)成本、發(fā)車費(fèi)、運(yùn)輸成本和庫(kù)存成本，各項(xiàng)成本之和即為初始解Cost。

（2）改進(jìn)初始解

步驟9 記此時(shí)被選中的配送中心數(shù)目為NUM。按照系統(tǒng)總成本最小原則選擇關(guān)閉一個(gè)回收中心。令NUM=NUM-1，t=1，并執(zhí)行步驟1～步驟8，求得此時(shí)的系統(tǒng)總成本，記為Cost′。

步驟10 若Cost′＜Cost，則令Cost=Cost′，執(zhí)行步驟11；否則直接轉(zhuǎn)步驟11。

步驟11 若NUM=1，則執(zhí)行步驟12；否則，返回步驟9。

步驟12 隨機(jī)選擇一個(gè)開放的配送中心和一個(gè)關(guān)閉的配送中心，將其狀態(tài)互換，并執(zhí)行步驟1～步驟8，求得此時(shí)的系統(tǒng)總成本，記為Cost′。

步驟13 若Cost′＜Cost，則令Cost=Cost′，執(zhí)行步驟14；否則令max＿swap=max＿swap+1，再執(zhí)行步驟14。

步驟14 若max＿swap＞default＿value，則執(zhí)行步驟15；否則執(zhí)行步驟13。

步驟15 算法結(jié)束，輸出最終結(jié)果。

3 實(shí)驗(yàn)與計(jì)算

本章構(gòu)建了一個(gè)閉環(huán)物流網(wǎng)絡(luò)。該網(wǎng)絡(luò)有5個(gè)候選配送中心（編號(hào)為1～5）和60個(gè)客戶點(diǎn)（編號(hào)為6～65），其位置在100×100的平面隨機(jī)產(chǎn)生，各節(jié)點(diǎn)之間的距離用平面坐標(biāo)上的歐氏距離表示。設(shè)車容量C=600，各客戶點(diǎn)各周期的新產(chǎn)品需求數(shù)NQit服從正態(tài)分布N（120，252），待回收產(chǎn)品數(shù)RQit服從正態(tài)分布N（100，502），單位距離運(yùn)輸費(fèi)用Ctr=1，單位周期單位數(shù)量待回收產(chǎn)品的庫(kù)存費(fèi)用Cs=2，最大庫(kù)存量Vi=200，冗余庫(kù)存Ri=180，五個(gè)候選回收中心的建設(shè)費(fèi)分別為Fj=（180 000，90 000，130 000，105 000，95 000），周期T=500。

采用Visual C++6.0 設(shè)計(jì)程序?qū)崿F(xiàn)上述算法，運(yùn)行環(huán)境為：3.30GHz CPU，4G 內(nèi)存。得到該物流網(wǎng)絡(luò)的最佳物流運(yùn)作總成本為1 015 340，該最優(yōu)解選中第2，3，4配送中心。其中：分給2號(hào)回收中心的客戶點(diǎn)為（10，14，18，19，31，33，44，49，53，59，60，62，64），分給3 號(hào)回收中心的客戶點(diǎn)為（9，16，21，22，27，29，35，36，37，38，41，42，43，45，46，48，50，51，54，58），分給4 號(hào)回收中心的客戶點(diǎn)為（6，7，8，11，12，13，15，17，20，23，24，25，26，28，30，32，34，39，40，47，52，55，56，57，61，63，65）。在此以t=2時(shí)為例，給出各節(jié)點(diǎn)的運(yùn)輸路徑安排和各客戶點(diǎn)的被回載產(chǎn)品數(shù)量的計(jì)算結(jié)果。運(yùn)輸路徑安排如圖1所示。分別為2-10-18-14-31-33-2，2-19-60-62-53-2，2-44-49-64-59-2，3-37-50-9-16-3，3-35-43-36-46-3，3-48-27-51-21-22-3，3-58-29-45-41-3，3-38-54-42-3，4-34-6-7-55-4，4-25-57-15-4，4-47-61-39-40-32-4，4-8-28-30-13-12-4，4-24-11-56-26-63-4，4-65-52-23-20-17-4。

各客戶點(diǎn)的回載數(shù)量如表1所示。

表1 t＝2時(shí)各客戶點(diǎn)的回載量

計(jì)算出傳統(tǒng)模式下（正向物流活動(dòng)和逆向物流活動(dòng)獨(dú)立進(jìn)行，且回收產(chǎn)品當(dāng)期都要回載完畢）對(duì)同一組示例數(shù)據(jù)的優(yōu)化結(jié)果，并與本文提出的模型優(yōu)化結(jié)果進(jìn)行對(duì)比，比較結(jié)果如表2所示。從表2可以看出，前一種模式下雖然增加了客戶點(diǎn)的庫(kù)存費(fèi)用，但總費(fèi)用卻降低了29.06%。這是因?yàn)檎蛭锪髋c逆向物流的運(yùn)輸整合大大降低了系統(tǒng)的運(yùn)輸費(fèi)用。另外，本文提出的回收產(chǎn)品部分回載、部分滯留的庫(kù)存策略也在一定程度上減少了派車次數(shù)，降低了發(fā)車費(fèi)用。

表2 不同模型優(yōu)化結(jié)果對(duì)比

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

本文從逆向物流系統(tǒng)集成優(yōu)化的角度，針對(duì)配送中心選址、車輛路徑安排以及客戶點(diǎn)的庫(kù)存控制的聯(lián)合決策問題，提出一個(gè)非線性混合整數(shù)規(guī)劃模型，并設(shè)計(jì)了一種兩階段啟發(fā)式算法來求解模型。最后通過算例驗(yàn)證了模型和算法的可行性。仿真結(jié)果表明，本文所考慮的正／逆向物流的運(yùn)輸整合和客戶點(diǎn)的庫(kù)存控制策略在優(yōu)化逆向物流方面效果顯著。此外，逆向物流系統(tǒng)存在高度的不確定性，主要體現(xiàn)在回收產(chǎn)品在數(shù)量和時(shí)間上的不確定性，同時(shí)其質(zhì)量和組成成分也不確定，因此進(jìn)一步的研究可考慮解決不確定環(huán)境下的逆向物流網(wǎng)絡(luò)系統(tǒng)優(yōu)化問題。

［1］DYCKHOFF H，LACKES R，REESE J.Supply chain management and reverse logistics［M］.Berlin，Germany：Springer-Verlag，2004.

［2］DA Qingli，HUANG Zuqing，ZHANG Qin.Current and future studies on structure of the reverse logistics system：a review［J］.Chinese Journal of Management Science，2004，12（1）：131-138（in Chinese）.［達(dá)慶利，黃祖慶，張 欽.逆向物流系統(tǒng)結(jié)構(gòu)研究的現(xiàn)狀及展望［J］.中國(guó)管理科學(xué)，2004，12（1）：131-138.］

［3］ZHOU Gengui，CAO Zhenyu.A genetic algorithm approach to location-allocation problem in reverse logistic network［J］.Chinese Journal of Management Science，2005，13（1）：42-47（in Chinese）.［周根貴，曹振宇.遺傳算法在逆向物流網(wǎng)絡(luò)選址問題中的應(yīng)用研究［J］.中國(guó)管理科學(xué)，2005，13（1）：42-47.］

［4］LI Bo，ZENG Chengpei.Method of multi-period dynamic location in reverse logistic network［J］.Journal of Management Science in China，2008，11（5）：76-84（in Chinese）.［李 波，曾成培.一種逆向物流網(wǎng)絡(luò)的多期動(dòng)態(tài)選址方法［J］.管理科學(xué)學(xué)報(bào)，2008，11（5）：76-84.］

［5］NAGY G，SALHI S.Location-routing issues，models and methods［J］.European Journal of Operational Research，2007，177（2）：649-672.

［6］LIU S C，CHUNG C H.A heuristic method for the vehicle routing problem with backhauls and inventory problem［J］.The International Journal of Advanced Manufacturing Technology，2005，26（4）：372-381.

［7］KLEYWEGT A J，NORI V S，SAVELSBERGH M W P.Dynamic programming approximations for a stochastic inventory routing problem［J］.Transportation Science，2004，38（1）：42-70.

［8］LIU S C，LEE S B.A two-phase heuristic method for the multi-depot location routing problem taking inventory control decisions into consideration［J］.The Inventory Journal of Advanced Manufacturing Technology，2003，22（11／12）：941-950.

［9］CUI Guangbin，LI Yijun.Study on the combined location routing and inventory problem in logistics system based on bi-level programming［J］.Systems Engineering—Theory &Practice，2007，27（6）：49-55（in Chinese）.［崔廣彬，李一軍.基于雙層規(guī)劃的物流系統(tǒng)集成定位—運(yùn)輸路線安排—庫(kù)存問題研究［J］.系統(tǒng)工程理論與實(shí)踐，2007，27（6）：49-55.］

［10］TAI H W，LOW C，BAI J W.Heuristic solutions to multidepot location-routing problems［J］.Computer Operational Research，2002，10（29）：1393-1415.

［11］WANG Yunfa，LI Bo.Research on coordinated productioninventory-distribution planning problem based on tabu search［J］.Information and Control，2012，41（3）：391-396（in Chinese）.［王運(yùn)發(fā)，李 波.基于禁忌搜索的生產(chǎn)-庫(kù)存-配送協(xié)同計(jì)劃問題研究［J］.信息與控制，2012，41（3）：391-396.］

［12］LEBLANC H M，F(xiàn)LEUREN H A，KRIKKE H R.Redesign of a recycling system for LPG-tanks［J］.OR Spectrum，2004，26（2）：283-304.

［13］DAI Ying，MA Zujun，ZHU Daoli.Multi-period locationrouting-inventory problem for reverse logistics with collector managed inventory［J］.Industrial Engineering and Management，2010，15（5）：1-6（in Chinese）.［代 穎，馬祖軍，朱道立.回收商管理庫(kù)存下逆向物流多周期LRIP［J］.工業(yè)工程與管理，2010，15（5）：1-6.］

［14］WANG Chanchan，MA Zujun.Stochastic dynamic location-routing-inventory problem in closed-loop logistics system for reusing end-of-use products［C］／／Proceedings of the 2008International Conference on Intelligent Computation Technology and Automation.Washingtion，D.C.，USA：IEEE，2008，2：691-695.

［15］LI Huajun，MA Zujun.The stochastic location-routing-inventory problem in reverse logistics systems for municipal solid waste［C］／／Logistics：The Emerging Frontiers of Transportation and Development in China.Reston，Va.，USA：ASCE，2008：3565-3571.

［16］WANG Fahong，DA Qingli.The multiple-depot &multiplevehicle transportation strategy in closed-loop chain with split pick-ups［J］.Journal of Industrial Engineering／Engineering Management，2008，22（2）：46-50（in Chinese）.［王發(fā)鴻，達(dá)慶利.回載可分的閉環(huán)供應(yīng)鏈多配送中心多車輛運(yùn)輸策略［J］.管理工程學(xué)報(bào)，2008，22（2）：46-50.］

［17］WANG Fahong，DA Qingli.Transportation strategy of single vehicle in reverse logistics［J］.Journal of Southeast University：Natural Science Edition，2006，36（1）：156-160（in Chinese）.［王發(fā)鴻，達(dá)慶利.逆向物流單車運(yùn)輸策略［J］.東南大學(xué)學(xué)報(bào)：自然科學(xué)版，2006，36（1）：156-160.］