基于滚动计划的堆场出口箱存储位置分配两阶段模型

刘婵娟,胡志华

基于滚动计划的堆场出口箱存储位置分配两阶段模型

刘婵娟,胡志华

(上海海事大学物流研究中心,上海201306)

考虑出口箱进场时间的随机性,将集装箱堆场出口箱箱位分配问题分为两个阶段进行研究:①在滚动计划的基础上,以最小化场内集卡运输距离为目标建立整数规划模型,对到场出口箱进行箱区分配;②以取箱装船过程中贝位内翻箱数最小和平衡贝位内各堆栈箱数为目标,建立堆场出口箱具体箱位分配的多目标优化模型.应用Matlab软件中Yalmip工具箱编程求解,通过数值实验验证了模型的有效性.实验结果表明,该方法能够有效解决堆场出口箱箱位分配问题,减小堆场设备作业量,并通过减少翻箱操作提高码头作业效率.

堆场位置分配;出口箱;滚动计划;多目标混合整数规划

在集装箱码头堆场中,出口箱的装载顺序对船舶运输效益会产生影响.在堆放集装箱时,配载人员通常尽可能地在保持船舶稳定前提下,减少起重机和堆场设备的作业量,且要满足集装箱的目的港以及大小等位置分配的要求.为了得到有效的装载顺序,出口箱必须被分配在适当的位置,因此针对集装箱堆场出口箱的存储空间分配问题,国内外专家们提出了不同的解决方法和策略.

Talebibrahimi等[1-2]分析了堆场存储空间的固定需求,提出了针对临时箱存储空间分配的策略,但其研究主要针对分配给每艘船舶的空间大小,而没有考虑到场集装箱具体存储位置的分配;Kang等[3]和Kim等[4-5]均仅以最小化堆场作业时翻箱量为目标来进行堆场箱位分配;Preston等[6]和Bazzazi等[7]运用遗传算法求解了堆场出口箱箱位分配问题,但是Bazzazi等[7]在应用遗传算法来确定出口箱存储位置时,并没有考虑出口集装箱到场的随机性;另外,还有学者采用两阶段法进行堆场出口箱箱位分配[8-11].但是,以上研究均没有考虑堆场作业现实操作中昼夜不停的连续作业特性.

Park等[12]采用滚动计划周期的方法对堆场作业的计划周期进行模拟,以计划周期内各个箱区之间的作业量不均衡最小化为目标函数,建立整数规划模型,对进入堆场的集装箱进行箱位分配.李建忠等[13]从平衡箱区贝位箱量和最小化集卡行驶距离入手,在滚动计划的基础上建立了集装箱堆场空间动态配置模型.该模型的主要目的是提高集卡作业效率,降低装船作业过程中堆场机械耗费成本.Kim等[14]针对集装箱堆场存储空间分配问题,以提高空间利用率和堆场集装箱装卸效率为目标,建立了基于滚动计划的混合整数规划模型,并设计了基于集装箱在场时间和次梯度优化技术的启发式算法进行求解.但是,该模型和算法只解决了集装箱到场后的箱区分配问题,并未给出到场集装箱具体位置分配方法.

基于Kim等[14]的研究,本工作考虑出口箱进场时间的随机性,将堆场出口箱箱位分配问题分两个阶段进行研究:①在滚动计划的基础上,以最小化场内集卡运输距离为目标建立整数规划模型,对到场出口箱进行箱区贝位分配;②以取箱装船过程中贝位内翻箱数最小和平衡贝位内各堆栈箱数为目标,建立堆场出口箱箱位分配的多目标优化模型来进行具体的箱位分配.最后,本工作通过数值实验验证了模型的有效性.与已有研究相比,本工作的贡献主要在于考虑了现实操作中堆场作业昼夜不停的连续作业特性,在使翻箱操作量最小和集卡运输距离最短的同时,使贝位内各堆栈中的箱数达到均衡,这既可以减少起重机工作量,又能防止堆栈过高而发生倾倒,从而提高堆场作业的安全性.

1 问题描述与假设

