集裝箱碼頭出口堆場(chǎng)空間分配問(wèn)題研究

集裝箱碼頭出口堆場(chǎng)空間分配問(wèn)題研究

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