李珍萍， 焦鵬博

(北京物資學(xué)院信息學(xué)院， 北京 101149)

隨著企業(yè)競爭的加劇，以客戶為中心的物流管理面臨更為復(fù)雜的競爭環(huán)境，市場供求關(guān)系也已經(jīng)由賣方市場轉(zhuǎn)變?yōu)橘I方市場[1]。在這種情況下，供應(yīng)商管理庫存 (vendor managed inventory, VMI) 受到了社會各界廣泛的關(guān)注與推崇。在VMI模式下，零售商將自己的庫存決策權(quán)轉(zhuǎn)移給上游供應(yīng)商，其本身只負責為供應(yīng)商提供透明的市場信息，由于供應(yīng)商得到的需求信息更加真實準確，因而能夠制定更加合理的產(chǎn)品配送決策[2]。一個合理的配送決策，不僅可以大大提高物流運輸效率，還能夠有效降低企業(yè)對運輸資源的消耗[3-6]，對物流配送企業(yè)有著重要的指導(dǎo)意義。

關(guān)于VMI模式的應(yīng)用與車輛路徑優(yōu)化問題，已有眾多學(xué)者開展了廣泛且深入的研究。在VMI模式的應(yīng)用方面，大多數(shù)學(xué)者更加注重對生產(chǎn)及庫存管理[7-9]、供應(yīng)鏈協(xié)調(diào)[10-13]、風險規(guī)避[14-15]等問題的決策，很少同時考慮配送路徑優(yōu)化問題。而針對車輛路徑優(yōu)化問題的研究成果則主要集中在客戶需求已知情況下單純的最優(yōu)路徑求解方面[3,16-19]，即在客戶管理庫存模式(customer managed inventory, CMI)下，由客戶下達固定補貨需求訂單，由供應(yīng)商決策最佳配送路徑。實際中，VMI模式下，供應(yīng)商不僅要確定為每個客戶補貨的商品數(shù)量，而且要規(guī)劃配送路徑，因此應(yīng)該將為客戶配送商品的數(shù)量和配送路徑優(yōu)化問題結(jié)合在一起開展研究?，F(xiàn)針對VMI模式下的配送路徑優(yōu)化問題開展研究，在供應(yīng)商可實時獲得客戶庫存水平和產(chǎn)品消耗率等信息的基礎(chǔ)上，考慮客戶的服務(wù)時間窗等因素，確定為每個客戶配送的商品數(shù)量和最優(yōu)的配送路徑方案。

1 問題描述

VMI模式下產(chǎn)品配送網(wǎng)絡(luò)如圖1所示，VMI模式下配送路徑優(yōu)化問題定義在一個完全有向圖G上，G=(N,A)，節(jié)點集合N={0,1,…,n,n+1}，弧集合A={(i,j)|?i,j∈N,i≠j}。其中，0和n+1表示同一個供應(yīng)商，供應(yīng)商既是配送過程的開始節(jié)點也是結(jié)束節(jié)點，中間節(jié)點為需要服務(wù)的客戶點，對于任意一個節(jié)點，已知節(jié)點位置、服務(wù)時間窗與服務(wù)持續(xù)時間，配送車輛從供應(yīng)商出發(fā)依次服務(wù)多個客戶點，最后返回供應(yīng)商處。

圖1 物流配送路徑示意圖Fig.1 Logistics distribution route schematic map

假設(shè)配送開始前所有客戶的產(chǎn)品儲量為100%，在配送開始時消耗產(chǎn)品，當配送車輛開始為其服務(wù)時，停止消耗產(chǎn)品且在服務(wù)持續(xù)時間內(nèi)完成補貨，補貨量等于車輛開始提供服務(wù)之前的產(chǎn)品消耗量，即補貨之后產(chǎn)品儲量恢復(fù)100%。在VMI模式下，已知所有客戶的單位時間產(chǎn)品消耗量(記為消耗率)和庫存水平，假設(shè)供應(yīng)商采取最大補貨量策略，即根據(jù)車輛開始提供服務(wù)之前各個客戶點消耗的產(chǎn)品數(shù)量確定補貨量(需求量)，從而將庫存水平恢復(fù)到100%。

在以上假設(shè)下，各個客戶點的補貨量(需求量)、開始服務(wù)時間與消耗率之間的關(guān)系為

需求量=消耗率×開始服務(wù)時間

