久久精品国产69国产精品亚洲_日韩欧美亚洲一区_免费观看污网站_欧美在线一

倉儲中心是供應鏈的重要節點, 在物流管理中起著連接供應鏈上下游的作用, 因此倉儲中心的選址直接影響著其他物流決策, 有時候甚至決定著整個物流過程的效率和效益。對倉儲中心位置進行合理規劃是個傳統的物流問題, 國內外學者進行了廣泛的研究。文獻[1]和文獻[2]從定性的角度分析了影響倉儲中心選址的多種因素, 文獻[3]則從定量角度給出了線性規劃、動態規劃等9種基本形式的選址模型。結合具體情景, 文獻[4]和文獻[5]在考慮庫存及運輸配送的基礎上, 建立倉儲中心選址模型, 并驗證了其合理性。

然而以上研究都是基于市場需求一定的情景進行研究的, 而市場需求受眾多因素影響, 往往會發生變化[6,7]。根據需求的這種特性, 文獻[8]從隨機需求角度將倉儲中心選址問題建模為整數線性規劃模型并設計求解;文獻[9]則在單一中心靜態選址的基礎上研究了動態選址問題。但是這些文獻多是考慮自建倉儲中心, 雖然自建倉儲中心更能符合企業自身存儲物品的特性及要求, 但卻需要巨大的投資, 資金占用率高, 風險大[10]。而租賃倉儲中心無需固定投資, 降低了倉儲成本, 特別是其地點選擇具有彈性, 可以隨市場遷移, 降低了需求變動所帶來的風險[11]。因此, 對于規模小, 產品需求波動大的產品來說, 租用倉儲中心可以減少固定投資, 增加資金的流動性, 提高經營靈活性。本文正是從這個角度出發, 在需求波動的背景下, 研究了單一第三方倉儲中心的選擇問題。文章首先針對需求變化已知的情形給出了最優的倉儲中心選擇策略, 然后為需求變化不可預知的情形設計了在線選擇策略, 并從競爭分析的角度討論了策略的競爭性能。

本文所研究的問題描述如下:某公司需要把產品從不同的產地運往銷售地, 銷售地分散著n個需求點, 每個需求點的需求量隨時間而變化。同時在銷售地的不同區域分散著m個第三方倉儲中心, 公司根據不同時期的需求量變化情況, 動態地選擇倉儲中心, 而倉儲中心的更換需要固定的轉換成本, 如果限定每階段只選擇一個倉儲中心, 那么公司應如何動態地選擇倉儲中心使得經營成本盡量小?

針對該問題, 給出以下符號定義:

C:倉儲中心轉換成本;c:單位運輸成本;xi:第i個潛在需求點, i=1, 2, …, n;yj:第j個備選倉儲中心, j=1, 2, …, m;T:階段數, 同時也是決策期限;qit:需求點xi的需在第t階段的需求量, t=1, 2, …, T;dij=d (xi, yj) :需求點xi到倉儲中心yj的最短路程, 設為已知。

便于討論, 本文基于以下假設:

(1) 不同產地到不同倉儲中心的距離相同;

(2) 由于資金或其他限制, 每階段只選一個倉儲中心;

(3) 在同一時期內, 不同倉儲中心的單位庫存成本相同;

(4) 不同中心之間的轉換需要固定的轉換成本, 且忽略中心轉換所需的時間。

需要說明的是, 產地到銷售地的距離相對于不同倉儲中心間的距離大得多, 因此在選擇倉儲中心的決策中, 假設⑴認為不同產地到不同倉儲中心的距離相同, 可以不考慮產地到銷售地的距離影響。假設⑶說明同一時期的總庫存成本不會因為倉儲中心的不同而不同, 因此只需要考慮從倉儲中心到需求點的運輸成本, 精簡了論證過程。

現在考慮下面兩個問題:

P1:所有需求點在不同階段的需求情況已知時, 如何進行倉儲中心的選擇?

P2:在任何階段, 只知道該階段及以前階段各個需求點的需求情況, 如何進行倉儲中心的選擇?

P1問題是信息完全情形下的多階段動態決策, 屬于離線問題, 可以設計相應的動態算法進行求解;P2問題是P1問題對應的在線問題, 該問題的特點是任何時刻, 對以后階段的情況不可預知, 決策者要在只知道以前需求的情況下做出在線決策, 使得收益 (成本或者利潤) 與對應的P1問題的最優解之間的差距盡量小。針對P2問題, 文章采用在線策略與競爭分析的方法進行研究, 這種方法與以往解決此類問題的方法的最大區別在于:它在變化因素的每一個特例中都能給出一個方案, 使得這一方案所得到的解離最優方案給出的解總在一定的比例之內[12,13]。對于費用最小化問題P以及任何有限的輸入序列δ, 如果存在一個常數r, 使得在線策略G的費用CostG (δ) 與離線最優策略OPT的費用CostOPT (δ) 滿足

