大型貨站貨物流配給策略研究

大型貨站貨物流配給策略研究

0動(dòng)態(tài)路徑策略隨著當(dāng)今社會(huì)，先進(jìn)的自動(dòng)倉(cāng)庫(kù)和配送中心在全球供應(yīng)鏈中發(fā)揮著越來(lái)越重要的作用。例如，為了節(jié)省勞動(dòng)力，現(xiàn)代物流中心（rss）使用自動(dòng)倉(cāng)庫(kù)系統(tǒng)（rss）來(lái)使用較高的空間，加快貨物的轉(zhuǎn)移。綜合自動(dòng)化裝運(yùn)處理系統(tǒng)(IASHSs)由多個(gè)ASRSs及各種各樣的處理站組成,并與物料處理設(shè)備組成的復(fù)雜網(wǎng)絡(luò)連接。本論文中,我們討論從一個(gè)大型空運(yùn)貨站——香港空運(yùn)貨站(HACTL)的工程項(xiàng)目里得到的一個(gè)設(shè)施物流網(wǎng)絡(luò)問(wèn)題,該問(wèn)題討論具有不同權(quán)重的多個(gè)貨物流如何在起訖點(diǎn)之間運(yùn)輸。已有很多文獻(xiàn)對(duì)貨運(yùn)站及設(shè)施物流進(jìn)行研究。Stahlbock,Gunther和Kim及Hartmann已經(jīng)對(duì)這一領(lǐng)域進(jìn)行了很好的研究,韓曉龍建立龍門(mén)吊的數(shù)量配置網(wǎng)絡(luò)流模型。對(duì)ASRS路徑問(wèn)題的早期研究主要關(guān)注某個(gè)特殊設(shè)備的作業(yè)規(guī)則,Graves等人表明一個(gè)較好的路徑會(huì)使得取貨時(shí)間降低達(dá)30%之多,VandeBerg和Gademanna研究了如何在使SR機(jī)器完成所有存取要求的條件下選擇路徑,使總時(shí)間最短。還有許多文獻(xiàn)研究了彈性制造系統(tǒng)(FMSs)的路徑策略。Yao和Pei根據(jù)熵標(biāo)準(zhǔn)研究FMSs路徑的動(dòng)態(tài)部分,他們給出了兩種作業(yè)規(guī)則,并將其與“處理時(shí)間最短”(SPT)規(guī)則進(jìn)行比較。包括Seidmann和Tenenbaum在內(nèi)的很多學(xué)者研究動(dòng)態(tài)部分的配給策略,并給出使處理能力最大的最優(yōu)策略。研究表明,在移動(dòng)電話系統(tǒng)中動(dòng)態(tài)路徑策略很有效(Boucher等)。由于設(shè)備數(shù)量很少,上述文獻(xiàn)都是以狀態(tài)空間方式研究系統(tǒng)作業(yè)情況。Kliewer等建立了基于時(shí)空網(wǎng)絡(luò)的動(dòng)態(tài)模型。但是,IASHS的網(wǎng)絡(luò)規(guī)模比FMS的網(wǎng)絡(luò)規(guī)模大的多,典型的IASHS包含幾百個(gè)關(guān)鍵設(shè)備、大量的連接設(shè)備及成千上萬(wàn)個(gè)儲(chǔ)存位置。用狀態(tài)空間的方式建立此問(wèn)題的模型就不太現(xiàn)實(shí),主要有以下兩個(gè)方面的問(wèn)題:首先是上述提到的網(wǎng)絡(luò)規(guī)模龐大及計(jì)劃時(shí)期較長(zhǎng);另外,此問(wèn)題的關(guān)鍵設(shè)備按先到先服務(wù)(FCFS)的原則作業(yè),因此很難建立簡(jiǎn)單的時(shí)空網(wǎng)絡(luò)模型。對(duì)交通運(yùn)輸路徑的路徑策略的研究也很多。在過(guò)去十年間,Merchant和Nemhauser、Carey使用了已公式化的動(dòng)態(tài)路徑模型,另外,Friesz等與Astarita利用路徑運(yùn)輸延遲建立模型,杜進(jìn)有等改進(jìn)了在一定運(yùn)輸需求條件下對(duì)路網(wǎng)上雙向、空重車流路徑同時(shí)進(jìn)行優(yōu)化的多目標(biāo)滿意優(yōu)化模型,并通過(guò)建立獨(dú)立滿意度和綜合滿意度來(lái)衡量?jī)?yōu)化解的品質(zhì)。侯立文等同時(shí)考慮客戶需求可分以及客戶方和配送中心時(shí)間窗限制的前提下,重新構(gòu)造了路徑問(wèn)題模型。朱晨波等運(yùn)用基于馬爾可夫決策過(guò)程的分解方法,研究一種有車輛限制、長(zhǎng)期的直接配送的三層隨機(jī)庫(kù)存路徑問(wèn)題。郭耀煌和鐘小鵬以顧客等待時(shí)間最小化作為系統(tǒng)目標(biāo),利用排隊(duì)理論研究了一類動(dòng)態(tài)車輛路徑的實(shí)時(shí)優(yōu)化策略。我們所研究的問(wèn)題與交通路徑問(wèn)題的有以下不同點(diǎn):首先,交通路徑問(wèn)題研究的對(duì)象是交通流,而我們的問(wèn)題研究的是單個(gè)貨物,因此,前者的目的是一般是推導(dǎo)網(wǎng)絡(luò)流平衡點(diǎn),設(shè)計(jì)交通網(wǎng)絡(luò);而我們的目的則是尋找運(yùn)輸所有貨物的最優(yōu)方案。第二,交通路徑問(wèn)題在進(jìn)行路徑?jīng)Q策時(shí)是分權(quán)的,因?yàn)槊總€(gè)車主的決策是獨(dú)立的;而我們研究的空運(yùn)貨站路徑問(wèn)題,可以由系統(tǒng)進(jìn)行集中決策?？傮w來(lái)說(shuō),前者的目的是推導(dǎo)出一種網(wǎng)絡(luò)平衡或者達(dá)到最大-最小公平;而本文的目的是尋找整個(gè)系統(tǒng)的最優(yōu)路徑策略。1hactl的路徑策略在介紹我們的模型與方法之前,有必要先解釋一下IASHS的組成部分及其運(yùn)行過(guò)程。一個(gè)IASHS系統(tǒng)通常由幾個(gè)ASRS系統(tǒng)及大量工作站組成,并且他們通過(guò)物料搬運(yùn)設(shè)備組成的網(wǎng)絡(luò)連接起來(lái)。單個(gè)ASRS用自動(dòng)存儲(chǔ)/取出設(shè)備在ASRS系統(tǒng)的進(jìn)庫(kù)/出庫(kù)臺(tái)(SEPs)與存儲(chǔ)貨架之間運(yùn)輸貨物,其中,物料搬運(yùn)設(shè)備根據(jù)其功能可分為兩類。第一類是關(guān)鍵設(shè)備,這些設(shè)備通常很昂貴,并且有多個(gè)輸入通道獲得貨物,多個(gè)出口通道運(yùn)出貨物,如臺(tái)架運(yùn)貨機(jī)(與自動(dòng)存儲(chǔ)/取出設(shè)備相似)即能水平運(yùn)動(dòng)又能垂直運(yùn)動(dòng),其中,自動(dòng)運(yùn)貨車水平運(yùn)動(dòng),升降臺(tái)垂直運(yùn)動(dòng),轉(zhuǎn)車臺(tái)能水平的改變運(yùn)送貨物的方向。另一類是連接設(shè)備,他們起到連接關(guān)鍵設(shè)備與系統(tǒng)SEPs的作用,如運(yùn)輸設(shè)備、動(dòng)力滾軸、貨物緩沖設(shè)備(等待關(guān)鍵設(shè)備處理)。由于IASHS的結(jié)構(gòu)網(wǎng)絡(luò)復(fù)雜,其中的動(dòng)作也比單個(gè)ASRS復(fù)雜的多。IASHS包含三種形式的動(dòng)作:從SEPs到ASRS貨架的存儲(chǔ)貨物動(dòng)作、從ASRS到SEPs的取出貨物動(dòng)作、不同ASRS之間的轉(zhuǎn)運(yùn)貨物及從處理站到ASRS的轉(zhuǎn)運(yùn)貨物動(dòng)作。整個(gè)流程為:當(dāng)一個(gè)航空集裝箱ULD(空運(yùn)貨站業(yè)務(wù)的集裝箱,接下來(lái)我們將此作為貨運(yùn)需求單位)到達(dá)一個(gè)大規(guī)模航空站時(shí),首先儲(chǔ)存在ASRS貨架,接著可能被取出到處理站進(jìn)行某些特殊操作。如被拆散成多個(gè)散包裝。接著,這些ULDs(以批量/箱的形式)被轉(zhuǎn)移到顧客清關(guān)中心,然后運(yùn)送到另一個(gè)ASRS進(jìn)行批量?jī)?chǔ)存。最后,從SEPs取出。HACTL擁有超級(jí)一號(hào)貨站,就貨量而言,它是全球最大的空運(yùn)貨站,圖1是它的簡(jiǎn)圖。從圖1可以看出,網(wǎng)絡(luò)結(jié)構(gòu)很復(fù)雜。這個(gè)貨站擁有350多個(gè)工作站及3500多個(gè)存儲(chǔ)機(jī)架。在SEPs與存儲(chǔ)機(jī)架之間有成千上萬(wàn)個(gè)連接設(shè)備來(lái)進(jìn)行物料的自動(dòng)搬運(yùn)。自動(dòng)物料搬運(yùn)設(shè)備分布在一個(gè)大樓里,這個(gè)大樓分為貨運(yùn)大樓及分布在貨運(yùn)大樓東西兩端的兩個(gè)貨箱貯存系統(tǒng),這兩個(gè)貨箱貯存系統(tǒng)通過(guò)72個(gè)高架橋與貨運(yùn)大樓相連。第一層是由動(dòng)力滾軸組成的主要線路類型軌道(下文就稱此為主線路),這些線路不僅將普通貨物儲(chǔ)藏區(qū)與冷藏貨物儲(chǔ)藏區(qū)分開(kāi),還在兩個(gè)儲(chǔ)藏區(qū)之間架起了可通行的橋梁。因此,建立這個(gè)系統(tǒng)的路徑策略非常具有挑戰(zhàn)性,設(shè)備尤其是關(guān)鍵設(shè)備的選擇非常困難。為了說(shuō)明這一點(diǎn),一對(duì)起訖點(diǎn)(OD,起點(diǎn)或者訖點(diǎn)可以是SEP或者存儲(chǔ)機(jī)架)之間至少要包含4個(gè)升降機(jī)、2個(gè)自動(dòng)運(yùn)貨車、兩個(gè)臺(tái)架運(yùn)貨機(jī)及大量的連接設(shè)備。在5層高的大樓里,一個(gè)OD對(duì)有15～40個(gè)實(shí)際可行路徑。例如,最簡(jiǎn)單的路徑可能是由升降臺(tái)到2樓,通過(guò)主路徑,再通過(guò)臺(tái)架運(yùn)貨機(jī)到4樓的存儲(chǔ)貨架。同樣,還可以從一樓的工作站出發(fā)。由升降機(jī)到3樓,通過(guò)高架橋,接著采用自動(dòng)運(yùn)貨車,然后通過(guò)臺(tái)架運(yùn)貨機(jī)到4樓的存儲(chǔ)貨架。目前HACTL的做法很簡(jiǎn)單。HACTL的路徑策略基于路徑列表,列表中,每個(gè)OD對(duì)之間都由很多被賦予不同分值的路徑。根據(jù)OD的位置以及網(wǎng)絡(luò)布局,路徑列表中可以有5～40個(gè)路徑。當(dāng)一單位貨物要在一個(gè)OD對(duì)之間運(yùn)輸時(shí),采用路徑列表中分值最低的路徑,當(dāng)選擇的路徑中有設(shè)備在進(jìn)行維護(hù)時(shí)就選擇備用路徑,這樣,大概90%的貨物采用分值最低的路徑(也可看作最短路徑)。在忙時(shí),由于很多路徑都要用到關(guān)鍵設(shè)備,系統(tǒng)采用上述路徑策略時(shí),經(jīng)常出現(xiàn)嚴(yán)重阻塞。數(shù)據(jù)表明,實(shí)際上貨物的存儲(chǔ)與取出要花費(fèi)3個(gè)多小時(shí),顯然遠(yuǎn)遠(yuǎn)達(dá)不到理想的績(jī)效要求。并且,當(dāng)前采用的路徑策略不能根據(jù)需求優(yōu)先要求處理具有不同優(yōu)先權(quán)的貨物。例如,在一個(gè)空運(yùn)貨站中,必須賦予需要速遞的貨物較高的優(yōu)先權(quán),由于出口貨物什么時(shí)候運(yùn)出取決于飛機(jī)起飛時(shí)間,因此出口ULDs比進(jìn)口ULDs更緊急。由于當(dāng)前路徑策略的這些局限性,為了優(yōu)化系統(tǒng)性能,在第2節(jié)中我們將給出貨物流配給原則,然后建立相應(yīng)的數(shù)學(xué)模型進(jìn)行分析。第3節(jié)我們進(jìn)行了大量的模擬實(shí)驗(yàn)并提供數(shù)值結(jié)果,實(shí)驗(yàn)結(jié)果表明貨物流配給策略比當(dāng)前的策略優(yōu)越很多。第4節(jié)給出我們的結(jié)論。2mdp模型求解本節(jié)我們將給出貨物配給原則的概念。貨物配給原則將路徑分為若干不同的集合,每個(gè)集合對(duì)應(yīng)一種貨物流類型。為了避免路徑空閑或者利用率較低,某些特殊的路徑集合允許權(quán)重較低的需求通過(guò)。我們考慮普通需求和緊急需求這兩種貨物流類型的情況。假設(shè)每個(gè)OD對(duì)之間都有兩種路徑集合:分別為普通需求和緊急需求類型設(shè)定的普通路徑和速遞路徑。所有的緊急需求必須在速遞路徑上運(yùn)輸,但是普通需求即可以在速遞路徑也可以在普通路徑運(yùn)輸,這取決于速遞路徑的利用情況。通常情況下,普通路徑的數(shù)量都多于速遞路徑,本文中我們先研究單一速遞路徑問(wèn)題,即每對(duì)OD之間僅存在一條速遞路徑的配給問(wèn)題。是否允許普通ULD在速遞路徑上運(yùn)輸取決于當(dāng)前路徑的利用情況及接下來(lái)可能到達(dá)的潛在緊急ULDs。本文用“飽和度”表示路徑的利用情況。飽和度指路徑能同時(shí)運(yùn)輸?shù)腢LDs數(shù)量。要特別強(qiáng)調(diào)的是:飽和度的一個(gè)重要性質(zhì)就是可恢復(fù)性,即當(dāng)一條路徑上的貨物運(yùn)輸完成時(shí)這條路徑的飽和度可以恢復(fù)。因此,系統(tǒng)運(yùn)行的不同時(shí)刻路徑的飽和度是不斷變化的。通過(guò)權(quán)衡(1)為潛在緊急ULDs預(yù)留飽和度還是(2)為避免緊急ULDs比預(yù)測(cè)過(guò)少而帶來(lái)的飽和度浪費(fèi),決定是否允許普通ULD使用速遞路徑。本文中我們用馬爾可夫決策決策過(guò)程(MDP)模型來(lái)處理這一過(guò)程。在給出模型之前,先定義以下符號(hào)。符號(hào)S:路徑飽和度。t:時(shí)期指標(biāo),t=1,2,…,T。At:t時(shí)期的可用飽和度。Rt:t時(shí)期通過(guò)速遞路徑配送普通需求貨物的收益。Wt:t時(shí)期的到達(dá)的普通貨物總量。(t,A):狀態(tài)變量。V(t,A):t時(shí)期的最優(yōu)價(jià)值函數(shù)。N(x):在前一期的使用的飽和度為x時(shí),本期可以恢復(fù)的飽和度。不失一般性,在下面的討論中,為了表達(dá)方便,符號(hào)的下標(biāo)t都省略。在這個(gè)模型中,恢復(fù)函數(shù)N(x)表示系統(tǒng)中運(yùn)出x的ULD以后可以恢復(fù)的飽和度,A+N(S-A)表示若前一期的可用飽和度為A時(shí),本期的可用飽和度為A+N(S-A)。根據(jù)航空站的網(wǎng)絡(luò)特征,我們假設(shè)A+N(S-A)滿足:1)是關(guān)于A的非減函數(shù);2)是關(guān)于A的凸函數(shù);3)且A+N(S-A)≤S。下面簡(jiǎn)單解釋一下這三個(gè)性質(zhì),性質(zhì)1表明網(wǎng)絡(luò)中ULDs越多從網(wǎng)絡(luò)中運(yùn)出的ULDs也就越多;性質(zhì)2反映了可用飽和度越大,網(wǎng)絡(luò)中的阻塞就越少,這反過(guò)來(lái)增加了飽和度的恢復(fù)速度;性質(zhì)3表明了任一時(shí)期的可用飽和的都不能超過(guò)總飽和度。實(shí)際經(jīng)驗(yàn)表明,飽和度恢復(fù)函數(shù)可以使用線性函數(shù),例如N(x)=x/3,從而A+N(S-A)=(S+2A)/3。根據(jù)以上約定的符號(hào),最優(yōu)方程可表示為:V(t,A)=EW,R{max{V(t+1,A-W+N(S-A))+R,V(t+1,A+N(S-A))}}且邊界條件為:V(T+1,A)=0.V(Τ+1,A)=0.下面的引理和定理指出了MDP模型的最優(yōu)函數(shù)的性質(zhì)。引理1給定t時(shí),V(t,A)是A的非減函數(shù)。證明:用數(shù)學(xué)歸納法來(lái)證明。顯然V(T+1,A)是A的非減函數(shù),假設(shè)V(t+1,A)是A的非減函數(shù),其中t=T,T-1,…,1,我們需要證明V(t,A)是非減的。由于A+N(S-A)是非減的,所以對(duì)任意給定R和W,V(t+1,A-W+N(S-A))+R與V(t+1,A+N(S-A))都是非減函數(shù),因此max{V(t+1,A-W+N(S-A))+R,V(t+1,A+N(S-A))}是非減函數(shù),從而V(t,A)是非減函數(shù),命題得證。引理2給定t時(shí),V(t,A)是A的凸函數(shù)。證明:同樣,還是用數(shù)學(xué)歸納法。首先,顯然t=T+1時(shí),命題成立。假設(shè)給定t,V(t+1,A)是A上的凸函數(shù),其中t=T,T-1,…,1,我們需要證明V(t,A)也是A的凸函數(shù)。由于A+N(S-A)是凸函數(shù)且V(t,A)是非減的,所以V(t+1,A-W+N(S-A))+R與V(t+1,A+N(S-A))都是凸函數(shù),從而,對(duì)任意給定的R,W,max{V(t+1,A-W+N(S-A))+R,V(t+1,A+N(S-A))}是凸函數(shù),這就意味著V(t,A)是凸函數(shù),命題得證。定理1最優(yōu)策略為:其中,RW(t,A)=V(t,A+N(S-A))-V(t,A-W+N(S-A))。并且,對(duì)給定t,RW(t,A)是非減的。證明:根據(jù)RW(t,A)及V(t,A)的定義,該策略是一個(gè)當(dāng)前最優(yōu)策略(myopicstrategy),由于該模型的收益函數(shù)是獨(dú)立的變量R,根據(jù)馬爾科夫決策過(guò)程的性質(zhì),該局部最優(yōu)策略也是全局最優(yōu)策略。并且,由于V(t,A)關(guān)于是A的凸函數(shù)及A+N(S-A)是A的非減函數(shù),因此對(duì)給定t,RW(t,A)是非減的。我們的貨物運(yùn)輸策略如下:(1)對(duì)于緊急貨物,我們直接用速遞路徑來(lái)運(yùn)輸;(2)對(duì)于普通貨物,依據(jù)其數(shù)量、收益、當(dāng)前速遞路徑的飽和度等,用定理1決定是否用速遞路徑來(lái)運(yùn)輸。MDP模型及貨物流配給原則的運(yùn)用很復(fù)雜。在運(yùn)用MDP模型及貨物流配給原則時(shí),應(yīng)該考慮大量問(wèn)題,包括:1)如何確定飽和度;2)如何劃分時(shí)期;3)如何選擇恢復(fù)函數(shù);4)如何將ULD需求轉(zhuǎn)化成離散的隨機(jī)變量。以上問(wèn)題我們將在下面數(shù)值試驗(yàn)具體實(shí)施過(guò)程中介紹。3實(shí)際造成的仿真實(shí)驗(yàn)為了評(píng)價(jià)我們定義的路徑策略的有效性,我們?cè)O(shè)計(jì)了一個(gè)仿真體統(tǒng),該仿真系統(tǒng)具有實(shí)際空運(yùn)貨站的主要特征。該仿真實(shí)驗(yàn)是在一臺(tái)CPU雙核2.0GHz,內(nèi)存1024M的個(gè)人電腦上進(jìn)行的。貨物流分為兩類:普通類和緊急類。3.1合成貨物流配我們選兩個(gè)不同的最短路徑策略作為基準(zhǔn),一個(gè)是分類獨(dú)立的最短路徑(SPI)策略,另一個(gè)是分類依賴的最短路徑(SPD)策略。其中SPI這樣決策,給定一個(gè)ULD,不論其類型,根據(jù)其OD確定一條最短路徑運(yùn)輸這個(gè)ULD。SPD則是對(duì)每個(gè)OD,確定一組路徑,每條路徑對(duì)應(yīng)一個(gè)權(quán)重類型。給定ULD并確定其權(quán)重類型后,就找到相應(yīng)路徑來(lái)進(jìn)行運(yùn)輸?，F(xiàn)在我們來(lái)構(gòu)造貨物流配給(FR)路徑策略,首先用SPI策略的最短路徑作為速遞路徑,另外有三個(gè)路徑作為普通路徑。假設(shè)用SPI可以完成90%的ULDs,并記錄模擬時(shí)間(32400秒)內(nèi)每個(gè)OD對(duì)能完成的ULDs的運(yùn)輸量。連續(xù)進(jìn)行100次,記錄其平均值,并將其作為速遞路徑的飽和度。另外,我們選定每個(gè)時(shí)期的時(shí)間長(zhǎng)度為1小時(shí),因此,整個(gè)模擬時(shí)間就可以分為9個(gè)時(shí)期,即T=9,恢復(fù)函數(shù)設(shè)為N(x)=x/ω,其中參數(shù)ω根據(jù)一個(gè)時(shí)期內(nèi)對(duì)應(yīng)路徑能完成的ULDs的運(yùn)輸量的平均值來(lái)確定。另外,我們注意到ULD的到達(dá)規(guī)律服從泊松過(guò)程,下一時(shí)期的ULD量服從泊松分布。鑒于阻塞以指數(shù)形式增長(zhǎng),我們?cè)O(shè)定R(t)=σ(Wt)puWt,其中,σ(Wt)=3Wt是Wt的增函數(shù),pu是緊急貨物的成本系數(shù),設(shè)為3。最后,普通ULDs以隨機(jī)形式分配到普通路徑,即將普通ULDs均勻分布到可能的普通路徑上。3.2仿真結(jié)果的分析我們構(gòu)建了一個(gè)仿真的系統(tǒng),由166個(gè)重要設(shè)備和304個(gè)連接設(shè)備組成。這個(gè)系統(tǒng)共有3層,上述設(shè)備在這個(gè)系統(tǒng)中均勻地分布。此外,為了測(cè)試我們的策略在不同貨物流環(huán)境下的表現(xiàn),我們考慮了兩種情形,穩(wěn)定貨物流(UR)和變動(dòng)貨物流(VR)。這兩種情形下,貨物流都是依照Poisson過(guò)程來(lái)到。但是第一種貨物流情形下,Poisson過(guò)程的速率是常數(shù)不變的;但是在第二種情形下,Poisson過(guò)程的速率是變化的。速率的取值,見(jiàn)表格λn列。由于篇幅限制,這個(gè)仿真系統(tǒng)的細(xì)節(jié)和實(shí)驗(yàn)數(shù)據(jù)的取得詳見(jiàn)。我們給出以下試驗(yàn)結(jié)果:其中表1給出給出UR情形下的績(jī)效結(jié)果,