劉 靜，賈 濤，吉 哲

（西安交通大學(xué) 管理學(xué)院，西安 710049）

0 引言

實(shí)物商品供應(yīng)鏈內(nèi)，企業(yè)運(yùn)作管理的主要問(wèn)題之一是如何達(dá)到供給與需求之間的平衡。除了調(diào)整運(yùn)作能力之外，企業(yè)實(shí)際上常常通過(guò)影響需求的策略以達(dá)到匹配的目標(biāo)，其中訂單積壓（延遲交貨）是需求選擇策略中有效的方法之一，從而在企業(yè)中有著廣泛的應(yīng)用。實(shí)物商品中，易腐品作為一大類(lèi)產(chǎn)品與人們的生活緊密相關(guān)，例如蔬果海鮮、奶制品等，這類(lèi)產(chǎn)品由于本身的物理特性等原因，其效用會(huì)隨著時(shí)間的推移而改變，并產(chǎn)生額外的腐敗成本。因而在易腐品庫(kù)存管理中，引入訂單延后策略不但能降低庫(kù)存成本，還可以減少腐敗損失，并通過(guò)優(yōu)化缺貨時(shí)間，權(quán)衡庫(kù)存、腐敗成本的減少以及缺貨損失的增加，以提高供應(yīng)鏈整體的運(yùn)作績(jī)效，從而具有理論和現(xiàn)實(shí)意義。

有關(guān)易腐品配送路徑的問(wèn)題，較多的出現(xiàn)在車(chē)輛路徑問(wèn)題(VRP)的研究中，例如Hemmelmayr等的血液配送問(wèn)題。而在眾多庫(kù)存路徑問(wèn)題中，以易腐品為背景的還不常見(jiàn)，能綜合考慮允許缺貨的庫(kù)存策略和配送路徑網(wǎng)絡(luò)的研究也比較少。在現(xiàn)實(shí)的易腐品分銷(xiāo)渠道中，需求選擇、庫(kù)存控制和配送調(diào)度構(gòu)成了運(yùn)作計(jì)劃體系的重要組成部分，因此，綜合考慮易腐商品的訂單延后、庫(kù)存和配送路徑?jīng)Q策，為一體化決策供應(yīng)鏈的優(yōu)化提供了另外一種選擇。本文將以單一易腐品為對(duì)象，在一個(gè)供應(yīng)商和多個(gè)零售商組成的供應(yīng)鏈中，研究允許缺貨的易腐品庫(kù)存路徑問(wèn)題，通過(guò)模型構(gòu)建證明目標(biāo)函數(shù)的性質(zhì)，以此為基礎(chǔ)設(shè)計(jì)求解算法對(duì)問(wèn)題進(jìn)行求解；并結(jié)合數(shù)值算例說(shuō)明實(shí)踐中易腐品分銷(xiāo)渠道內(nèi)常見(jiàn)的成本權(quán)衡問(wèn)題。

1 問(wèn)題描述與符號(hào)假設(shè)

1.1 問(wèn)題描述

本文研究的易腐品物流配送系統(tǒng)由一個(gè)供應(yīng)商和N個(gè)零售商構(gòu)成，供應(yīng)商向零售商提供一種腐敗率固定的易腐品，并定期為其補(bǔ)貨。每個(gè)零售商擁有相互獨(dú)立且固定的產(chǎn)品需求率。零售商允許缺貨，所缺貨物供應(yīng)商會(huì)在下一個(gè)配送周期補(bǔ)齊。供應(yīng)商送貨的車(chē)輛同質(zhì)且數(shù)目足夠多，車(chē)輛具有最大載重約束。為了更加貼近物流管理實(shí)踐，允許車(chē)輛在執(zhí)行配送任務(wù)的過(guò)程中進(jìn)行重復(fù)裝貨，每輛車(chē)在配送過(guò)程中行駛多個(gè)回路，負(fù)責(zé)一個(gè)區(qū)域的零售商的補(bǔ)貨服務(wù)，最終每個(gè)零售商有且僅有一輛車(chē)為其服務(wù)。由于車(chē)輛行駛速度及最大載重量的約束，每個(gè)區(qū)域的配送周期以及每條回路的不缺貨時(shí)間都有上下限。在無(wú)限計(jì)劃期內(nèi)，供應(yīng)商在滿足車(chē)容等約束的條件下，制定使得車(chē)輛固定成本、行駛費(fèi)用、裝卸費(fèi)用、庫(kù)存成本、腐敗成本和缺貨成本之和最小的合理的配送方案，確定對(duì)零售商的補(bǔ)貨周期、補(bǔ)貨量、零售商的不缺貨時(shí)間以及車(chē)輛的行駛路徑。