CostG (δ) ≤r·CostOPT (δ) (1)

則稱該在線策略G為r競爭策略, 或者該在線策略具有競爭比r, 如果某一個在線策略的競爭比滿足r*=lnf(r)G?則稱r*為該在線問題的最優競爭比[14]。

文章第三部分針對P1問題給出了線性時間的動態規劃算法, 論證了結論的最優性;第四部分針對P2問題給出了一種簡單貪婪策略, 并討論了該策略在一般情形和特殊情形下的競爭性能;第五部分分別用DPA算法和簡單貪婪策略對算例進行分析求解;第六部分對文章進行了總結及展望。

當所有需求點在不同階段的需求情況已知時, 本文給出了線性時間的動態規劃算法, 在給出算法之前, 首先討論最優解的有關性質。假設決策期包含T個階段, 如果不考慮轉換成本, 則在任意階段t, 選擇第j個備選倉儲中心的運輸成本為:

Cjt=n∑i=1cdijqit, j=1,2,?,m (2)

在已知Cjt的情況下, P1問題可以轉化為特殊的最短路問題, 該最短路問題具有以下三個特點: (1) 具有T個階段, 每階段均包含m個結點, 其中第t階段的第j個結點記為yjt, 對應于第t階段的備選倉儲中心yj; (2) 上一階段的任一結點都可以到達下一階段的所有結點, 其中只有一條弧長為0, 其它均為C, 在P1問題中的實際意義是, 如果前后兩相鄰階段的倉儲中心位置不變, 則弧長為0, 如果改變則弧長為C; (3) 第t階段的每個結點也有權重, 權重值為Cjt。

我們可以通過以下兩個輔助操作, 把該特殊最短路問題轉化為一般的分階段最短路問題: (1) 增加兩個虛擬結點:一個初始結點O和一個終止結點D, 同時連接結點O和第一階段的m個結點, 以及結點D和最后階段的m個結點, 令增加的虛擬結點和虛擬弧的權重均為0; (2) 把第t階段的結點yjt的權重變為0, 把結點yji所有入弧的權重都增加Cjt。則可以用圖1描述該特殊最短路問題, 其中最短路徑對應的結點就是最優的倉儲中心選擇序列。

因為該最短路問題具有 (Tm+2) 個結點, 所以直接利用Dijkstra算法對該最短路問題進行求解的時間復雜性為O ( (Tm) 2) 。為了尋找更加快捷的算法, 對問題的最優解結構進行分析:設Ctit為第t階段選擇中心yi時, 前t階段的最小總成本, 且定義Yit為實現Ctit時從第1階段到第t階段的倉儲中心序列, 則下面的引理是顯然的:

引理1 若最優策略在第t階段選擇了中心yi, 則第t階段以前的中心序列為Yit。

圖1 P1問題的最短路模型示意圖  下載原圖

結合前文對Cjt的定義, 有以下遞推關系:

Ctit=min{Ct-1i(t-1)+Cit,minj≠i{Ct-1j(t-1)+C+Cit}}, i=1,2,3,?,m (3)

根據引理1和關系式 (3) , 給出離線問題的動態規劃算法 (DPA) 如下:

Step 1 計算Cjt=n∑i=1cdijqit, j=1, 2, …, m;t=1, 2, …, T, 令C1j1=Cj1, j=1, 2, …, m, 得到向量X1= (C111, C121, …, C1m1) T。

Step 2 , For (t=2;t=T;t++) , 計算Ctit=min{Ct-1i(t-1)+Cit,minj≠i{Ct-1j(t-1)+C+Cit}},i=1,2,3,?,m, 若Ct-1i(t-1)+Cit≤minj≠i{Ct-1j(t-1)+C+Cit}, 則標記ji (t-1) =i, 否則標記ji(t-1)=j=argminj≠i{Ct-1j(t-1)+C+Cit}, 同時得到向量Xt= (Ct1t, Ct2t, …, Ctmt) T。

Step 3 令Csummin=min1≤j≤mCΤjΤ, 標記j*Τ=j=argminjCΤjΤ。

Step 4 標記j*T-1=jj*T (T-1) , 令T=T-1, 當T=1時結束, 否則返回Step 4, 并記錄Csummin以及序列 (j*1, j*2, …j*T) 。

其中序列 (j*1, j*2, …j*T) 對應的倉儲中心序列即為最優的選擇序列, 最優成本為Csummin。

關于算法時間復雜性的分析:Step 1需要計算 (Tm) 個值, 每個值需要n次加法運算, 所以Step 1的時間復雜性為O (Tm) ;Step 2共需循環T次, 每次循環需要確定m個值, 而每個值需要進行m次比較, 所以時間復雜性為O (Tm2logm) ;Step 3和Step 4的時間復雜性分別為O (1) 和O (T) , 所以總的時間復雜性為O (Tm2logm) , 如下面定理所示:

