集装箱码头装船贝内发箱顺序决策

宓为建,张晓华,秦 曌,田 婷

(上海海事大学物流工程学院,上海201306)



集装箱码头装船贝内发箱顺序决策

宓为建,张晓华,秦 曌,田 婷

(上海海事大学物流工程学院,上海201306)

随着世界集装箱海运量的不断增加及集装箱船舶的日益大型化,集装箱装卸作业的稳定高效已成为港口经营者关注的重点,所以在装船作业中如何通过优化发箱顺序决策提高装船效率也变得尤为重要.针对集装箱码头装船贝内发箱顺序的决策问题,考虑船舶大型化对于防悬空约束、分舱盖板约束,以翻箱次数最少、移机次数最少和转场次数最少为目标,建立集装箱装船贝内发箱顺序的决策模型.然后设计模型算例,通过对于算例结果的分析验证模型的有效性.相关思路及研究方法对于集装箱码头装船作业时的贝内发箱顺序决策具有借鉴意义,同时,模型的构建方法对于研究同类基于空间布局的组合优化问题具有一定借鉴意义.

集装箱码头; 发箱顺序; 分舱盖板; 移机转场

随着世界集装箱海运量的不断增长及集装箱船舶的日益大型化,集装箱装卸作业的稳定高效已成为港口经营者关注的重点.提高码头通过能力、降低码头能耗、提高船舶装卸效率,是集装箱码头未来集装箱码头发展的必然趋势.在集装箱装船作业中,如何提高装船作业效率一直都是港口企业所追求的.合理的发箱顺序,可以提高堆场场桥和码头前沿岸吊的作业效率,减少非工作时间,从而减少装船作业时间和船舶在港停泊时间,避免造成船公司和港口时间上的浪费,所以通过优化发箱顺序达到提高装船作业效率的目的是具有现实意义的.

对于装船问题,有很多学者都进行了较为详细的研究,主要分为三个方面:场地堆存位置方面,装船作业翻箱率方面和船舶配载方面.

场地堆存位置方面:合适的堆存位置会给之后的装船作业中的配载和装船作业指令提供便利,从而提高效率,所以它是提高码头装卸效率的重要环节.Kim等[1]运用动态规划以及决策树的方法对于集装箱的场地堆存位置问题进行了研究.郝聚民等[2]对于图搜索理论和模式识别技术进行了研究,以此为基础建立了随机条件下的混合顺序作业堆场优化模型,产生有利于之后做船舶配载的堆场.徐亚等[3]研究了集装箱码头的堆场空间分配问题,建立了多目标规划模型,该模型考虑了“使得集卡总运输距离最少”以及“使得各箱区工作量的差异最小”这两个目标.

装船作业翻箱率方面:对于码头来说,翻箱作业是做无用功的一种方式,浪费人力和物力,所以最大程度上地减少翻箱率是调高装船效率的重要方式.靳志宏等[4]等考虑了海关是否放关的现实约束,建立了以最小翻箱数为目标的集装箱发箱顺序决策模型.KIM等[5]利用分支定界和启发式方法研究了提箱过程中翻箱落箱位置的确定问题,发现随着问题规模的扩大,使用分支定界法的求解时间呈指数形式上升,而启发式方法解的质量明显下降.这对于问题的算法研究上具有重要意义.

船舶配载方面:装船作业指令发送是在配载已知的情况下进行的,好的配载结果可以得到更好的装传作业效率.SHIELDS等[6]首先对船舶的配载问题进行了研究建模,并和实际的装船情况进行了比较,获得了一定的效果.但是由于当时船舶比较小,装箱量也较少,其研究结果已不适合当前超大型的集装箱船舶.BOSE等[7]对影响船舶配载的所有因素都进行了分析,并用模拟仿真技术做了一个决策支持系统.但是该系统中所有因素相对比较孤立,没有从系统的角度来解,也没有进行系统优化.VIS等[8]对于近年来涉及的该类文章中的模型和算法做了较为综合全面的综述.STEENKEN等[9]针对集装箱码头管理运营的生产调度数学模型做了概括和总结,并且对其涉及的优化模型和方法进行了研究.BISH等[10]证明了用一个单独的模型来解决所有与集装箱码头相关的决策优化问题远远超出了现今的计算能力.