(1)

在滿足客戶補貨量要求以及服務(wù)時間窗限制的前提下，為了最小化總配送成本，供應(yīng)商應(yīng)該如何制定配送路徑規(guī)劃方案？為簡化問題，做出以下假設(shè)。

(1)每個客戶只被一輛車服務(wù)且只服務(wù)一次。

(2)每條路徑上客戶的需求量之和不超過車容量。

(3)不考慮車輛的固定使用費用，將其他成本作為單位距離配送成本。

(4)車輛可以提前到達客戶點，但需要等待至客戶最早時間窗時才能提供服務(wù)，不考慮等待費用。

(5)每個客戶的產(chǎn)品消耗率為已知常量，所有客戶的產(chǎn)品消耗率相同。

2 數(shù)學(xué)模型

2.1 變量符號

(1)定義集合：B為供應(yīng)商集合即開始節(jié)點和結(jié)束節(jié)點集合，本文研究中只有一個供應(yīng)商，B={0,n+1}；N*為待服務(wù)的客戶集合,N*={1,…,n}；N為所有節(jié)點集合，N=B∪N*，i,j∈N為客戶索引；K為車輛集合，k∈K為車輛索引。

(2)定義參數(shù)：cij為弧(i,j)之間的單位距離配送成本，i∈N,j∈N；dij為弧(i,j)之間的歐式距離，i∈N,j∈N；tij為車輛通過弧(i,j)的行駛時間，i∈N,j∈N；oi為任意車輛在客戶節(jié)點i的服務(wù)持續(xù)時間，i∈N*；[ei,li]為客戶節(jié)點i的服務(wù)時間窗，i∈N*；Qk為車輛k的容量，k∈K；v為產(chǎn)品消耗率；M為一個足夠大的正數(shù)。

(3)定義決策變量：sik為車輛k在客戶節(jié)點i開始服務(wù)的時間，i∈N*,k∈K，取值范圍[0,S]；S為最晚開始服務(wù)時間；qi為客戶節(jié)點i的補貨量，i∈N*，取值范圍[vei,vli]。

(2)

2.2 數(shù)學(xué)模型

基于VMI模式的配送路徑優(yōu)化問題可以表示成如下混合整數(shù)規(guī)劃模型：

(3)

(4)

(5)

(6)

qi=vsik, ?i∈N*,k∈K

(7)

ei≤sik≤li, ?i∈N*,k∈K

(8)

(9)

(10)

sik+oi+tijk-M(1-xijk)≤sjk,

?i,j∈N，i≠j,k∈K

(11)

xijk∈{0,1}, ?i,j∈N,i≠j,k∈K

(12)

0≤sik≤S, ?i∈N*，k∈K

(13)

vei≤qi≤vli, ?i∈N*

(14)

目標函數(shù)式(3)表示最小化總配送成本，即單位距離配送成本與總配送距離乘積；約束條件式(4)表示每輛車必須從供應(yīng)商出發(fā)；約束條件式(5)表示每輛車完成配送任務(wù)后必須回到供應(yīng)商處；約束條件式(6)表示每輛車給客戶的補貨量不能超過車輛容量；約束條件式(7)表示需求量、開始服務(wù)時間與消耗率之間的關(guān)系即式(1)；約束條件式(8)表示每輛車開始服務(wù)客戶的時間在客戶的時間窗范圍內(nèi)；約束條件式(9)表示流平衡約束即某輛車從某個客戶點進入則必須從該客戶點離開；約束條件式(10)表示每個客戶點能且僅能被訪問一次；約束條件式(11)表示某輛車開始服務(wù)某客戶的時間一定大于等于車輛開始服務(wù)前一個客戶的時間加上服務(wù)持續(xù)時間和行駛時間；約束條件式(12)、條件式(13)和條件式(14)為決策變量取值約束，約束條件式(13)表示開始服務(wù)時間只能為正值且不能超過最晚開始服務(wù)時間；約束條件式(14)表示每個客戶點的補貨量限制。

根據(jù)上述混合整數(shù)規(guī)劃模型，不僅可以求出為每個客戶配送的商品數(shù)量，而且可以同時確定出配送路徑方案。

3 模擬計算與分析