定理1 對于P1問題, 存在時間復雜性為O (Tm2logm) 的線性算法 (DPA) 。

從定理1可知, 當T>logm時, DPA算法的復雜性 (O (Tm2logm) ) 小于Dijkstra算法的復雜性 (O (Tm) 2) ) , 因此面對實際問題時, 可以先判斷是否滿足T>logm, 如果滿足則利用本文的DPA算法進行求解, 否則直接采用Dijkstra算法進行求解。

上一節給出了離線情形的最優解及算法, 而在實際商業活動中, 尤其是需求波動大的產品, 未來的需求情況往往難以預測, 因此在只知道當前階段及以前階段的需求情況時, 對倉儲中心的選擇做出在線決策就顯得更為重要。面臨不確定問題時, 人們對未來缺乏充足的認識, 通常追求“眼前利益”, 這正是貪婪策略產生的根源, 本節針對具有在線決策特點的P2問題給出一種簡單貪婪策略, 并分別在一般情形和特殊情形下, 討論了策略的競爭性能。

簡單貪婪策略 (SGS) :設t-1階段的倉儲中心為yi, 則在t階段進行判斷:若Cit≤C+minj≠iCjt, 則不改變倉儲中心, 仍然為yi, 否則選擇倉儲中心yj, 滿足j=argminj≠iCjt。

簡單貪婪策略是人們在處理類似P2問題時經常做出的選擇, 但是從競爭分析的角度而言, 在一般情形下簡單貪婪策略不是競爭的。要證明該策略不是競爭的, 只需構造一個序列, 使得貪婪策略在該序列下沒有常數競爭比, 或者競爭比無界, 因此構造下面特例:

設只有三個備選倉儲中心, 即y1、y2、y3, 同時構造T個階段的需求序列使得對應的各倉儲中心的運輸成本向量分別為:C1= (x, M, …, x, M) , C2= (M, x…, M, x) , C3= (x+ε, x+ε, …, x+ε) , 其中M>x+C, ε→0+。在這里向量Ci中的分量表示倉儲中心yi在某一階段的運輸成本Cit。

根據定義, 簡單貪婪策略的倉儲中心選擇序列為 (y1, y2, …, y1, y2) , 對應成本為Tx+ (T-1) C;而最優策略的選擇序列為 (y3, y3, …, y3) , 對應成本為Tx+Tε。因此一般情形下, 簡單貪婪策略的競爭比不小于r1=Τx+(Τ-1)CΤx+Τε=1+(Τ+1)CΤx, 而當C>>x時, r1是無界的, 因此有下面定理:

定理2 一般情形下, 簡單貪婪策略 (SGS) 不是競爭的。

上一小節論證了簡單貪婪策略在一般情形下不是競爭的。本節結合實際情況, 研究了經濟生活中經常存在的一種特殊情形下的簡單貪婪策略的競爭性能。特殊情形:任何階段中, 各倉儲中心的運輸成本都至少是改變倉儲中心所需轉化成本的α倍, 即存在關系:Cjt≥αC。在該特殊情形下, 當α是確定常數時, 簡單貪婪策略具有常數競爭比, 如定理3所示:

定理3 當Cjt≥αC時, 簡單貪婪策略 (SGS) 的競爭比為r2=1+1α。

證明 首先對于簡單貪婪策略而言, 如果在第t-1階段選擇的倉儲中心為yi, 則在第階段會出現兩種可能的情形:Cit≤C+minj≠iCjt或者Cit>C+minj≠iCjt。若Cit≤C+minj≠iCjt, 則不改變倉儲中心位置;若Cit>C+minj≠iCjt, 則倉儲中心位置變更為yj, 其中j=argminj≠iCjt。無論哪種情形, 簡單貪婪策略在每階段的成本 (Cont) 都滿足關系式:Cont≤C+minjCjt。對于離線最優策略而言, 每階段的成本 (Coptt) 不小于該階段的最小運輸成本, 即Coptt。≥minjCjt。

所以該情形下的策略競爭比為

r2=ConCopt=Τ∑t=1ContΤ∑t=1Coptt≤Τ∑t=1(minjCjt)+ΤCΤ∑t=1(minjCjt)=1+ΤCΤ∑t=1(minjCjt)≤1+1α (4)

證畢。

特殊情形下, 簡單貪婪策略的競爭性能給決策者的啟示是:當α較大時, 貪婪策略與離線最優策略的差距較小, 因此這種情況下簡單貪婪策略是合理的在線策略。值得注意的是, 很多決策者具有不同程度的成本敏感度, 即當成本差異在一定范圍之內可以接受, 超出該范圍就明顯感受到差異, 結合敏感度的啟示是, 當決策者的敏感度s≥α時, 對于決策者而言, 簡單貪婪策略和離線最優策略沒有區別;當決策者的敏感度s<α時, 能夠比較明顯地感受簡單貪婪策略和離線最優策略的差異。

