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

劉 靜，賈 濤，吉 哲

（西安交通大學 管理學院，西安 710049）

0 引言

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

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

1 問題描述與符號假設

1.1 問題描述

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

1.2 基本假設條件

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

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

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

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

1.3 符號表示

s：配送中心；S：零售商集合，S={1,2,…,i,…,N}；S+：配送中心及零售商集合，S+=S?{s}；V：車輛集合，V={1,…,v,…}；Sv：車輛v服務的零售商集合；M：車輛v所行駛的路徑集合，M={1,…,m,…}；：車輛v第m次裝貨所服務的零售商集合；：車輛v第m次裝貨的裝貨量；σ：車輛行駛速度；ψ：車輛最大載重量；di：零售商i的產品需求率；φ：單次裝卸費用；κ：單位時間車輛固定成本；δ：車輛單位路程行駛費用；θ：易腐品常數腐敗率；p：單位產品腐敗成本；h：零售商單位產品單位時間庫存成本；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一個周期內的庫存成本、腐敗成本和缺貨成本；ICv,DCv,SCv：車輛v所負責的補貨服務單周期總庫存成本、總腐敗成本和總缺貨成本；TCv：車輛v所負責的補貨服務單位時間總成本。

2 模型構建

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

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

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

單位時間腐敗成本為：

單位時間缺貨成本為：

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

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

證明過程略。

由于有多個車輛負責零售商的補貨服務，系統總成本是由所有配送任務總成本之和構成的，為了得到單位時間系統總成本的表達式，本文又設置了如下變量：

：0-1變量，當車輛v從i行駛到j時否則變量，車輛v負責某一區域的零售商的補貨服務時，yv=1，否則連續變量，車輛v第m次裝貨，從零售商i行駛到j的途中，該回路中還沒有完成補貨的零售商的補貨量之和。

單位時間系統總成本的目標函數及約束條件如下：

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

3 求解算法

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

算法1：改進的節約算法求解路徑

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

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

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

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

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

b.重復a，將所有可行的合并列出，并計算其成本節約值（調用算法2）。

c.記錄b中節約值最大的合并。刷新回路列表，將由此合并得到的路徑加入回路列表，并從回路列表中刪除被合并的兩條回路。轉a，直到沒有可行的回路合并為止，得到調整后的配送任務。

③記算②所得調整后的配送任務的總成本（調用算法2），并計算其合并節約值。

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

(4)記錄(3)中節約值最大的合并。刷新配送任務列表，將由此合并所得的配送任務加入配送任務列表，并從配送任務列表中刪除被合并的兩個配送任務。轉(2)，直到沒有可行的配送任務合并為止，得到合并后的配送任務組合。

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

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

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

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

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

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

4 算例分析

基礎數據來源于文獻[9]，有1個供應商給15個零售商配送一種腐敗率固定的易腐品，相關基本參數為：車輛行駛速度σ=50千米/小時；車輛最大載重ψ=100噸；車輛單位時間固定成本κ=50元/小時；車輛單位路程行駛費用δ=1元/千米；零售商單位產品單位時間庫存成本h=0.1元/小時*噸；單位缺貨成本b=1元/小時*噸；單次裝卸費用φ=50元；產品腐敗率θ=0.03；單位產品腐敗成本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]。

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

圖1 車輛行駛路徑網絡圖

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

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

5 結論

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

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

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