集裝箱碼頭出口堆場空間分配問題研究

集裝箱碼頭出口堆場空間分配問題研究

0堆場空間分配堆場空間分配的合理性在很大程度上決定了集裝箱碼頭的運營效率，是箱場計劃的核心內(nèi)容之一。本文主要研究了出口堆場的空間分配問題，即在箱區(qū)范圍內(nèi)的箱量分配問題。在文獻(xiàn)研究中，如果確定了箱裝船的裝載順序，則應(yīng)注意，在實際裝載船之前，貨物的序列不確定。在文獻(xiàn)中，基于出口碼頭的空間分配問題，建立了混合單元模型，以最小卡運輸距離和場橋移動距離為目標(biāo)。在文獻(xiàn)中，我們研究了輸入箱、輸出箱和旋轉(zhuǎn)箱混合的堆場空間分配問題，提出了兩個階段的決策模型。在第二階段，重點是在文獻(xiàn)的基礎(chǔ)上限制不同箱區(qū)域之間的距離，并建立相應(yīng)的兩個階段的決策模型。根據(jù)文獻(xiàn)，文獻(xiàn)研究了第一階段模型引入的可能性，并使用了傳統(tǒng)計算法進(jìn)行了求解。文獻(xiàn)均采用兩階段法,在首先保證工作量平衡的前提下,再考慮降低集卡的運輸距離,使集卡運輸距離的改善空間受到很大限制.由于碼頭作業(yè)過程復(fù)雜,裝船效率受到各種因素的共同影響,出口箱堆存空間分配時,必須綜合考慮這些因素,是典型的多目標(biāo)優(yōu)化問題.本文針對該問題建立了多目標(biāo)整數(shù)規(guī)劃模型,并利用改進(jìn)的線性功效系數(shù)法對模型進(jìn)行求解.1堆場期的確定在碼頭實際運行中出口堆場空間分配主要考慮兩個目標(biāo),一個是盡量減少出口箱堆放位置與相應(yīng)船舶泊位間的距離,以節(jié)省裝船時集卡的運輸時間;另一個是盡量使堆場中各箱區(qū)的工作量在各時段保持均衡,避免場橋忙閑不一,充分發(fā)揮其裝卸效能.本文采用滾動計劃的方法,從實際需求出發(fā),確定以3d為一個計劃期,以4h為一個時段.在實施時只有第一天的計劃被實際執(zhí)行,而后根據(jù)最新數(shù)據(jù)制定下一個計劃期的計劃,并覆蓋掉前一計劃期中后兩天的計劃.需要說明,制定計劃時個別船舶的抵港時間尚無法確定,為體現(xiàn)這部分信息不完整的箱量對堆存空間造成的影響,本文按計劃期開始時各箱區(qū)可用空間的比例,將其預(yù)分配到各箱區(qū)中.1.1符號表明1船集港箱量的估計T——計劃期內(nèi)的總時段數(shù);B——出口箱區(qū)數(shù);L——計劃期內(nèi)的船舶數(shù);Ci——箱區(qū)i的容量;Gjt——在t時段內(nèi)船j的預(yù)計集港箱量;Ljt——在t時段內(nèi)船j的預(yù)計裝船箱量;xij0——初始時刻箱區(qū)i中船j的出口箱量;αit——t時段放入箱區(qū)i的信息不完整箱量;dij——箱區(qū)i與船j的泊位間的運輸距離;bj——船j所能分配的最大箱區(qū)數(shù);2系裝船箱量的影響xijt——t時段放入箱區(qū)i的船j的箱量;yijt——t時段從箱區(qū)i裝船的船j的箱量;δij——δij=1表示船j有出口箱放入箱區(qū)i,否則δij=0.1.2多目標(biāo)規(guī)劃模型目標(biāo)函數(shù)為1信度計算ΜinB∑i=1L∑j=1dij(xij0+Τ∑t=1xijt)(1)Min∑i=1B∑j=1Ldij(xij0+∑t=1Txijt)(1)2船集箱量的估計約束ΜinΤ∑t=1(Μax1≤i≤BL∑j=1(xijt+yijt)-Μin1≤i≤BL∑j=1(xijt+yijt))(2)Min∑t=1T(Max1≤i≤B∑j=1L(xijt+yijt)?Min1≤i≤B∑j=1L(xijt+yijt))(2)為便于計算,將目標(biāo)函數(shù)2線性化,定義Μt=Μax1≤i≤BL∑j=1(xijt+yijt),Νt=Μin1≤i≤BL∑j=1(xijt+yijt).于是可得模型(LIP)如下.ΜinB∑i=1L∑j=1dij(xij0+Τ∑t=1xijt)(3)ΜinΤ∑i=1(Μt-Νt)(4)s.t.B∑i=1xijt=Gjt;j=1,2,…,L;t=1,2,…,T(5)B∑i=1yijt=Ljt;j=1,2,…,L;t=1,2,…,T(6)yijt≤t-1∑s=1(xijs-yijs)+xij0,i=1,2,?,B,j=1,2,?,L;t=1,2,?,Τ(7)L∑j=1(xij0+t∑k=1(xijk-yijk))+t∑k=1αik≤Ci,i=1,2,?,B,t=1,2,?,Τ(8)δij≥1Ct(xij0+Τ∑t=1xijt),i=1,2,?,B;j=1,2,?,L(9)δij≤xij0+Τ∑t=1xijt,i=1,2,?,B,j=1,2,?,L(10)B∑i=1δij≤bj,j=1,2,?,L(11)L∑j=1(xijt+yijt)≤Μt,i=1,2,?,B,t=1,2,?,Τ(12)L∑j=1(xijt+yijt)≥Νt,i=1,2,…,B;t=1,2,…,T(13)xijt,yijt∈Z+(非負(fù)整數(shù)),δij∈{0,1}(14)約束式(5)和式(6)保證t時段船j的預(yù)計集港箱量和預(yù)計裝船箱量分別等于其分配到各箱區(qū)中的箱量之和;約束式(7)保證在任何時段船j從箱區(qū)i裝船的箱量不超過該箱區(qū)中所堆存的箱量;約束(8)為箱區(qū)的容量約束;約束式(9)和式(10)用于建立變量δij和xijt之間的關(guān)系;約束式(11)保證船j出口箱在堆場中的分布范圍不超過bj個箱區(qū);約束式(12)和式(13)是目標(biāo)2線性化所需約束.2多目標(biāo)函數(shù)上界與其它方法相比,功效系數(shù)法特別適用于處理不同量綱的多目標(biāo)規(guī)劃問題.模型(LIP)中目標(biāo)1的量綱是距離,而目標(biāo)2的量綱是箱量,且兩者的取值范圍相差較大.因此,本文采用一種改進(jìn)的線性功效系數(shù)法對兩個目標(biāo)進(jìn)行處理.設(shè)X為模型(LIP)的解向量,D為X的可行域,f1=f1(X)=B∑i=1L∑j=1dij(xij0+Τ∑t=1xijt),f2=f2(X)=Τ∑t=1(Μt-Νt).按照傳統(tǒng)線性功效系數(shù)法,需要得到f1和f2的上界ˉf1=ΜaxX∈DB∑i=1L∑j=1dij(xij0+Τ∑t=1xijt)ˉf2=ΜaxX∈DΤ∑t=1(Μt-Νt)若以約束式(5)～式(14)構(gòu)成的解空間作為可行域D,求解ΜaxX∈DΤ∑t=1(Μt-Νt),將產(chǎn)生無界解(即ˉf2=+∞).因為約束式(5)～式(14)無法限制Mt的上界和Nt的下界,本文對線性功效系數(shù)法中目標(biāo)函數(shù)上界的取法進(jìn)行改進(jìn).取f1和f2下界分別為f-1=ΜinX∈DB∑i=1L∑j=1dij(xij0+Τ∑t=1xijt)(15)f-2=ΜinX∈DΤ∑t=1(Μt-Νt)(16)設(shè)X′為f1對應(yīng)的解,X″為f2對應(yīng)的解,則定義f1和f2的上界分別為ˉf1=f1(X″)(17)ˉf2=f2(X′)(18)取f1和f2的功效系數(shù)分別為d1=(ˉf1-f1)/(ˉf1-f-1)和d2=(ˉf2-f2)/(ˉf2-f-2),并以ΜaxX∈Du=2∏j=1dj為目標(biāo)對問題進(jìn)行求解.由于改變了上界ˉf1和ˉf2的取法,在原問題的可行域D內(nèi),可能存在解?X,使d1(?X)<0,d2(?X)<0?ΜaxX∈Du=d1(?X)d2(?X)>0.而由d1(?X)<0,可知f1(?X)>ˉf1=f1(X″),又因為f2(?X)≥f-2=f2(X″),則由有效解的定義??X不是原問題的有效解.也就是說,以式(17)和式(18)作為f1和f2的上界時,ΜaxX∈Du的最優(yōu)解不一定是原問題的有效解.性質(zhì)1問題(LIP)的任何有效解X*對應(yīng)的目標(biāo)函數(shù)值f1(X*)≤ˉf1?f2(X*)≤ˉf2.證明略.于是,可在模型中引入附加約束B∑i=1L∑j=1dij(xij0+Τ∑t=1xijt)≤ˉf1(19)Τ∑t=1(Μt-Νt)≤ˉf2(20)由性質(zhì)1,加入附加約束式(19)和式(20)后,可行解空間不會丟失原問題的任何有效解.于是可將多目標(biāo)模型(LIP)化為如下單目標(biāo)模型(SP)如下.ΜaxX∈D′u=2∏j=1dj(21)其中D′為約束式(5)～式(14)及式(19)、式(20)構(gòu)成的解空間.下面說明上述方法所得模型(SP)的最優(yōu)解與原問題有效解的關(guān)系,為此引入如下定理.定理1設(shè)ΜinX∈Df(X)=(f1(X)f2(X)?fp(X))Τ為原問題,假設(shè)?X∈D,有dj(fj)>0(j=1,2,…,p),而且當(dāng)j=1,2,…,k時,?X∈D,dj(fj)單減;當(dāng)j=k+1,k+2,…,p時,?X∈D,dj(fj)單增,則ΜaxX∈Du=p∏j=1dj(fj)的任一最優(yōu)解為原問題的有效解.由附加約束式(19)和式(20),模型(SP)中d1∈,d2∈,因此d1d2≥0,即ΜinX∈D′u≥0.而通常ΜaxX∈D′u>ΜinX∈D′u,所以u(X*)=ΜaxX∈D′u>0,即模型(SP)的最優(yōu)解X*對應(yīng)的d1(X*)>0,d2(X*)>0.因此ΜaxX∈D′u=ΜaxX∈D″u其中D″={X|X∈D′∧d1(X)>0∧d2(X)>0}.又因為d1(f1)和d2(f2)均單調(diào)減少,由定理1,模型(SP)的最優(yōu)解X*是原問題的有效解.3與港區(qū)實際計劃比較為驗證本文方法的有效性和實用性,作者利用從天津港某集裝箱碼頭實際采集得到的一個月(28個計劃期)的數(shù)據(jù)對上述方法進(jìn)行測試,并將結(jié)果與碼頭實際計劃進(jìn)行比較.實驗使用lingo8.0對兩個目標(biāo)的下界及模型(SP)進(jìn)行求解,所得結(jié)果均在Pentium4,2.8GHz,CPU及512MB內(nèi)存平臺下測得.表1給出了本文方法所得方案與碼頭實際計劃在兩項指標(biāo)上的比較.其中f*1和f*2分別是本文方法所得方案對應(yīng)的集裝箱運輸距離和工作量不平衡程度,f1和f2是實際計劃得到的相應(yīng)指標(biāo),GAP1=(f1-f*1)/f1和GAP2=(f2-f*2)/f2分別表示本文方法所得目標(biāo)值f1和f2相對實際計劃的改善程度.可以看出,本文方法所得方案比碼頭實際計劃在兩項指標(biāo)上均有明顯改善,其中集裝箱運輸距離平均減少26.51%,而工作量不平衡程度平均降低36.05%.表中time為本文方法的計算時間,所有計劃期time均不超過35min,相對三天的計劃期來說,該方法在計算時間上具有良好的實用性.表2給出了本文方法所得方案與碼頭實際計