1.2 基本假設(shè)條件

(1)易腐品在零售商處由于銷(xiāo)售條件的限制而存在常數(shù)腐敗率，運(yùn)輸途中不發(fā)生腐?。ú捎美滏溑渌停?；

(2)配送過(guò)程中，貨物裝卸時(shí)間相對(duì)于運(yùn)輸時(shí)間和配送周期足夠小，可以忽略不計(jì)；

(3)零售商無(wú)庫(kù)存容量限制；

(4)一個(gè)周期中，每個(gè)零售商只接受一次補(bǔ)貨服務(wù)。

1.3 符號(hào)表示

s：配送中心；S：零售商集合，S={1,2,…,i,…,N}；S+：配送中心及零售商集合，S+=S?{s}；V：車(chē)輛集合，V={1,…,v,…}；Sv：車(chē)輛v服務(wù)的零售商集合；M：車(chē)輛v所行駛的路徑集合，M={1,…,m,…}；：車(chē)輛v第m次裝貨所服務(wù)的零售商集合；：車(chē)輛v第m次裝貨的裝貨量；σ：車(chē)輛行駛速度；ψ：車(chē)輛最大載重量；di：零售商i的產(chǎn)品需求率；φ：?jiǎn)未窝b卸費(fèi)用；κ：?jiǎn)挝粫r(shí)間車(chē)輛固定成本；δ：車(chē)輛單位路程行駛費(fèi)用；θ：易腐品常數(shù)腐敗率；p：?jiǎn)挝划a(chǎn)品腐敗成本；h：零售商單位產(chǎn)品單位時(shí)間庫(kù)存成本；b：?jiǎn)挝蝗必洺杀荆籺ij：車(chē)輛從零售商i到零售商j的行駛時(shí)間；Tv：車(chē)輛v的配送周期；：車(chē)輛v行駛的第m個(gè)回路的周期，：配送周期Tv的取值上限和下限；：車(chē)輛v所行駛的第m個(gè)回路的周期上下限；ti：零售商i的不缺貨時(shí)間：車(chē)輛v所行駛的第m個(gè)回路的不缺貨時(shí)間；Ii(t)：零售商i在t時(shí)刻的庫(kù)存水平；Qi0：零售商i的期初庫(kù)存水平；QiT：零售商i期末的缺貨量；Qi：零售商i每周期的送貨量；ICi,DCi,SCi：零售商i一個(gè)周期內(nèi)的庫(kù)存成本、腐敗成本和缺貨成本；ICv,DCv,SCv：車(chē)輛v所負(fù)責(zé)的補(bǔ)貨服務(wù)單周期總庫(kù)存成本、總腐敗成本和總?cè)必洺杀?；TCv：車(chē)輛v所負(fù)責(zé)的補(bǔ)貨服務(wù)單位時(shí)間總成本。

2 模型構(gòu)建

若車(chē)輛v負(fù)責(zé)某一區(qū)域零售商的補(bǔ)貨服務(wù)，則該區(qū)域內(nèi)所有的零售商的訂貨周期都相同，即為車(chē)輛v的配送周期Tv。該區(qū)域內(nèi)的零售商i在周期Tv內(nèi)，當(dāng)0≤t≤ti時(shí)，庫(kù)存水平為[12]：

由于在一條回路上零售商有相同的配送周期，因此在計(jì)算不缺貨時(shí)間時(shí)，為了簡(jiǎn)化計(jì)算，本文采用了“按需求率等比例缺貨原則”，即每個(gè)零售商的不缺貨時(shí)間相同。

車(chē)輛v所服務(wù)的零售商集合Sv對(duì)應(yīng)的單位時(shí)間庫(kù)存成本可表示為：

