第25卷第4期　青岛大学学报(工程技术版)　Vol.25No.4　2010年12月JOURNAL OF QING DAO UNIVERSIT Y (E &T)Dec.2010文章编号:1006-9798(2010)04-0057-04集装箱码头泊位调度问题的启发式算法研究张海滨,张纪会,宣金钊(青岛大学复杂性科学研究所,山东青岛266071)摘要:为优化集装箱码头泊位的分配,提高泊位的利用率,把码头泊位的调度问题转化为带有约束条件的特殊二维装箱问题。

通过建立连续泊位调度的非线性规划模型,提出了一种求解集装箱码头连续泊位分配问题启发式算法。

仿真算例结果表明该算法能在实际的集装箱码头泊位调度中有效的提高泊位的利用率。

关键词:泊位分配;装箱问题;启发式算法中图分类号:U692.4文献标识码:A收稿日期:2010-09-11基金项目:国家自然科学基金项目(70671057);山东省自然科学基金项目(ZR2010GM006)作者简介:张海滨(1982-),男,硕士研究生,主要从事集装箱码头泊位调度的研究。

泊位作为港口运输中一种重要的资源,是影响港口发展的关键因素之一。

随着港口之间的竞争越来越激烈,如何最大限度提高泊位的利用率、加快船舶的装卸速度,提高港口作业效率和服务水平,是增强港口竞争力的关键因素之一。

因此,泊位调度问题成为港口运输中研究的一项重点内容之一。

泊位分配问题根据泊位的特点分为离散泊位分配和连续泊位分配,根据作业特点分为静态泊位分配和动态泊位分配。

泊位分配问题作为N P 难问题,可以视为指派问题或者划分问题[1];Lai 等[2]提出了以先到先服务为准则的动态泊位调度的启发式算法;Imai [3-5]提出了一种离散泊位下静态和动态泊位分配的启发式算法;Cordeau 等[6]利用禁忌搜索方法对动态泊位分配问题进行了求解;K im 等[7]建立了惩罚策略下的最小费用泊位动态分配模型,并利用模拟退火算法进行了求解;Monaco 等[8]通过考虑船舶总的在港时间,建立了一种连续泊位动态分配模型并进行求解;Hansen 等[9]基于在港时间和在港费用综合考虑建立了相应的模型,并进行了仿真求解。

本文仅考虑泊位一种因素,建立了连续的动态泊位分配优化模型,提出了一种启发式算法可以求得模型的近似最优解。

1　以利用率最高为目标的泊位调度模型泊位调度问题实际是如何安排船舶靠泊的时间和靠泊位置,使某一时间内港口泊位的利用率最高。

实际上泊位的划分主要是逻辑划分而非物理划分。

目前国际上的集装箱运输都是采用班轮运输方式,因此,为建立模型作如下假设:模型中的泊位是连续的,进入待泊区域的集装箱船舶都可以进入泊位作业区域进行作业;根据集装箱采取班轮运输的特点,假设船舶的作业时间由所在目的港装卸箱子的数量决定,与船舶的靠泊位置无关;假设船舶都能按照预计时间到达目的港,可以根据船舶的预计到达时间对船舶进行分配靠泊位置。

建立x -y 直角坐标系,x 轴表示作业时间,y 轴表示离散泊位长度。

则连续泊位调度的模型可以描述为:1)　某一时间段内通过合理安排船舶靠泊作业顺序和作业位置使泊位的利用率最大,其模型为max F =∑j ∈Vl j t nj/S (1)式中,l j 表示船舶j 安全作业需要的泊位长度(其中包括船舶的长度和船舶安全作业之间的距离);t nj 表示船青岛大学学报(工程技术版)第25卷舶j 作业需要的时间;S 表示二维坐标下某一时间内船舶靠泊作业所占的面积(泊位长度和时间的乘积),V 表示等待靠泊船舶的集合。

2)任意时刻所有正在作业船舶占用泊位的长度不超过连续泊位的总长度,其模型为s.t.∑j ∈Vl jX tj≤L ,　Πt ∈T (2)3)相同位置同一时刻只能允许一艘船舶靠泊作业,也就是船舶不能重叠作业,其模型为Z x ij +Z x ji +Z y ij +Z yji ≥1,　Πi ,j ∈V(3)式(2)和(3)中,X tj ,Z x ij 和Z yij 为0～1决策变量。

决策变量X tj =1,表示t 时刻船j 正在装卸作业,否则,X tj =0;Z xij =1,表示船i 靠泊的位置在船j 靠泊位置的左边,否则,Z xij =0;Z yij =1,表示船i 比船j 的靠泊时间早,否则,Z y ij =0。

4)船舶到达港口后才能进入泊位作业,其模型为t bj >t aj ,　Πj ∈V(4)式中,t aj ,t bj 分别表示船舶j 的到达及开始作业的时刻。

5)船j 的吃水要小于泊位允许最大吃水,其模型为d j ≤D(5)式中,d j 表示船舶j 的吃水;D 表示泊位允许的最大吃水。

6)表示船j 等待泊位的时间不能超过C 个小时,其模型为(b j -a j )≤C ,　Πj ∈V ,C >0(6)式中,C 为常数。

2　将泊位调度模型转化为二维装箱模型图1　模型中的船舶作业示意图 根据船舶靠泊作业的特点,把船舶作业过程转化为特殊二维矩形装箱模型,如图1所示。

目标函数就变为把待装物品转入箱子,使箱子被占用的面积最小。

把连续泊位的长L 视为矩形箱子的宽W ,时间T 看做箱子的高。