然而以上文献多数只考虑发箱顺序对于翻箱率或船舶稳性的影响,随着船舶的大型化发展,船舶稳性的可控范围增大,所以如何在船舶稳性允许的条件下通过更好的发箱顺序提高装船效率变得更加重要.本文考虑当集装箱分布在多贝位或多箱区时所引起的场桥移机次数和转场次数,以及船舶对于装卸舱盖板的作业因素,提出基于多箱区发箱的多目标混合整数规划模型，对发箱顺序进行决策.

1 问题描述

集装箱码头的主要业务有四种:卸船业务、提箱业务、集港业务和装船业务.其中,装船业务主要是将已经集港的出口箱进行复核、放行确认、配载和最终的实际装船.而装船作业中,配载的主要任务是把场地上需要装船的集装箱与相应船上的指定船箱位进行一一对应,即要计划每个集装箱将来要装到船上什么位置.配载结束之后才可以得出完整的箱量分布图,在制定好配载计划后,船控调度人员需要根据堆场内的集装箱的堆存位置和该集装箱在船上的配载位置,制定发箱顺序.在作业过程中,通常岸桥都是以一个船贝为单位进行装船作业,因此针对每一个船贝的发箱顺序的确认对整个出口箱装船作业的有效、顺利进行起着十分重要的作用,是整个装船作业流程中的关键环节之一.

在发箱顺序决策时,需要考虑一些限制条件,本文考虑首先要避免集装箱悬空,发箱顺序很大程度上决定了贝内的装船顺序,且装船过程中集装箱的船箱位不可随意改动,因而要避免装船时出现悬空问题.其次是随着船舶大型化的发展,对于中型或者大型集装箱船舶来说,舱内的同一个船贝可能会有2～3块舱盖板,在装卸作业过程中应码头的要求和为提高装卸效率,需要先装卸一块舱盖板下面的集装箱,再进行下一块舱盖板下面的集装箱装卸,不允许在两块舱盖板之间交替作业.

在装船作业中,为达到高效的装船效率,就应当避免一些不必要的作业,本文主要考虑的是在决策发箱顺序时的一些因素,以此作为优化目标,包括避免不必要的翻箱、降低场吊的移机次数和降低场吊的转场次数.发箱顺序可以控制场地内集装箱操作的序列,对于在同一位串(某一排)内的集装箱,应尽量保证上面的集装箱先发,否则就会产生翻箱作业.移机指的是场桥在同一箱区要从一个贝移动到另一个贝,在作业过程中还应该使场吊需要移机的总次数尽量少,以避免因指派不当造成场吊在同一箱区不同贝内频繁移动,降低作业效率,导致船期的延误.转场指的是场桥要从一个箱区移动到另一个箱区,在作业过程中还应该使场吊需要转场的总次数尽量少,转场所消耗的时间相比于翻箱操作和移机操作更费时间,所以更应该避免.

2 模型建立

2.1 模型假设

不考虑码头不截关的情况;假设装船箱位是已知的且不会再做调整;假设先从堆场中取走的集装箱都先被装上船;本文只考虑12.192 m(40ft)集装箱的贝内发箱顺序问题;本文假设只针对单路发箱进行决策;假设装船业务时分舱盖板,必须当一块舱盖板的装船任务全部完成后,才能继续装下一块舱盖板,而不允许多块舱盖板底下的集装箱交替进行装船.

2.2 模型建立

2.2.1 约束限制

(1) 防止装船悬空

(1)

如式(1)所示,不等式左侧表示每个船箱位v将来的顺序号,不等式右侧表示每个船箱位v上面一层船箱位的顺序号,所以要求左边<右边,从而保证不悬空.