單位時(shí)間腐敗成本為：

單位時(shí)間缺貨成本為：

車(chē)輛v所負(fù)責(zé)的配送任務(wù)單位時(shí)間總成本=單位時(shí)間車(chē)輛固定成本+單位時(shí)間行駛費(fèi)用+單位時(shí)間裝卸費(fèi)用+單位時(shí)間庫(kù)存成本+單位時(shí)間腐敗成本+單位時(shí)間缺貨成本，可表示為：

由表達(dá)式(1)可知，當(dāng)車(chē)輛v的行駛路徑確定后，單位時(shí)間總成本TCv與周期Tv以及各回路的不缺貨時(shí)間tvm有關(guān)。

證明過(guò)程略。

由于有多個(gè)車(chē)輛負(fù)責(zé)零售商的補(bǔ)貨服務(wù)，系統(tǒng)總成本是由所有配送任務(wù)總成本之和構(gòu)成的，為了得到單位時(shí)間系統(tǒng)總成本的表達(dá)式，本文又設(shè)置了如下變量：

：0-1變量，當(dāng)車(chē)輛v從i行駛到j(luò)時(shí)否則變量，車(chē)輛v負(fù)責(zé)某一區(qū)域的零售商的補(bǔ)貨服務(wù)時(shí)，yv=1，否則連續(xù)變量，車(chē)輛v第m次裝貨，從零售商i行駛到j(luò)的途中，該回路中還沒(méi)有完成補(bǔ)貨的零售商的補(bǔ)貨量之和。

單位時(shí)間系統(tǒng)總成本的目標(biāo)函數(shù)及約束條件如下：

上述模型是一個(gè)非線性規(guī)劃模型。目標(biāo)函數(shù)(2)表示無(wú)限計(jì)劃期內(nèi)，系統(tǒng)單位時(shí)間總成本；約束式(3)保證單周期內(nèi)每個(gè)零售商有且只有一次補(bǔ)貨服務(wù)；約束式(4)保證車(chē)輛v在行駛到一個(gè)零售商后，一定能離開(kāi)此零售商，繼續(xù)補(bǔ)貨服務(wù)；約束式(6)表示對(duì)于任意的回路，不缺貨時(shí)間不能大于配送周期；約束式(7)保證車(chē)輛v在駛?cè)肱c離開(kāi)零售商j時(shí)裝載貨物量之差等于零售商j要求的補(bǔ)貨量；約束式(8)保證車(chē)輛v只有在執(zhí)行配送任務(wù)時(shí)才能離開(kāi)供應(yīng)商；約束式(10)保證只有當(dāng)車(chē)輛v從i行駛到j(luò)時(shí)，zmvij才不為零；約束式(11)是決策變量的取值范圍。

3 求解算法

由上述模型可知，該問(wèn)題目標(biāo)函數(shù)復(fù)雜，且約束條件中包含非線性約束，求解過(guò)程中需要確定車(chē)輛行駛路徑，即需要確定TSP回路，而TSP問(wèn)題是運(yùn)籌學(xué)中經(jīng)典的NP-Complete問(wèn)題，故該問(wèn)題也是一個(gè)NP-Complete問(wèn)題。因此，本節(jié)采用改進(jìn)的節(jié)約算法這一啟發(fā)式算法求解配送路徑，并設(shè)計(jì)算法求解每條路徑的周期和不缺貨時(shí)間，進(jìn)而求得每個(gè)配送任務(wù)的總成本。節(jié)約算法由Clarke和Wright提出并證明了其有效性，近年來(lái)被廣泛的應(yīng)用于求解車(chē)輛路徑及其相關(guān)問(wèn)題。與傳統(tǒng)的節(jié)約算法不同的是，改進(jìn)的節(jié)約算法除了滿足車(chē)容量約束外，還要滿足周期上下限的時(shí)間約束以及不缺貨時(shí)間的約束，合并時(shí)并非以路徑距離的減少值為節(jié)約值直接將兩條回路合并，而是以配送任務(wù)總成本的減少值為節(jié)約值，先對(duì)車(chē)輛配送任務(wù)進(jìn)行合并，再對(duì)每輛車(chē)所行駛的多個(gè)回路進(jìn)行路徑合并，改進(jìn)的節(jié)約算法求解思路見(jiàn)算法1。由于路徑確定后，成本函數(shù)與多個(gè)變量相關(guān)，故根據(jù)函數(shù)特點(diǎn)設(shè)計(jì)了算法求解配送周期和每條路徑的不缺貨時(shí)間，求解思路見(jiàn)算法2。