现代集装箱码头作业系统主要包括堆场作业、集卡作业和前方泊位作业系统,其中堆场作业系统的任务有进口及转运集装箱卸载后的箱位安排问题、出口集装箱到场的箱位安排、空箱到场的堆垛策略以及堆场各设备的协同作业配置计划等(见图1).本工作主要研究堆场作业系统中出口箱到场后的箱位安排问题.

由于堆场作业是昼夜不停的连续作业,因此采用滚动计划的方法对堆场作业的计划周期进行模拟.考虑到在实际生产作业中,出口箱到场的提前期通常为1～3 d,故选取3 d为一个计划周期,每天分2个计划阶段,故一个计划期共有6个阶段,其中每个计划阶段12 h.在实际生产时,仅根据计划期首日制定的计划完成当天的生产,计划期次日的生产根据下一计划期首日信息与本计划期现有信息综合决定.依此类推,滚动进行每天生产计划的制定.滚动计划周期示意图如图2所示.

堆场空间资源配置优化的目的是:①减少船舶在港停留时间以提高港口生产效率;②使港口设备利用率最大化以降低港口运营成本.本工作采用两阶段分析方法,将堆场出口箱存储空间配置问题分为两个阶段:①为了提高堆场设备利用率和降低场内集卡运输成本,在平衡各箱区贝位作业量的约束下将集装箱分配到各个箱区贝位中;②以取箱装船过程中贝位内翻箱数最小和各堆栈箱数均衡为目标建立多目标规划模型进行具体箱位分配(见图3).

图1 集装箱堆场作业系统Fig.1 Container yard operation system

图2 滚动计划周期示意图Fig.2 Illustration of the rolling plan schedule

2 模型建立

2.1 箱区分配模型M1

2.1.1 符号说明

(1)集合.I为计划初期需要被分配存储空间的船舶集合,I={1,2,···,NI},NI为待装船舶总数,通过i∈I索引;J为滚动计划周期阶段数,J={1,2,···,NJ},NJ为计划周期内计划阶段总数,通过j∈J索引;M 为堆场箱区集合,M={1,2,···,NM},NM为堆场箱区总数,通过m∈M索引.

(2)参数.Cm为箱区m的最大堆存容量;mi为能分配给船舶i的最大箱区数;B为一个很大正整数;dij为j阶段到达堆场的i船集装箱数;xm0i为开始时刻,m箱区中已有的i船集装箱数;c1为场内集卡运输一个集装箱的单位距离运输成本;tmi为从泊位i到箱区m的运输距离.

(3)变量.xmji为j阶段到达堆场的i船集装箱被分配到m箱区中的数量;在m箱区中有i船集装箱时,设变量δmi等于1,否则等于0.

图3 堆场出口箱存储空间配置方案Fig.3 Storage space allocation scheme for export containers in the yard

2.1.2 模型

第一阶段模型M1的目标是使场内集卡的总运输成本最低,其目标函数如式(1)所示.式(2)～(6)是约束条件,其中式(2)表示任一箱区中堆存的集装箱数不能超过箱区最大容量;式(3)表示任一阶段所有箱区中放入的集装箱数之和等于该阶段到达堆场的集装箱总数;式(4)表示任一阶段放入m箱区的i船集装箱数大于等于0;式(5)表示在一个计划周期结束后,如m箱区中有i船集装箱,则δmi等于1,否则等于0;式(6)表示i船集装箱所占的箱区数不能超过规定的最大值.

2.2 贝位及具体箱位选择模型M2

2.2.1 符号说明

(1)集合.I={1,2,···,NI}为所有出口集装箱的集合,NI为到场集装箱总数,通过i,j∈I索引;B={1,2,···,NB}为箱区内贝位集合,NB为箱区内贝位总数,通过b∈B索引;R={1,2,···,NR}为贝位内列数的集合,NR为贝位内总列数,通过r∈R索引;T={1,2,···,NT}为贝位内层数的集合,NT为贝位内总层数,通过t∈T索引.