利用Solomon[20]數(shù)據(jù)庫中的隨機分布R101的基礎(chǔ)數(shù)據(jù)，生成測試算例，給出1個供應(yīng)商(編號為0)和前20個客戶點(編號為1～20)，各個節(jié)點的橫坐標(X)、縱坐標(Y)、最早時間窗(ET)、最晚時間窗(LT)、服務(wù)持續(xù)時間(DT)如表1所示。

表1 配送中心和客戶點信息Table 1 Information of deport and customers

為生成符合要求的算例，補充如下數(shù)據(jù)：供應(yīng)商共擁有12輛車，即K=12；所有車輛為同一類型且車容量為2 000 kg，即Qk=2 000；車輛的單位配送成本為10元/km，即cij=10；車輛固定速度為60 km/h，即1 km/min，則車輛的行駛時間可表示為兩節(jié)點之間的歐式距離tij=dij；每輛車在時刻0出發(fā)，最晚開始服務(wù)時間為300 min，即S=300；設(shè)置M=10 000；設(shè)置產(chǎn)品消耗率為4 kg/min，即v=4。

首先計算經(jīng)典的客戶管理庫存模式(CMI)下的配送方案，在CMI模式下，由于客戶提交補貨訂單時無法預(yù)知車輛的開始服務(wù)時間，為防止缺貨，客戶通常會以時間窗中的最晚時間即l作為車輛的開始服務(wù)時間計算補貨量并下達訂單，補貨量q為

q=vl

(15)

根據(jù)以上參數(shù)設(shè)置，利用Python編程并調(diào)用商業(yè)求解器Gurobi，在1.60 GHz Intel Core i5處理器上，求解基于CMI模式的混合整數(shù)規(guī)劃模型，在3.04 s的時間內(nèi)得到最優(yōu)配送路徑、補貨量、車輛行駛里程等數(shù)據(jù)如表2所示。

表2 CMI模式下的配送路徑方案Table 2 Routes scheme under CMI mode

由表2可知，在CMI模式下的最優(yōu)配送路徑方案中，供應(yīng)商需要使用5輛配送車輛，分為5條路徑在客戶要求的時間內(nèi)完成配送任務(wù)，總配送成本為4 613.89元(車輛行駛里程461.389 km)。若要滿足所有客戶訂單中的補貨量要求，供應(yīng)商的產(chǎn)品庫存水平應(yīng)為8 436 kg。每條路徑的服務(wù)節(jié)點、補貨量、消耗量、車輛行駛里程等信息均可從表2得出。

在同樣的處理器上，利用求解器對基于VMI模式的混合整數(shù)規(guī)劃模型進行求解，在5.11 s的時間內(nèi)得到最優(yōu)配送路徑、補貨量、車輛行駛里程等數(shù)據(jù)如表3所示。

表3 VMI模式下的配送路徑方案Table 3 Routes scheme under VMI mode

由表3可知，供應(yīng)商同樣需要安排5輛車完成所有配送任務(wù)，此方案的總配送成本為4 492.42元(車輛行駛里程449.242 km)。若采用最大補貨量策略，將所有客戶庫存水平恢復(fù)至100%，則供應(yīng)商產(chǎn)品庫存水平應(yīng)為6 822.84 kg。每條路徑服務(wù)節(jié)點、開始服務(wù)時間等數(shù)據(jù)均可從表3得出。

對比CMI和VMI兩種庫存模式下的配送路徑方案可以發(fā)現(xiàn)，兩種方案均需5輛車完成所有配送任務(wù)。在總成本節(jié)約方面，VMI模式下的路徑方案減少了車輛總行駛里程12.147 km，總成本降低了121.47元；在庫存水平合理化方面，VMI模式下的路徑方案可以幫助供應(yīng)商減少庫存1 613.16 kg，有效降低了供應(yīng)商的庫存水平以及庫存持有成本；在車輛的利用率方面，CMI模式下車輛的無效裝載量(補貨量-消耗量)為794.08 kg，而VMI模式下車輛的無效裝載量為0，即VMI模式減少了車輛的無效裝載量和運力浪費情況，提高了車輛的有效利用率。以上分析結(jié)果驗證了VMI模式的優(yōu)越性。

由于VMI模式下的配送路徑優(yōu)化問題屬于NP難問題(NP-hard problem)，因此對于中等規(guī)模算例(40個客戶點)，利用求解器直接求解基于VMI模式的混合整數(shù)規(guī)劃模型，無法在可接受的時間內(nèi)得到最優(yōu)解。本文設(shè)置求解時間為240 min時，得到一個可行的配送方案，配送路徑、補貨量等數(shù)據(jù)如表4所示。