算法1：改進(jìn)的節(jié)約算法求解路徑

(1)初始化配送任務(wù)，每輛車(chē)負(fù)責(zé)一個(gè)零售商的配送，形成初始配送任務(wù)列表。

(2)兩輛車(chē)的配送任務(wù)的合并。

①一輛車(chē)負(fù)責(zé)的配送任務(wù)包含n個(gè)回路，總成本為C1，另一輛車(chē)負(fù)責(zé)的配送任務(wù)包含m個(gè)回路，總成本為C2。將這兩輛車(chē)所負(fù)責(zé)的配送任務(wù)合并，即合并后的配送任務(wù)包含n+m個(gè)回路（若此配送任務(wù)不可行，則放棄）。

②將①所得配送任務(wù)的n+m個(gè)回路視為一個(gè)回路列表，并對(duì)其進(jìn)行路徑調(diào)整。

a.用最近插入法[14]將回路列表中兩條回路進(jìn)行合并（若此合并不可行，則放棄），并記錄其節(jié)約值（調(diào)用算法2）。

b.重復(fù)a，將所有可行的合并列出，并計(jì)算其成本節(jié)約值（調(diào)用算法2）。

c.記錄b中節(jié)約值最大的合并。刷新回路列表，將由此合并得到的路徑加入回路列表，并從回路列表中刪除被合并的兩條回路。轉(zhuǎn)a，直到?jīng)]有可行的回路合并為止，得到調(diào)整后的配送任務(wù)。

③記算②所得調(diào)整后的配送任務(wù)的總成本（調(diào)用算法2），并計(jì)算其合并節(jié)約值。

(3)重復(fù)(2)，將所有可行的配送任務(wù)合并列出，并計(jì)算其成本節(jié)約值（調(diào)用算法2）。

(4)記錄(3)中節(jié)約值最大的合并。刷新配送任務(wù)列表，將由此合并所得的配送任務(wù)加入配送任務(wù)列表，并從配送任務(wù)列表中刪除被合并的兩個(gè)配送任務(wù)。轉(zhuǎn)(2)，直到?jīng)]有可行的配送任務(wù)合并為止，得到合并后的配送任務(wù)組合。

算法2：求解車(chē)輛v所負(fù)責(zé)的配送任務(wù)的周期、各回路的不缺貨時(shí)間及總成本

(2)判斷Tv?是否超界，并對(duì)Tv取值（若超界則取邊界，若不超界則取最優(yōu)周期），由約束式(9)求得在此Tv條件下每條回路的不缺貨時(shí)間上界，并判斷是否超界。

(3)若所有的都不超界，則將Tv和代入成本函數(shù)式(1)即得此配送任務(wù)的成本。針對(duì)每個(gè)超界的，依次將不缺貨時(shí)間取為邊界值，并帶入成本函數(shù)式(1)，并重新求解新的周期、其他回路的不缺貨時(shí)間和此時(shí)的成本函數(shù)值（由式(1)確定，周期和不缺貨時(shí)間超界則取邊界）。

(4)返回(3)所得的配送任務(wù)成本的最小值，以及得出此最小成本的周期和各回路的不缺貨時(shí)間。

根據(jù)命題1，各個(gè)不缺貨時(shí)間的最優(yōu)解雖然相同，但是由于約束式(9)，不同回路的不缺貨時(shí)間邊界值可能不同，實(shí)際上根據(jù)算法2求得的各不缺貨時(shí)間是可以不同的。

上述算法在Visual C++6.0平臺(tái)上進(jìn)行程序編寫(xiě)和運(yùn)行，運(yùn)行環(huán)境為：CPU—Inter?Core?2 Duo,2.0GHz,內(nèi)存—2G，操作系統(tǒng)—Windows XP。