(2)参数.Ei,j表示贝位内满足时间先后顺序先到先堆存(early arrive early stack,EAES)原则的箱子,当集装箱i和j的放置满足时间先后顺序时Ei,j取1,否则取0;Wi,j表示贝位内满足重箱在上原则(light below heavy,LBH)约束原则的箱子数,当集装箱i和j的放置满足重量约束时Wi,j取1,否则取0;Ob,r,t表示贝位内已被占用的箱位;Cb表示b贝位内的集装箱在取箱装船过程中集卡运输成本,该成本与贝位离岸边的距离成正比,Cb∈{1,2,···,B},通过b∈B索引.

(3)决策变量.xi,b,r,t∈{0,1},如集装箱i被放置在b贝r列t层的位置时,xi,b,r,t的值为1,否则为0;yi,j,b,r,t1,t2∈{0,1},如集装箱i和j被分配到(b,r,t1)和(b,r,t2)两个箱位时足时间先后顺序EAES约束原则时zwi,j,b,r,t1,t2的值为1,否则为0.

2.2.2 模型

在第二阶段进行贝位和具体箱位选择时,本工作建立了多目标混合整数优化模型M2.

M2的目标函数如式(7)所示,式(7)表示最小化贝位内翻箱操作数、最小化场内集卡运输距离和使贝位内各堆栈中箱数均衡.式(8)中frehandle为翻箱操作数,式(9)中fw为不满足重量约束原则的箱数,式(10)中fe为不满足时间先后顺序原则的箱数,式(11)中fb为存储在贝位中集装箱在取箱装船过程中的运输成本,式(12)中fh为堆栈堆存高度.式(13)～(21)是约束条件,其中式(13)表示一个集装箱只能占用一个箱位,式(14)表示一个箱位只能放一个箱子,式(15)表示某一贝位内堆存集装箱总数不能超过贝内箱位数,这里假定每贝由6列4层构成,且有3个缓冲箱位,则贝内可堆存集装箱数最多为21个.式(16)表示决策变量yi1,i2,b,r,t1,t2和xi,b,r,t之间的关系,只有当i1和i2集装箱分别分配给箱位(b,r,t1)和(b,r,t2)时,决策变量yi1,i2,b,r,t1,t2的值为1,否则为0,式(17)表示箱子不能悬空放置.式(18)和(19)表

在模型M2的基础上,提出模型M3和M4对该问题进行优化.

M3是对目标函数fh的最小值进行求解,使贝位内各堆栈箱数尽量均衡,避免堆存过高;M4是将目标函数fh和fb作为一个整体进行优化.该过程分为两个阶段:①根据M3求出目标函数fh的最小值,令其等于fh∗;②是对目标函数fb优化,其中α是目标函数fh的松弛系数.

3 算例

为了验证本工作提出的基于滚动计划的堆场出口箱箱位分配两阶段模型的正确性和有效性,运用Matlab中的Yalmip工具箱包含的线性规划求解算法,输入统一的建模语言,得到M1的最优箱区分配方案和M2的最优具体箱位分配方案.

算例1 运用模型M1对集装箱堆场出口箱进行箱区优化配置.假定一个计划周期为3 d,每天分为2个阶段,则一个计划周期共6个阶段;待装船舶数NI为3,箱区数为5,每个箱区的最大容量为42.为了使同一船舶的集装箱能够尽可能地集中堆存,故分配给每艘船舶的最大箱区数均为2.场内集卡运输单个集装箱的单位运输成本为1,其余输入参数如表1和2所示.所得场内集卡运输成本为440,箱区分配结果如图(4)～(6)所示.

表1 j阶段到达堆场的i船集装箱数djiTable 1 Container number djiof ship i arriving at the yard at stage j

表2 m箱区到i船的距离tmiTable 2 Distance tmifrom block m to ship i

图4 船舶1的集装箱箱区分配Fig.4 Block distributions of containers on ship 1

图5 船舶2的集装箱箱区分配Fig.5 Block distributions of containers on ship 2

图6 船舶3的集装箱箱区分配Fig.6 Block distributions of containers on ship 3