表4 VMI模式下可行配送路徑方案Table 4 Feasible routes scheme under VMI mode

由表4可知，對于40個客戶點的中等規(guī)模算例，供應(yīng)商至少需要安排8輛車完成所有配送任務(wù)，此方案的總配送成本為8 779.70元(車輛行駛里程877.970 km)。每條路徑的服務(wù)節(jié)點、補貨量、行駛里程等數(shù)據(jù)均可從表4中得出。

由以上分析可知，雖然在求解小規(guī)模配送路徑優(yōu)化問題時，求解器可在較短時間內(nèi)得到最優(yōu)解，但隨著問題規(guī)模的增加，對于中等規(guī)模的算例，求解器無法在可接受時間內(nèi)最優(yōu)解。因此，本文設(shè)計了滿足時間窗與補貨量約束且路徑最短的貪婪算法，依次安排配送車輛由近至遠服務(wù)客戶。結(jié)果表明，貪婪算法可在0.031 s的時間內(nèi)得到一個可行的路徑規(guī)劃方案。采用貪婪算法得到的路徑、路徑經(jīng)過節(jié)點、開始服務(wù)時間、補貨量等數(shù)據(jù)如表5所示。

表5 貪婪算法路徑方案Table 5 Routes scheme under greedy algorithm

由表5數(shù)據(jù)，采用貪婪算法得到的路徑規(guī)劃方案中，供應(yīng)商需要安排12輛配送車輛才能在滿足所有約束的條件下完成配送任務(wù)。由貪婪算法所得結(jié)果可知，此路徑規(guī)劃方案的總配送成本為9 279.73元(車輛行駛里程927.973 km)，當前配送路徑方案總成本與求解器得到的可行方案總成本之間的差值為500.03元。每條路徑的服務(wù)節(jié)點、補貨量、行駛里程等數(shù)據(jù)均可從表5中得出。

對以上結(jié)果進行分析可以發(fā)現(xiàn)，對于20個客戶點的小規(guī)模算例，在兩種庫存模式下，求解器都能夠在較短時間內(nèi)得到最優(yōu)解；對于40個客戶點的中等規(guī)模算例，雖然求解器的可行路徑方案在成本節(jié)約方面的效果優(yōu)于本文研究的貪婪算法，但此方案的求解時間為4 h，在實際配送場景中是供應(yīng)商無法接受的，而本文研究的貪婪算法可以在極短時間內(nèi)得到近似最優(yōu)解，為供應(yīng)商提供可接受的配送路徑方案。

4 結(jié)論

針對VMI模式下的配送路徑優(yōu)化問題進行了研究，考慮客戶的產(chǎn)品消耗率和服務(wù)時間窗等因素，以總配送成本極小化為目標建立了混合整數(shù)規(guī)劃模型，通過對比VMI和CMI兩種庫存模式下小規(guī)模算例的計算結(jié)果，驗證了VMI模式下的模型有效性，VMI模式可為供應(yīng)商和客戶節(jié)約庫存降低庫存持有成本。對于VMI模式下的中等規(guī)模算例，利用求解器和貪婪算法分別進行求解，通過對比可知，求解器在可接受時間內(nèi)無法得到供應(yīng)商的滿意解，而本文設(shè)計的貪婪算法在較短時間內(nèi)得到滿意的路徑規(guī)劃方案。因此所構(gòu)建的模型與算法可以作為企業(yè)管理庫存和規(guī)劃配送路徑的理論依據(jù)和方法支持。

在研究VMI模式下的配送路徑優(yōu)化問題時，只考慮了單車型配送的情況，假設(shè)每輛車的容量均相同，實際中，供應(yīng)商可能擁有多種類型車輛，每種類型車輛的容量不同，此時問題將變得更加復(fù)雜，也更加符合實際，后續(xù)研究將考慮多類型的配送車輛，得到更加經(jīng)濟合理的配送方案。另外，本研究設(shè)計的貪婪算法求解效果可能難以滿足大規(guī)模算例的求解精度要求，因此在接下來的研究中需要設(shè)計更有效的啟發(fā)式算法，為供應(yīng)商提供更加合理的配送路徑方案。