4 算例分析

基礎(chǔ)數(shù)據(jù)來(lái)源于文獻(xiàn)[9]，有1個(gè)供應(yīng)商給15個(gè)零售商配送一種腐敗率固定的易腐品，相關(guān)基本參數(shù)為：車(chē)輛行駛速度σ=50千米/小時(shí)；車(chē)輛最大載重ψ=100噸；車(chē)輛單位時(shí)間固定成本κ=50元/小時(shí)；車(chē)輛單位路程行駛費(fèi)用δ=1元/千米；零售商單位產(chǎn)品單位時(shí)間庫(kù)存成本h=0.1元/小時(shí)*噸；單位缺貨成本b=1元/小時(shí)*噸；單次裝卸費(fèi)用φ=50元；產(chǎn)品腐敗率θ=0.03；單位產(chǎn)品腐敗成本p=100元/噸；15個(gè)零售商的需求率分別為{0.109;0.326;0.322;0.478;0.134;0.429;0.381;0.503;0.187;0.123;0.953;0.638;0.247;0.188;0.441}。零售商及配送中心位置和距離矩陣見(jiàn)參考文獻(xiàn)[9]。

求解結(jié)果為:供應(yīng)商需要2輛車(chē)為零售商送貨，第一輛車(chē)不重復(fù)裝貨，行駛路徑為0-7-8-4-12-11-0，配送周期為33.86小時(shí)，路徑不缺貨時(shí)間為0.51小時(shí)，配送任務(wù)單位時(shí)間總成本為140.18元；第二輛車(chē)重復(fù)裝貨，行駛2條回路，路徑為0-13-15-1-0-10-14-3-5-6-2-9-0，配送周期為55.31小時(shí)，第一條回路的不缺貨時(shí)間為11.73小時(shí)，第二條回路的不缺貨時(shí)間為11.73小時(shí)，配送任務(wù)單位時(shí)間總成本159.25元。單位時(shí)間系統(tǒng)總成本為299.43元。車(chē)輛行駛路徑網(wǎng)絡(luò)圖1。

圖1 車(chē)輛行駛路徑網(wǎng)絡(luò)圖

當(dāng)零售商處不允許缺貨時(shí)，配送策略為：供應(yīng)商共需要3輛車(chē)為零售商補(bǔ)貨，第一輛車(chē)不重復(fù)裝貨，路徑為0-15-1-14-10-0，配送周期為50.02小時(shí)，任務(wù)單位時(shí)間總成本為95.76元；第二輛車(chē)也不重復(fù)裝貨，路徑為0-9-3-5-6-2-0，配送周期為38.2小時(shí)，任務(wù)單位時(shí)間總成本為114.16元；第三輛車(chē)重復(fù)裝貨，行駛2條回路，路徑為0-7-8-4-0-13-12-11-0，配送周期為32.26小時(shí)，任務(wù)單位時(shí)間總成本為138.18元。單位時(shí)間系統(tǒng)總成本為348.1元。

以上測(cè)試結(jié)果表明，缺貨策略會(huì)使系統(tǒng)總成本減小。這是由于在缺貨狀態(tài)下，不會(huì)發(fā)生產(chǎn)品腐敗，客戶需求量一定時(shí)，系統(tǒng)貨運(yùn)總量降低，對(duì)供應(yīng)商的運(yùn)輸能力要求降低，因此供應(yīng)商所需車(chē)輛數(shù)目減少，車(chē)輛固定成本減少，產(chǎn)品庫(kù)存成本和腐敗成本也減少。這兩組測(cè)試說(shuō)明，在不影響顧客需求的前提下，適當(dāng)缺貨會(huì)使供應(yīng)鏈總成本降低，提高供應(yīng)鏈整體效益。

5 結(jié)論