假設某公司需要將產品運往5個需求點, 其可選擇的倉儲中心有3個, 倉儲中心與需求點以及需求點之間的距離如圖2所示。設定單位運輸成本c=1, 倉儲中心轉換成本C=800, T=4, Dt={q1, q2t, q3t, q4t, q5t}表示第t階段5個需求點的需求的集合, 其中D1={239, 179, 25, 19, 33}, D2={37, 29, 62, 158, 277}, D3={185, 166, 33, 28, 35}, D4={64, 75, 450, 224, 150}。

圖2 倉儲各心及需求點運輸路線示意圖  下載原圖

離線情景下, 公司對4個階段中需求點的需求狀況完全了解。由于可選倉儲中心只有3個, 因此無論采用DPA算法還是Dijkstra算法進行計算都不復雜, 本算例中采用本文設計的DPA算法進行求解:

Step 1 對第1階段各個倉儲中心的運輸成本進行計算, 如:C11=5∑i=1cdi1qi1=742, 并令C111=C11, 得到向量X1= (742, 1509, 2252) 。

Step 2 先對第2階段的第一個倉儲中心進行分析, 計算C212=min{C111+C12, min{C121+C+C12, C131+C+C12}}=C111+C12=3226, 同理可得C222=3201, C232=2439, 最終得到向量X2= (3226, 3201, 2439) ;以此類推, 再進行第3階段, 第4階段的計算, 得到X3= (3965, 4502, 4342) , X4= (6800, 6406, 6300) 。

Step 3 根據X4可知, 令Csummin=C434=6300, 標記j*T=3。

Step 4 根據第三步的結果進行逆推, 可知倉儲中心選擇的最優序列為 (1, 3, 3, 3) , 最低成本Copt=6300。

然而現實中, 公司往往對未來的需求信息并不能做到完全掌握。在線情境下, 假設公司僅知道當前階段的需求信息, 即在第t階段時, 公司僅知道Dt及t階段以前的信息。針對此情景, 采用文中設計的簡單貪婪策略進行求解, 具體如下:

Step 1 第1階段選擇成本最小的倉儲中心, 由C1i1=min{C11, C21, C31}=742可知為倉儲中心1, 即i=1。

Step 2 在選定倉儲中心1的基礎上進行第2階段選擇, 由C2i2=min{C111+C12, min{C111+C+C22, C111+C+C32}}=C111+C32=2439知選擇倉儲中心3;以此類推, 第3階段選擇倉儲中心1, C313=3978;第4階段選擇倉儲中心2, C424=6682。

Step 3 根據第二步的結果, 可知倉儲中心選擇序列為 (1, 3, 1, 2) , 最低成本Con=6682。

由以上兩部分計算可知, 此算例中在線與離線的比值r=ConCopt=1.1。結合定理3可知, 當倉儲中心轉換成本足夠小的情境下, 即滿足Cjt≥αC, 采用簡單貪婪策略可以有效的控制成本, 使得簡單貪婪策略的運輸成本與最優策略的成本比值總在一定的比例之內。

在物流管理中, 物流中心選址是一個經典問題, 以往的研究多是考慮自建設施。但在中國當前的經濟情境下, 城市地價飛漲, 自建倉儲中心的成本會遠遠超過租賃成本, 占用企業大量的資金。同時 , 如果只建單一倉儲中心, 當需求變動時, 無疑會大幅增加運輸成本;而建造多個倉儲中心, 不僅會增加投入, 同時還會面臨空置的風險, 增加了管理成本。因此, 當決策者資金有限, 或者銷售產品具有需求波動大的特點時, 往往會采取租用第三方倉儲中心的策略。

假設倉儲成本不變的條件下, 決策者出于運輸費用最小化考慮, 往往租用臨近消費者的倉儲中心, 但是消費者消費趨向的轉變往往導致以前的倉儲中心不再適合, 因此根據消費趨向的變化動態地選擇倉儲中心顯得尤為重要。本文首先針對未來需求變化完全預知的情形, 給出了時間復雜性為O (Tm2logn) 的離線算法;其次, 對于未來需求變化無法預知的情形, 分析了一般情形下, 簡單貪婪策略 (SGS) 的競爭性能, 指出一般情形下SGS不具有競爭性;并結合實際, 分析了特殊情形下 (Cjt≥αC) 的SGS, 證明了該情形下的競爭比為1+1α。而結合城市的交通狀況以及最新的經濟形勢, 設計合理的動態選址策略正是以后的研究方向。