精品久久一区,污黄啪啪网,16女下面流水不遮视频,色婷五月天

倉(cāng)儲(chǔ)中心是供應(yīng)鏈的重要節(jié)點(diǎn), 在物流管理中起著連接供應(yīng)鏈上下游的作用, 因此倉(cāng)儲(chǔ)中心的選址直接影響著其他物流決策, 有時(shí)候甚至決定著整個(gè)物流過(guò)程的效率和效益。對(duì)倉(cāng)儲(chǔ)中心位置進(jìn)行合理規(guī)劃是個(gè)傳統(tǒng)的物流問(wèn)題, 國(guó)內(nèi)外學(xué)者進(jìn)行了廣泛的研究。文獻(xiàn)[1]和文獻(xiàn)[2]從定性的角度分析了影響倉(cāng)儲(chǔ)中心選址的多種因素, 文獻(xiàn)[3]則從定量角度給出了線性規(guī)劃、動(dòng)態(tài)規(guī)劃等9種基本形式的選址模型。結(jié)合具體情景, 文獻(xiàn)[4]和文獻(xiàn)[5]在考慮庫(kù)存及運(yùn)輸配送的基礎(chǔ)上, 建立倉(cāng)儲(chǔ)中心選址模型, 并驗(yàn)證了其合理性。

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

本文所研究的問(wèn)題描述如下:某公司需要把產(chǎn)品從不同的產(chǎn)地運(yùn)往銷售地, 銷售地分散著n個(gè)需求點(diǎn), 每個(gè)需求點(diǎn)的需求量隨時(shí)間而變化。同時(shí)在銷售地的不同區(qū)域分散著m個(gè)第三方倉(cāng)儲(chǔ)中心, 公司根據(jù)不同時(shí)期的需求量變化情況, 動(dòng)態(tài)地選擇倉(cāng)儲(chǔ)中心, 而倉(cāng)儲(chǔ)中心的更換需要固定的轉(zhuǎn)換成本, 如果限定每階段只選擇一個(gè)倉(cāng)儲(chǔ)中心, 那么公司應(yīng)如何動(dòng)態(tài)地選擇倉(cāng)儲(chǔ)中心使得經(jīng)營(yíng)成本盡量小?

針對(duì)該問(wèn)題, 給出以下符號(hào)定義:

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

便于討論, 本文基于以下假設(shè):

(1) 不同產(chǎn)地到不同倉(cāng)儲(chǔ)中心的距離相同;

(2) 由于資金或其他限制, 每階段只選一個(gè)倉(cāng)儲(chǔ)中心;

(3) 在同一時(shí)期內(nèi), 不同倉(cāng)儲(chǔ)中心的單位庫(kù)存成本相同;

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

需要說(shuō)明的是, 產(chǎn)地到銷售地的距離相對(duì)于不同倉(cāng)儲(chǔ)中心間的距離大得多, 因此在選擇倉(cāng)儲(chǔ)中心的決策中, 假設(shè)⑴認(rèn)為不同產(chǎn)地到不同倉(cāng)儲(chǔ)中心的距離相同, 可以不考慮產(chǎn)地到銷售地的距離影響。假設(shè)⑶說(shuō)明同一時(shí)期的總庫(kù)存成本不會(huì)因?yàn)閭}(cāng)儲(chǔ)中心的不同而不同, 因此只需要考慮從倉(cāng)儲(chǔ)中心到需求點(diǎn)的運(yùn)輸成本, 精簡(jiǎn)了論證過(guò)程。

現(xiàn)在考慮下面兩個(gè)問(wèn)題:

P1:所有需求點(diǎn)在不同階段的需求情況已知時(shí), 如何進(jìn)行倉(cāng)儲(chǔ)中心的選擇?

P2:在任何階段, 只知道該階段及以前階段各個(gè)需求點(diǎn)的需求情況, 如何進(jìn)行倉(cāng)儲(chǔ)中心的選擇?

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

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

則稱該在線策略G為r競(jìng)爭(zhēng)策略, 或者該在線策略具有競(jìng)爭(zhēng)比r, 如果某一個(gè)在線策略的競(jìng)爭(zhēng)比滿足r*=lnf(r)G?則稱r*為該在線問(wèn)題的最優(yōu)競(jìng)爭(zhēng)比[14]。

文章第三部分針對(duì)P1問(wèn)題給出了線性時(shí)間的動(dòng)態(tài)規(guī)劃算法, 論證了結(jié)論的最優(yōu)性;第四部分針對(duì)P2問(wèn)題給出了一種簡(jiǎn)單貪婪策略, 并討論了該策略在一般情形和特殊情形下的競(jìng)爭(zhēng)性能;第五部分分別用DPA算法和簡(jiǎn)單貪婪策略對(duì)算例進(jìn)行分析求解;第六部分對(duì)文章進(jìn)行了總結(jié)及展望。