本文在現(xiàn)有易腐品允許缺貨的庫(kù)存問(wèn)題和IRP問(wèn)題研究的基礎(chǔ)上，綜合考慮易腐品供應(yīng)鏈上的配送成本、庫(kù)存成本、腐敗成本和缺貨成本，研究了兩級(jí)供應(yīng)鏈允許缺貨的易腐品IRP問(wèn)題，同時(shí)決策零售商的庫(kù)存策略和配送策略。通過(guò)建立合理的數(shù)學(xué)模型，證明了當(dāng)某一配送任務(wù)的路徑確定后總成本與配送周期及各路徑的不缺貨時(shí)間等多個(gè)變量相關(guān)，且各路徑在不考慮約束時(shí)的最優(yōu)不缺貨時(shí)間都相等。證明了成本函數(shù)的性質(zhì)，在解析分析的基礎(chǔ)上，以改進(jìn)的節(jié)約算法得到配送路徑，結(jié)合變量的邊界條件，設(shè)計(jì)算法求解配送周期和各路徑的不缺貨時(shí)間。以算例驗(yàn)證問(wèn)題和算法的有效性，測(cè)試結(jié)果分析表明，允許零售商部分缺貨，會(huì)明顯提高供應(yīng)鏈的整體利益。

本文的模型只考慮了零售商處的腐敗及缺貨，并沒(méi)有考慮供應(yīng)商處的生產(chǎn)及腐敗問(wèn)題，然而在現(xiàn)實(shí)中，若供應(yīng)商對(duì)產(chǎn)品進(jìn)行相應(yīng)的處理、包裝，則會(huì)改變產(chǎn)品的腐敗率及配送方式，進(jìn)而改變供應(yīng)鏈的總成本。如何在考慮供應(yīng)商生產(chǎn)的條件下，綜合權(quán)衡配送成本、庫(kù)存成本、腐敗成本和缺貨成本，決策最優(yōu)的配送方式和運(yùn)輸路徑，將是筆者進(jìn)一步研究的方向。

[1]Yang H L.Two-warehouse Inventory Models for Deteriorating Items with Shortages under Inflation[J].European Journal of Operational Research,2004,（157）.

[2]Rong M,Mahapatra N K,Maiti M.A Two Warehouse Inventory Model for a Deteriorating Item with Partially/Fully Backlogged Shortage and Fuzzy Lead Time[J].European Journal of Operational Research,2008,（189）.

[3]Hou K L.An Inventory Model for Deteriorating Items with Stock-Dependent Consumption Rate and Shortages under Inflation and Time Discounting[J].European Journal of Operational Research,2006,（168）.

[4]Lo S T,Wee H M,Huang W C.An Integrated Production-Inventory Model with Imperfect Production Processes and Weibull Distribution Deterioration under Inflation[J].International Journal of Production Economics,2007,（106）.

[5]Federgruen A,Zipkin P.A Combined Vehicle-routing and Inventory Allocation Problem[J].Operations Research,1984,(32).

[6]Anily S,Federgruen A.One Warehouse Multiple Retailer Systems with Vihicle Routing Costs[J].Management Science,1990,(36).

[7]Viswanathan S,Mathur K.Integrating Routing and Inventory Decisions in One-Warehouse Multiretailer Multiproduct Distribution Systems[J].Management Science,1997,(43).

[8]Qu W W,Bookinder J H,Iyogun P.An Integrated Inventory-Transportation System with Modified Periodic Policy for Multiple Products[J].European Journal of Operational Research,1999,（115）.

[9]Aghezzaf E,Raa B,Landeghem H.Modeling Inventory Problems in Supply Chains of High Consumpution Products[J].European Journal of Operational Research,2006,（169）.

[10]Abdelmaguid T F,Dessouky M M,Ordonez F.Heuristic Approaches for The Inventory-routing Problem with Backlogging[J].Computers&Industrial Engineering,2009,（56）.

[11]Hemmelmayr V,Doerner K F,Hartl R F,et al.Delivery Strategies for Blood Products Supplies[J].Operations Research,2009,（31）.

[12]Ouyang L Y,Teng J T,Goyal S K,Yang C T.An Economic Order Quantity Model for Deteriorating Items with Partially Permissible Delay in Payments Linked to Order Quantity[J].European Journal of Operational Research,2009,194(2).

[13]Clarke G,Wright J W.Scheduling of Vehicles from a Central Depot to a Number of Delivery Points[J].Operations Research,1964,(12).

[14]盧開(kāi)澄.圖論及其應(yīng)用[M].北京：清華大學(xué)出版社，1981.