允許訂單延后的易腐品庫存——路徑問題研究

劉 靜，賈 濤，吉 哲

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

0 引言

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

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

1 問題描述與符號假設(shè)

1.1 問題描述

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

1.2 基本假設(shè)條件

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

(2)配送過程中，貨物裝卸時間相對于運輸時間和配送周期足夠小，可以忽略不計；

(3)零售商無庫存容量限制；

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

1.3 符號表示

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

2 模型構(gòu)建

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

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

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

單位時間腐敗成本為：

單位時間缺貨成本為：

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

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

證明過程略。

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

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

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

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

3 求解算法

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4 算例分析

基礎(chǔ)數(shù)據(jù)來源于文獻[9]，有1個供應(yīng)商給15個零售商配送一種腐敗率固定的易腐品，相關(guān)基本參數(shù)為：車輛行駛速度σ=50千米/小時；車輛最大載重ψ=100噸；車輛單位時間固定成本κ=50元/小時；車輛單位路程行駛費用δ=1元/千米；零售商單位產(chǎn)品單位時間庫存成本h=0.1元/小時*噸；單位缺貨成本b=1元/小時*噸；單次裝卸費用φ=50元；產(chǎn)品腐敗率θ=0.03；單位產(chǎn)品腐敗成本p=100元/噸；15個零售商的需求率分別為{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}。零售商及配送中心位置和距離矩陣見參考文獻[9]。

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

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

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

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

5 結(jié)論

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

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

[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]盧開澄.圖論及其應(yīng)用[M].北京：清華大學(xué)出版社，1981.