(2) 分舱盖板限制

(2)

(3)

(4)

(5)

(3) 集装箱序号与发箱顺序一一对应

(6)

(7)

式(6)表示一个集装箱序号只能对应一个发箱顺序号,而式(7)表示一个发箱顺序只能对应一个集装箱序号.

2.2.2 目标函数

(1) 场内翻箱次数最少

(8)

(9)

式(8)表示目标函数一:发箱作业过程中发生翻箱的总次数最少.式(9)中不等式左边表示第y个场箱位上面一层的场箱位的发箱顺序号,而不等式右边表示第y个场箱位的发箱顺序号,若不等式左边大于右边,表示第y个场箱位先发,第y个场箱位的上一层的场箱位后发,否则会造成翻箱.

(2) 场吊移机次数最少

(10)

(11)

(12)

(13)

式10表示目标函数二:发箱作业过程中场桥移机的总次数最少.式(11)—(13)用于计算移机次数,思路与式(3)—(5)类似,这里不再赘述.

(3) 场吊转场次数最少

(14)

(15)

(16)

(17)

式(14)表示目标函数三:发箱作业过程中场桥转场的总次数最少.式(15)—(17)用于计算移机次数,思路与式(3)—(5)类似,这里不再赘述.

针对以上3个目标,由于量纲统一且都是求最小值,本文使用线性加权法将模型从多目标转化为单目标,如式(18)所示.

(18)

式中:w1,w2,w3表示3个子目标的权重.O表示总目标函数.

3 算例验证

为验证模型的有效性,本文应用LINGO软件进行编程,在IntelCore i7-4710HQ 2.50GHz计算机上进行求解,采用确定性分支定界整数规划方法.

3.1 算例描述

本文设计算例,场地堆存位置及船上配载位置如图1，2所示.共装船14个集装箱,编号从C1～C14.待装集装箱分布在堆场A132,A136,A212共3个贝,其中A132与A136为A1箱区不同贝,而A212为A2箱区的12贝.

图1 场地堆存位置示意图Fig.1 Diagrammatic sketch of storage location

(1) 场地堆存位置

(2) 船上配载位置

(3) 子目标权重

根据上海外高桥二期码头实际作业时翻箱、转场、移机所消耗的时间长短平均值,本文分别取w1,w2,w3为4,1,12.

3.2 算例结果及分析

(1) 算例结果

最优目标函数值如表1所示,最优解如表2所示.

图2 船上配载位置示意图Fig.2 Diagrammatic sketch of stowage location表1 最优目标函数值Tab.1 Best Objective Value

总最优目标值子目标一/次(翻箱数)子目标二/次(移机数)子目标三/次(数)22221

(2) 算例结果分析

① 如图3所示,根据上述求解结果,耗时10,27 min,可以看出由该模型得到的发箱顺序结果较为合理,在整个过程中共发生翻箱2次,移机2次,转场1次,实现了全局最优解.而其中移机2次和转场次数1是不可避免的,从而可以看出整体的求解结果较为理想,使用该模型对于发箱顺序进行决策较为理想.

表2 最优解

图3 算例结果示意图Fig.3 Diagrammatic Sketch of Case Results

② 若在做配载时将船上配载位置的C7箱与C8箱交换,C9箱与C11箱交换,如图3所示,则可以避免两次翻箱,得到更好的目标函数值.经过求解,耗时1.1 min,可得翻箱数为0,转场数为2,移机数为1.从而说明在条件允许的情况下对于船舶配载结果进行适当优化调整可以提高发箱顺序的效果,从而提高装船效率.所以在做船舶装船配载时就应当考虑到发箱顺序对于装船作业的影响,在满足其他约束(如重压轻限制,单槽高度限制等)的条件下,适当调整配载结果可以直接提高装船效率,避免不必要的翻箱、移机或转场.

