集装箱码头出口堆场空间分配问题研究

集装箱码头出口堆场空间分配问题研究

0堆场空间分配堆场空间分配的合理性在很大程度上决定了集装箱码头的运营效率，是箱场计划的核心内容之一。本文主要研究了出口堆场的空间分配问题，即在箱区范围内的箱量分配问题。在文献研究中，如果确定了箱装船的装载顺序，则应注意，在实际装载船之前，货物的序列不确定。在文献中，基于出口码头的空间分配问题，建立了混合单元模型，以最小卡运输距离和场桥移动距离为目标。在文献中，我们研究了输入箱、输出箱和旋转箱混合的堆场空间分配问题，提出了两个阶段的决策模型。在第二阶段，重点是在文献的基础上限制不同箱区域之间的距离，并建立相应的两个阶段的决策模型。根据文献，文献研究了第一阶段模型引入的可能性，并使用了传统计算法进行了求解。文献均采用两阶段法,在首先保证工作量平衡的前提下,再考虑降低集卡的运输距离,使集卡运输距离的改善空间受到很大限制.由于码头作业过程复杂,装船效率受到各种因素的共同影响,出口箱堆存空间分配时,必须综合考虑这些因素,是典型的多目标优化问题.本文针对该问题建立了多目标整数规划模型,并利用改进的线性功效系数法对模型进行求解.1堆场期的确定在码头实际运行中出口堆场空间分配主要考虑两个目标,一个是尽量减少出口箱堆放位置与相应船舶泊位间的距离,以节省装船时集卡的运输时间;另一个是尽量使堆场中各箱区的工作量在各时段保持均衡,避免场桥忙闲不一,充分发挥其装卸效能.本文采用滚动计划的方法,从实际需求出发,确定以3d为一个计划期,以4h为一个时段.在实施时只有第一天的计划被实际执行,而后根据最新数据制定下一个计划期的计划,并覆盖掉前一计划期中后两天的计划.需要说明,制定计划时个别船舶的抵港时间尚无法确定,为体现这部分信息不完整的箱量对堆存空间造成的影响,本文按计划期开始时各箱区可用空间的比例,将其预分配到各箱区中.1.1符号表明1船集港箱量的估计T——计划期内的总时段数;B——出口箱区数;L——计划期内的船舶数;Ci——箱区i的容量;Gjt——在t时段内船j的预计集港箱量;Ljt——在t时段内船j的预计装船箱量;xij0——初始时刻箱区i中船j的出口箱量;αit——t时段放入箱区i的信息不完整箱量;dij——箱区i与船j的泊位间的运输距离;bj——船j所能分配的最大箱区数;2系装船箱量的影响xijt——t时段放入箱区i的船j的箱量;yijt——t时段从箱区i装船的船j的箱量;δij——δij=1表示船j有出口箱放入箱区i,否则δij=0.1.2多目标规划模型目标函数为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)为便于计算,将目标函数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+(非负整数),δij∈{0,1}(14)约束式(5)和式(6)保证t时段船j的预计集港箱量和预计装船箱量分别等于其分配到各箱区中的箱量之和;约束式(7)保证在任何时段船j从箱区i装船的箱量不超过该箱区中所堆存的箱量;约束(8)为箱区的容量约束;约束式(9)和式(10)用于建立变量δij和xijt之间的关系;约束式(11)保证船j出口箱在堆场中的分布范围不超过bj个箱区;约束式(12)和式(13)是目标2线性化所需约束.2多目标函数上界与其它方法相比,功效系数法特别适用于处理不同量纲的多目标规划问题.模型(LIP)中目标1的量纲是距离,而目标2的量纲是箱量,且两者的取值范围相差较大.因此,本文采用一种改进的线性功效系数法对两个目标进行处理.设X为模型(LIP)的解向量,D为X的可行域,f1=f1(X)=B∑i=1L∑j=1dij(xij0+Τ∑t=1xijt),f2=f2(X)=Τ∑t=1(Μt-Νt).按照传统线性功效系数法,需要得到f1和f2的上界ˉf1=ΜaxX∈DB∑i=1L∑j=1dij(xij0+Τ∑t=1xijt)ˉf2=ΜaxX∈DΤ∑t=1(Μt-Νt)若以约束式(5)～式(14)构成的解空间作为可行域D,求解ΜaxX∈DΤ∑t=1(Μt-Νt),将产生无界解(即ˉf2=+∞).因为约束式(5)～式(14)无法限制Mt的上界和Nt的下界,本文对线性功效系数法中目标函数上界的取法进行改进.取f1和f2下界分别为f-1=ΜinX∈DB∑i=1L∑j=1dij(xij0+Τ∑t=1xijt)(15)f-2=ΜinX∈DΤ∑t=1(Μt-Νt)(16)设X′为f1对应的解,X″为f2对应的解,则定义f1和f2的上界分别为ˉf1=f1(X″)(17)ˉf2=f2(X′)(18)取f1和f2的功效系数分别为d1=(ˉf1-f1)/(ˉf1-f-1)和d2=(ˉf2-f2)/(ˉf2-f-2),并以ΜaxX∈Du=2∏j=1dj为目标对问题进行求解.由于改变了上界ˉf1和ˉf2的取法,在原问题的可行域D内,可能存在解˜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的最优解不一定是原问题的有效解.性质1问题(LIP)的任何有效解X*对应的目标函数值f1(X*)≤ˉf1‚f2(X*)≤ˉf2.证明略.于是,可在模型中引入附加约束B∑i=1L∑j=1dij(xij0+Τ∑t=1xijt)≤ˉf1(19)Τ∑t=1(Μt-Νt)≤ˉf2(20)由性质1,加入附加约束式(19)和式(20)后,可行解空间不会丢失原问题的任何有效解.于是可将多目标模型(LIP)化为如下单目标模型(SP)如下.ΜaxX∈D′u=2∏j=1dj(21)其中D′为约束式(5)～式(14)及式(19)、式(20)构成的解空间.下面说明上述方法所得模型(SP)的最优解与原问题有效解的关系,为此引入如下定理.定理1设ΜinX∈Df(X)=(f1(X)f2(X)⋯fp(X))Τ为原问题,假设∀X∈D,有dj(fj)>0(j=1,2,…,p),而且当j=1,2,…,k时,∀X∈D,dj(fj)单减;当j=k+1,k+2,…,p时,∀X∈D,dj(fj)单增,则ΜaxX∈Du=p∏j=1dj(fj)的任一最优解为原问题的有效解.由附加约束式(19)和式(20),模型(SP)中d1∈,d2∈,因此d1d2≥0,即ΜinX∈D′u≥0.而通常ΜaxX∈D′u>ΜinX∈D′u,所以u(X*)=ΜaxX∈D′u>0,即模型(SP)的最优解X*对应的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)均单调减少,由定理1,模型(SP)的最优解X*是原问题的有效解.3与港区实际计划比较为验证本文方法的有效性和实用性,作者利用从天津港某集装箱码头实际采集得到的一个月(28个计划期)的数据对上述方法进行测试,并将结果与码头实际计划进行比较.实验使用lingo8.0对两个目标的下界及模型(SP)进行求解,所得结果均在Pentium4,2.8GHz,CPU及512MB内存平台下测得.表1给出了本文方法所得方案与码头实际计划在两项指标上的比较.其中f*1和f*2分别是本文方法所得方案对应的集装箱运输距离和工作量不平衡程度,f1和f2是实际计划得到的相应指标,GAP1=(f1-f*1)/f1和GAP2=(f2-f*2)/f2分别表示本文方法所得目标值f1和f2相对实际计划的改善程度.可以看出,本文方法所得方案比码头实际计划在两项指标上均有明显改善,其中集装箱运输距离平均减少26.51%,而工作量不平衡程度平均降低36.05%.表中time为本文方法的计算时间,所有计划期time均不超过35min,相对三天的计划期来说,该方法在计算时间上具有良好的实用性.表2给出了本文方法所得方案与码头实际计