根据装箱模型,把待靠泊的船舶看做小矩形物品,这里船j 占用泊位的长度l i 看做小矩形物品i 的宽W i ,所需作业时间t ni 看做为矩形的高h i ;矩形箱子的宽为W ,高为H 。

在装箱过程中,待装矩形物块直角放入且不能进行旋转。

3　模型求解把靠泊船舶看作矩形物品集合P ={B 1,B 2,…,B n },将P 中的元素按照3.2中的算法描述进行排放,使矩形箱子内浪费的空间最小。

3.1　约束条件1)　B i ,B j 互不重叠,i ≠j ,i ,j =1,2,…,n 。

2)　B i 必须放在P 内,只能放一次,且在放置的过程中,B i 不能进行翻转,i =1,2,…,n 。

3)　排列过程利用一刀切分层[10]思想对剩余区域进行确定,对矩形物品进行分层放置。

所谓“一刀切”思想是指在工业生产中,对原料进行切割时每切一刀必须把原来的一个矩形分成两个,切割分为横切和竖切,这里采用的是横切(如图1所示),沿着B 1的上边界横切,剩余空间分成S 1和S 2两部分。

4)　在排列过程中,所有船舶的等待时间不能超过C 小时,当出现某一物品必须放在某一层时,选择高度差最小的位置放置该物品。

3.2　算法描述1)　根据初始化相关参数,把等待和预计到达的船舶看做是装箱的物品,对已经到达和预计到达港口的85　第4期 张海滨,等:集装箱码头泊位调度问题的启发式算法研究船舶按照到达时间先后顺序进行编号。

2)　根据船舶在港装卸货物需要时间长短进行排列,即对装矩形箱子要根据高度由高到低进行排列。

3)　从待装矩形物品集合中选择高度最大的物品(假设为B1)置于箱子的左下角(如图1所示)。

4)　沿着B1上边所在的直线横向切,把剩余的空间分成S1和S2两部分,切线下方S1作为装箱的第一层(如图1所示)。

5)　在剩余的有效集合P中扫描寻找与B1高度差最小的物品;如果高度相差最小的小物品有多个,选择排号最小的物品,假设为B2,把B2放在S1区域内,紧靠B1向右进行排列,继续扫描集合P,寻找与B2高度差最小的物块向右排列,直到无法排入为止。

6)　以上B2边所在的直线横向切,重新扫描集合P,寻找集合P中与B1和B2高度差相差最小的物品,在B2的上方靠右排列,重复以上过程,直到有效集合P中的矩形物块无法装入第一层为止。

7)　在排列下一层时,根据船舶预计到达时间看是否能排入该层更新集合P,重复2)～6)步,选择合适的矩形物品放入箱内。

上述过程中,为保证每艘船舶等待时间不超过10h,当确定了每一层的第一艘船舶后,计算所有船舶在下一排排列所需的等待时间,如果出现船舶在下一层排列的等待时间超过10h,就优先考虑把这些船舶放入该层。

同时,在排列的过程中,可以根据船舶预计到达时间看是否能排入某层对集合进行更新。

4　算例分析以青岛前港湾集装箱码头No81,No82,No83为例,泊位长度分别为340,330,330m,吃水均为17m,设计靠泊能力均为100000dwt。

由于它们最大吃水和靠泊能力相同,故看为连续泊位,假设连续泊位吃水大于所有到港船舶的最大吃水。

取某时刻在港待泊及预计到达的船舶数据,为满足规定的时间格式和便于计算,分配船舶靠泊时间从00:00时刻开始,每艘船舶的等待时间不能超过10h。

船舶数据如表1所示。

表1　靠泊作业船舶的主要初始参数船舶占泊长度/m作业时间/h到港时刻船舶占泊长度/m作业时间/h到港时刻1270617∶35 2120417∶41 3300819∶26 4150320∶08 5115223∶06 6130223∶20 7250523∶24 8160223∶43 9310923∶51 10180223∶53 11120300∶40 12120402∶41 13200503∶47 14210204∶19 15150305∶58 16130206∶16 17230207∶1218190208∶10 19160611∶28 20310812∶42 21240513∶30 22150213∶35 23280614∶46 24180315∶20 25250516∶11 26150318∶28 27290619∶45 28140320∶34 29220421∶24 30200222∶35 31300822∶50 32140223∶39 33200523∶54采用基于先到先服务规则的启发式算法和本文提出的启发式算法对本例进行求解,得到了约束条件下两种不同的泊位分配方案,如图2所示。

取T=24h为界,把数据代入式(1)计算出两个利用率分别为8618%和8911%。

通过多次测试表明,随着时间的延长和泊位长度的增加,采用本文提出的算法能够更加有效的提高泊位的利用率。

95图2　两种不同的泊位分配方案5　结束语通过把集装箱码头泊位分配问题转化为带有约束条件的特殊二维装箱问题,根据二维装箱思想和船舶靠泊作业的实际情况,提出了一种解决集装箱码头连续泊位分配问题的启发式算法。

该算法在船舶时间的约束条件下按照参数标量递减排序、时间分割等优化策略来确定船舶的靠泊时间、靠泊位置。

本文的不足之处是没有考虑船舶到港出现延误的情况,并且提出的算法只能得到近似最优解,但这种思想能够使船舶动态分配过程直观地反映在平面上,提出的算法在应用上具有操作简单、实用性强等优点,同时,其思想对其他类型码头和机场停机分配调度问题有一定的借鉴意义。

最后应指出:本文是在假设所有船舶都能在预计的时间内到达的基础上,只考虑泊位一种因素对集装箱码头泊位调度问题进行讨论的。