當(dāng)所有需求點(diǎn)在不同階段的需求情況已知時(shí), 本文給出了線性時(shí)間的動(dòng)態(tài)規(guī)劃算法, 在給出算法之前, 首先討論最優(yōu)解的有關(guān)性質(zhì)。假設(shè)決策期包含T個(gè)階段, 如果不考慮轉(zhuǎn)換成本, 則在任意階段t, 選擇第j個(gè)備選倉(cāng)儲(chǔ)中心的運(yùn)輸成本為:

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

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

我們可以通過(guò)以下兩個(gè)輔助操作, 把該特殊最短路問(wèn)題轉(zhuǎn)化為一般的分階段最短路問(wèn)題: (1) 增加兩個(gè)虛擬結(jié)點(diǎn):一個(gè)初始結(jié)點(diǎn)O和一個(gè)終止結(jié)點(diǎn)D, 同時(shí)連接結(jié)點(diǎn)O和第一階段的m個(gè)結(jié)點(diǎn), 以及結(jié)點(diǎn)D和最后階段的m個(gè)結(jié)點(diǎn), 令增加的虛擬結(jié)點(diǎn)和虛擬弧的權(quán)重均為0; (2) 把第t階段的結(jié)點(diǎn)yjt的權(quán)重變?yōu)?, 把結(jié)點(diǎn)yji所有入弧的權(quán)重都增加Cjt。則可以用圖1描述該特殊最短路問(wèn)題, 其中最短路徑對(duì)應(yīng)的結(jié)點(diǎn)就是最優(yōu)的倉(cāng)儲(chǔ)中心選擇序列。

因?yàn)樵撟疃搪穯?wèn)題具有 (Tm+2) 個(gè)結(jié)點(diǎn), 所以直接利用Dijkstra算法對(duì)該最短路問(wèn)題進(jìn)行求解的時(shí)間復(fù)雜性為O ( (Tm) 2) 。為了尋找更加快捷的算法, 對(duì)問(wèn)題的最優(yōu)解結(jié)構(gòu)進(jìn)行分析:設(shè)Ctit為第t階段選擇中心yi時(shí), 前t階段的最小總成本, 且定義Yit為實(shí)現(xiàn)Ctit時(shí)從第1階段到第t階段的倉(cāng)儲(chǔ)中心序列, 則下面的引理是顯然的:

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

圖1 P1問(wèn)題的最短路模型示意圖  下載原圖

結(jié)合前文對(duì)Cjt的定義, 有以下遞推關(guān)系:

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

根據(jù)引理1和關(guān)系式 (3) , 給出離線問(wèn)題的動(dòng)態(tài)規(guī)劃算法 (DPA) 如下:

Step 1 計(jì)算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++) , 計(jì)算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}, 則標(biāo)記ji (t-1) =i, 否則標(biāo)記ji(t-1)=j=argminj≠i{Ct-1j(t-1)+C+Cit}, 同時(shí)得到向量Xt= (Ct1t, Ct2t, …, Ctmt) T。

Step 3 令Csummin=min1≤j≤mCΤjΤ, 標(biāo)記j*Τ=j=argminjCΤjΤ。

Step 4 標(biāo)記j*T-1=jj*T (T-1) , 令T=T-1, 當(dāng)T=1時(shí)結(jié)束, 否則返回Step 4, 并記錄Csummin以及序列 (j*1, j*2, …j*T) 。

其中序列 (j*1, j*2, …j*T) 對(duì)應(yīng)的倉(cāng)儲(chǔ)中心序列即為最優(yōu)的選擇序列, 最優(yōu)成本為Csummin。

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

定理1 對(duì)于P1問(wèn)題, 存在時(shí)間復(fù)雜性為O (Tm2logm) 的線性算法 (DPA) 。

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

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

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

簡(jiǎn)單貪婪策略是人們?cè)谔幚眍愃?span>P2問(wèn)題時(shí)經(jīng)常做出的選擇, 但是從競(jìng)爭(zhēng)分析的角度而言, 在一般情形下簡(jiǎn)單貪婪策略不是競(jìng)爭(zhēng)的。要證明該策略不是競(jìng)爭(zhēng)的, 只需構(gòu)造一個(gè)序列, 使得貪婪策略在該序列下沒(méi)有常數(shù)競(jìng)爭(zhēng)比, 或者競(jìng)爭(zhēng)比無(wú)界, 因此構(gòu)造下面特例:

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

根據(jù)定義, 簡(jiǎn)單貪婪策略的倉(cāng)儲(chǔ)中心選擇序列為 (y1, y2, …, y1, y2) , 對(duì)應(yīng)成本為Tx+ (T-1) C;而最優(yōu)策略的選擇序列為 (y3, y3, …, y3) , 對(duì)應(yīng)成本為Tx+Tε。因此一般情形下, 簡(jiǎn)單貪婪策略的競(jìng)爭(zhēng)比不小于r1=Τx+(Τ-1)CΤx+Τε=1+(Τ+1)CΤx, 而當(dāng)C>>x時(shí), r1是無(wú)界的, 因此有下面定理:

定理2 一般情形下, 簡(jiǎn)單貪婪策略 (SGS) 不是競(jìng)爭(zhēng)的。