算例2 运用模型M2对集装箱堆场出口箱进行具体箱位分配.本工作以实际最常见的每贝6列4层堆场为例,假定每个贝位中有3个箱位为缓冲箱位,以每个箱区有2个贝位,24个集装箱的存储任务为基本算例,验证模型M2的实用性.24个出口箱随机到场顺序及重量分布如表3所示,所得具体箱位分配方案如图7所示.

表3 24个出口箱的时间顺序和重量分布Table 3 Time sequence and weight distributions of 24 containers

图7 24个集装箱具体箱位分配Fig.7 Specif i c space allocations of 24 containers

4 实验分析

为了进一步分析参数变化对实验结果的影响,本工作设计了4组实验场景,场景描述和不同场景中模型需作的调整如表4所示.

表4 实验目的和配置Table 4 Experimental purposes and settings

基于以上4个实验,对所得结果结合图(8)～(12)进行分析,得出如下结论.

(1)由实验1的结果可知,当箱区容量和每阶段到达堆场的集装箱数以及场内集卡单位运输成本保持不变时,分配给船舶i的箱区数越多,则目标函数值越小,场内集卡运输成本越小(见图8).

图8 模型M1中参数mi对实验结果的影响Fig.8 Inf l uence of parameters mion the results in model M1

(2)由实验2的结果可知,参数Ob,i,t变化对目标函数fw,fe的值并无影响.在算例2中,当有2个贝位时,目标函数fb和fh的值会随着已被占用箱位数的变化而变化.总体上,已被占用的箱位数越多,则目标函数fh的值越大,即堆栈越高.集装箱堆存太高可能引发倒塌,存在安全隐患.此外,贝内堆栈高度分布不均衡将会增加取箱装船过程中场桥移动距离,提高机械作业成本(见图9).

图9 模型M2中参数Ob,i,t对实验结果的影响Fig.9 Inf l uence of parameters Ob,i,ton the results in Model M2

(3)由实验3的结果可知,假如不考虑各堆栈中箱子数均衡原则,即在模型M2中去掉第4个目标函数,则箱位分配方案会发生改变(见图10).两种分配方式所得目标函数fb,fh的值如图11所示.由实验结果可知,在考虑各堆栈箱数均衡原则的情况下,集装箱存储成本较高,为34;而不考虑各堆栈箱数均衡原则的情况下,堆存成本只有31.相反,在考虑各堆栈箱数均衡原则的情况下,目标函数fh的值仅为118,在不考虑各堆栈箱数均衡原则的情况下fh的值为168.在考虑各堆栈箱数均衡原则的情况下,集装箱明显堆存于较低层.这样不但提高了堆栈的安全性,而且有利于在取箱装船过程中减少场桥上下移动距离,降低机械作业成本.

图10 不考虑堆栈中箱数均衡原则时24个集装箱箱位分配Fig.10 Specif i c space allocation of 24 containers not considering the number equilibrium in each stack

(4)以算例2中24个集装箱数据为例,根据模型M3和M4对目标函数fh和fb进行均衡分析.结合图12可知,当fh的松弛系数α值在0.8到2.4之间时,存储成本fb的值几乎呈线性减小;而当fh的值大于2.4时,存储成本fb的值保持为20,不再改变.当fb在34～20之间时,两个目标可以同时优化.

图11 两种不同分配方式所得fb和fh的值Fig.11 Values of fband fhin two dif f erent distribution ways

图12 fh和fb之间的均衡分析Fig.12 Tradeof fanalysis between fhand fb

5 结束语

在滚动计划的基础上,以最小化场内集卡运输成本和最小化翻箱操作数为目标,建立了集装箱堆场出口箱箱位分配的两阶段整数规划模型,并通过不同算例分析,验证了模型的有效性,结果显示本模型能够在优化场内集卡水平运输距离的同时,平衡各箱区作业量且尽可能减少翻箱操作量.对集装箱码头堆场出口箱区的存储位置分配问题有一定的借鉴意义.但是,在实际生产过程中由于各个堆场作业计划周期不同,堆场作业设备数量不同,以及出口箱到场的随机性等因素,都将不同程度增大出口箱箱位分配的难度.因此,在以后的工作中可融入出口箱到场的随机性因素,以进一步增强集装箱码头堆场出口箱存储位置分配的准确性,提高堆场作业的效率.