(3) 虽然本模型为纯整数线性规划模型,但由于模型的很多约束较为复杂,给LINGO运用分支定界法带来了难处,求解时间随着求解规模的增加呈指数级增长,与KIM等[5]得出的结论类似;另外,修改配载位置前后的算例求解时间相差10倍,说明同样的问题规模,数据不同可能会导致求解效率差异比较大,说明运用分支定界法对于该模型进行求解稳定性不高,具有一定局限,故在以后的研究中可以考虑使用启发式算法进行求解.

4 结语

本文通过对集装箱码头装船作业流程的调研以及研究,针对船舶大型化所带来的问题及影响装船效率的主要因素,建立集装箱装船贝内发箱顺序决策模型,模型考虑防悬空和分舱盖板的约束,并且以翻箱次数最少、移机次数最少和转场次数最少作为目标进行优化.之后,通过设计算例和求解结果分析证明本文提出的模型能够较好地解决集装箱装船贝内发箱顺序决策问题,并且好的配载结果可以指导发箱顺序进行决策.综上所述,该模型对于装船发箱顺序决策具有较高的应用价值.同时,模型的构建方法对于研究同类基于空间布局的组合优化问题具有一定的借鉴意义.

[1] 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):89-101.

[2] HAO Jumin,JI Zhuoshang.Study of optimization of a bay of stacking[J].Journal of Dalian University of Technology,2000,40(1):102-105.

[3] XU Ya,CHEN Qiushuang.Yard space allocation based on multi-objective programming[J].Journal of Systems Engineering,2009,03:365-369.

[4] JIN Zhihong,LAN Hui.Optimization on containership loading scheduling based on actual constraints [J].Journal of Dalian University of Technology,2011(1):71-74.

[5] KIM K H,Hong G P.A heuristic rule for relocating blocks [J].Computers and Operations Research(S0305-0548),2006,33(4):940-954.

[6] SHIELDS J J.Container-ship stowage:a computer-aided preplanning system[J].Martime.Technol,1984,21(4):370-383.

[7] BOSE J,REINERS T,STEENKEN D.2000 Vehicle dispatching at seaport container terminals using evolutionary algorithms[C]//Proceedings of the 33rd Hawaii International Conferenceon System Science,Piscataway:IEEE,2000:1-10.

[8] VIS I F A,RENE D K.Transshipment of containers at a container terminal:An overview[J].European Journal of Operational Research 2003,147:1-16.

[9] STEENKEND,VOLL S,STAHLBOCK R.Container terminal operation and operations research—a classification and literature review[J].OR Spectrum,2004,26:3-49.

[10] BISH E K.A multiple-crane-constrained scheduling problem in a container terminal[J].European Journalof Operational Research,2003,144:83-107.

Decisions on container retrieving orders forcontainer terminals

MI Wei-jian,ZHANG Xiao-hua,QIN Zhao,TIAN Ting

(Logistics Engineering College,Shanghai Maritime University, Shanghai 201306,China)

Owing to the increase of world container shipping and enlargement of container ships, the port operators have focused on the stability and efficiency of container handling operation. In this regard, the container retrieving order decision during loading operation secures a crucial position for loading efficiency. By considering the hatch cover and anti-vacant limitations as constraints, and the minimum marshalling times, times of moving in the same block and times of moving in different blocks as objectives, a decision-making model for container retrieving orders is established. Afterwards, a computational example is designed to verify model efficiency. Therefore, this approach provides instructions for similar combined optimization problems based on spatial distribution.

container terminal, ship loading, hatch cover, movement in same block, movement in different blocks.

上海市科学技术委员会部分地方院校能力建设专项计划(13510501800);上海青年科技英才扬帆计划(15YF1404900);上海市教育委员会科研创新项目(14ZZ140);上海海事大学博士创新项目(2014ycx040)

宓为建(1956-),男,教授,工学博士.E-mail:nearzxh@163.com

U 691.3

A

1672-5581(2016)04-0369-06