上一小節(jié)論證了簡(jiǎn)單貪婪策略在一般情形下不是競(jìng)爭(zhēng)的。本節(jié)結(jié)合實(shí)際情況, 研究了經(jīng)濟(jì)生活中經(jīng)常存在的一種特殊情形下的簡(jiǎn)單貪婪策略的競(jìng)爭(zhēng)性能。特殊情形:任何階段中, 各倉(cāng)儲(chǔ)中心的運(yùn)輸成本都至少是改變倉(cāng)儲(chǔ)中心所需轉(zhuǎn)化成本的α倍, 即存在關(guān)系:Cjt≥αC。在該特殊情形下, 當(dāng)α是確定常數(shù)時(shí), 簡(jiǎn)單貪婪策略具有常數(shù)競(jìng)爭(zhēng)比, 如定理3所示:

定理3 當(dāng)Cjt≥αC時(shí), 簡(jiǎn)單貪婪策略 (SGS) 的競(jìng)爭(zhēng)比為r2=1+1α。

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

所以該情形下的策略競(jìng)爭(zhēng)比為

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

證畢。

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

假設(shè)某公司需要將產(chǎn)品運(yùn)往5個(gè)需求點(diǎn), 其可選擇的倉(cāng)儲(chǔ)中心有3個(gè), 倉(cāng)儲(chǔ)中心與需求點(diǎn)以及需求點(diǎn)之間的距離如圖2所示。設(shè)定單位運(yùn)輸成本c=1, 倉(cāng)儲(chǔ)中心轉(zhuǎn)換成本C=800, T=4, Dt={q1, q2t, q3t, q4t, q5t}表示第t階段5個(gè)需求點(diǎn)的需求的集合, 其中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 倉(cāng)儲(chǔ)各心及需求點(diǎn)運(yùn)輸路線示意圖  下載原圖

離線情景下, 公司對(duì)4個(gè)階段中需求點(diǎn)的需求狀況完全了解。由于可選倉(cāng)儲(chǔ)中心只有3個(gè), 因此無(wú)論采用DPA算法還是Dijkstra算法進(jìn)行計(jì)算都不復(fù)雜, 本算例中采用本文設(shè)計(jì)的DPA算法進(jìn)行求解:

Step 1 對(duì)第1階段各個(gè)倉(cāng)儲(chǔ)中心的運(yùn)輸成本進(jìn)行計(jì)算, 如:C11=5∑i=1cdi1qi1=742, 并令C111=C11, 得到向量X1= (742, 1509, 2252) 。

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

Step 3 根據(jù)X4可知, 令Csummin=C434=6300, 標(biāo)記j*T=3。

Step 4 根據(jù)第三步的結(jié)果進(jìn)行逆推, 可知倉(cāng)儲(chǔ)中心選擇的最優(yōu)序列為 (1, 3, 3, 3) , 最低成本Copt=6300。

然而現(xiàn)實(shí)中, 公司往往對(duì)未來(lái)的需求信息并不能做到完全掌握。在線情境下, 假設(shè)公司僅知道當(dāng)前階段的需求信息, 即在第t階段時(shí), 公司僅知道Dt及t階段以前的信息。針對(duì)此情景, 采用文中設(shè)計(jì)的簡(jiǎn)單貪婪策略進(jìn)行求解, 具體如下:

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

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

Step 3 根據(jù)第二步的結(jié)果, 可知倉(cāng)儲(chǔ)中心選擇序列為 (1, 3, 1, 2) , 最低成本Con=6682。

由以上兩部分計(jì)算可知, 此算例中在線與離線的比值r=ConCopt=1.1。結(jié)合定理3可知, 當(dāng)倉(cāng)儲(chǔ)中心轉(zhuǎn)換成本足夠小的情境下, 即滿足Cjt≥αC, 采用簡(jiǎn)單貪婪策略可以有效的控制成本, 使得簡(jiǎn)單貪婪策略的運(yùn)輸成本與最優(yōu)策略的成本比值總在一定的比例之內(nèi)。

在物流管理中, 物流中心選址是一個(gè)經(jīng)典問(wèn)題, 以往的研究多是考慮自建設(shè)施。但在中國(guó)當(dāng)前的經(jīng)濟(jì)情境下, 城市地價(jià)飛漲, 自建倉(cāng)儲(chǔ)中心的成本會(huì)遠(yuǎn)遠(yuǎn)超過(guò)租賃成本, 占用企業(yè)大量的資金。同時(shí) , 如果只建單一倉(cāng)儲(chǔ)中心, 當(dāng)需求變動(dòng)時(shí), 無(wú)疑會(huì)大幅增加運(yùn)輸成本;而建造多個(gè)倉(cāng)儲(chǔ)中心, 不僅會(huì)增加投入, 同時(shí)還會(huì)面臨空置的風(fēng)險(xiǎn), 增加了管理成本。因此, 當(dāng)決策者資金有限, 或者銷售產(chǎn)品具有需求波動(dòng)大的特點(diǎn)時(shí), 往往會(huì)采取租用第三方倉(cāng)儲(chǔ)中心的策略。

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