[1]TALEbIbRAHIMI D C M.Modeling and analysis of container storage in ports[J].Journal of Clinical Microbiology,1989,47(12):4144-4145.

[2]TALEbIbRAHIMI D C M,CASTILHO B D,DAGANZO C F.Storage space vs.handling work in container terminals[J].Transportation Research Part B Methodological,1993,27(1):13-32.

[3]KANG J K R,KIM R K H.Deriving stacking strategies for export containers with uncertain weight information[J].Intelligent Manufacturing,2006,17:399-410.

[4]KIM K H.Evaluation of the number of rehandlings in the container yards[J].Computers and Industrial Engineering,1997,32(4):701-711.

[5]KIM K H,PARk Y M,RYU K R.Deriving decision rules to locate export containers in container yards[J].European Journal of Operational Research,2000,124(1):80-101.

[6]PRESTON P,KOZAN E.An approach to determine storage locations of containers at seaport terminal[J].Computers and Operations Research,2001,28(10):983-995.

[7]BAZZAZI M,SAFAEI N.A genetic algorithm to solve the storage space allocation problem in a container terminal[J].Computers and Industrial Engineering,2009,56(1):44-52.

[8]CHEN L,LU Z.The storage location assignment problem for outbound containers in a maritime terminal[J].International Production Economics,2012,135:73-80.

[9]HU W,WANG H,MIN Z.A storage allocation algorithm for outbound containers based on the outer-inner cellular automation[J].Information Sciences,2014,281:147-171.

[10]ZHANG C,LIU J,WAN Y W,et al.Storage space allocation in container terminals[J].Transportation Research Part B,2003,37:883-903.

[11]靳志宏,毛钧,李娜.基于混合动态规划的集装箱堆场贝位内翻箱作业调度优化[J].交通运输系统工程与信息,2011,16(3):131-136.

[12]PARk T,CHOE R,KIM Y H.Dynamic adjustment of container stacking policy in an automated container terminal[J].International Journal of Production Economics,2011,133(25):385-392.

[13]李建忠,丁以中,王斌.集装箱堆场空间动态配置模型[J].交通运输工程学报,2007,3(7):50-55.

[14]KIM K H,PARk K T.A note on a dynamic space-allocation method for outbound containers[J].European Journal of Operational Research,2003,148:92-101.

Two-stage model for outbound containers’space allocation assignment using rolling horizon method

LIU Chanjuan,HU Zhihua
(Logistics Research Center,Shanghai Maritime University,Shanghai 201306,China)

This paper addresses storage location assignment for outbound containers.Considering randomness of the containers’approach time,this study divides the problem into two phases.The f i rst is distribution of blocks and bays for containers based on a rolling plane.The second is to propose a multi-objective optimization model to minimize reshuffling and balance the number of each stack.The Yalmip toolbox of Matlab is used to solve the problem.Experimental results show that proposed method can ef f ectively solve the space allocation problem for outbound containers,and reduce the amount of yard equipment operations.Efficiency of the terminal operation is signif i cantly improved by reducing reshuffling.

yard space allocation;outbound container;rolling horizon method;multiobjective mixed integer programming

U 691.3

A

1007-2861(2017)05-0789-12

10.12066/j.issn.1007-2861.1741

2016-02-19

国家自然科学基金面上资助项目(71471109);国家自然科学基金青年资助项目(71101088);教育部博士点基金资助项目(20113121120002);交通部应用基础研究资助项目(2015329810260);上海市教委科研创新资助项目(14YZ100);上海市曙光计划资助项目(13SG48)

胡志华(1977—),男,教授,博士,研究方向为港航与物流运作优化、社会科学计算实验和计算智能.

E-mail:zhhu@shmtu.edu.cn