（机械设计及理论专业论文）集装箱码头堆场箱位动态分配优化策略研究.pdf

武汉理工大学硕士学位论文 摘要 随着集装箱运输量的增加，集装箱船舶日益大型化，使得集装箱码头的作 业效率成为集装箱运输的瓶颈。如何提高集装箱码头作业效率以应对新的形势 已经成为国内外相关学者的重要研究课题。许多现有的码头承担着超负荷的作 业量，尤其是堆场空间显得相对紧缺，堆场成了码头的作业瓶颈，因此，研究 堆场的作业策略有着重要的意义。堆场的作业策略主要包括箱区分配策略和具 体箱位分配策略两个层次。本文分别对这两个层次的策略进行了研究。 首先，针对集装箱进入堆场的具体过程，建立堆存过程的数学模型，利用 图论，给出生成取，倒箱决策的启发式算法，并以减少倒箱量为目标，给出了堆 存策略的表达形式，利用模拟退火算法与仿真结合，对堆存策略进行优化。 第二，根据集装箱流在堆场上箱区间的分配过程，将箱区分配策略的优化 分成两个阶段；箱区间作业量平衡模型和箱区泊位距离最小化模型，分析了两 个阶段的约束条件，并通过启发式算法给出较优策略。 第三，利用w i t n e s s 仿真平台，根据码头作业的特点，划分集装箱码头的功 能模块，据此设计仿真模型的结构和单元，并将仿真模型细化到具体箱位的分 配。 最后，以具体码头为对象，将现行策略与本论文提出的策略分别应用于仿 真模型，通过仿真结果的对比来考察策略的优劣。 关键词：集装箱，码头，堆存策略，模拟退火算法，w i t n e s s ，仿真模型 武汉理工大学硕士学位论文 t h ep r o m o t i o no fc o n t a i n e rt r a n s p o r t a t i o na n dl a r g e ra n dl a r g e rc o n t a i n e rs h i p s h a sm a d et h e c 街c i e n c y o fc o n t a i n e rt e r m i n a l st h eb o t t l e - n e c ko fc o n t a i n e r t r a n s p o r t a t i o n a n dh o wt od e v e l o pt h eo p e r a t i o ne f f i c i e n c yo fc o n t a i n e rt e r m i n a l sh a s b e e na ni m p o r t a n ts u b j e c to fm a n yc o u n t r i e sa n dr e s e a r c h e r si no r d e rt of a c et h en e w s i t u a f i o n m a n ye x i s t e dc o n t a i n e rt e r m i n a l sa g ec a r r y i n go p e r a t i o nl o a d st h a te x c e e d t h e i rc a p a c i t y , a n de s p e c i a l l yc o n t a i n e ry a r ds 1 0 l a c cs e e m st ob et o of e wr e l a t i v e l y , w m c hm a k e sc o n t a i n e ry a r da st h eb o t t l e - n e c ko fc o n t a i n 盱t e r m i n a l s s oi ti so fm u c h s i g n i f i c a n c et or e s e a r c ho p e r a t i o n si nc o n t a i n e ry a r d s w h i l eo p e r a t i o ns t r a t e g yi n c o n t a i n e fy a r d s nb ed i v i d e di n t ot w os t a g e s ，t h a ti s ，b l o c ka l l o c a t i o ns t r a t e g ya n d s p e c i a ls l o ta l l o c a t i o ns t r a t e g y , w h i c ha r eb o t hs t u d i e di nt h i sd i s s e r t a t i o n f i r s t l y , am a t h e m a t i cm o d e li se s t a b l i s h e df o rt h ep r o g r e s so f c o n t a i n e r se n t e r i n g i n t oc o n t a i n e ry a r d s ，w h e r eah e u r i s t i ca l g o r i t h mf o rg e n e r a t i n gp u l l i n g r e - s t a c k i n g d e c i s i o n si sg i v e n , u s i n gg r a p ht h e o r y a ne x p r e s s i o nf o r mo fs t a c ks t r a t e g ya l s oi s g i v e n , a n dt h es t a c ks t r a t e g yi so p t i m i z e db ys i m u l a t e da n n e a l i n ga l g o r i t h mc o m b i n e d w i t hs i m u l a t i o n , a i m e dt or e d u c t i o no fi e s t a c k i n gt i m e s s e c o n d l b a s e d0 1 1t h ea l l o c a t i o np r o g r e s so fc o n t a i n e rf l o wa m o n g b l o c k s t h e b l o c ka l l o c a t i o ns t r a t e g yi sd i v i d e di n t ot w os t a g e s , t h a ti s , m o d e lo fo p e r a t i o n a m o u n tb a l a n c ea m o n gb l o c k sa n dm o d e lo fm i n i m i z i n gd i s t a n c eb e t w e e nb l o c k sa n d b e r t h s t h ec o n s t r a i n to ft h et w os t a g e si sa n a l y z e da n db e t t e rs t r a t l ：g i e sa r ed e v e l o p e d b y h e u r i s t i ca l g o r i t h m s t h e n , u s i n gw i 恤e s sp l a t f o r m , f u n c t i o nm o d u l e sa r es e p a r a t e df r o mc o n t a i n e r t e r m i n a l s , b a s e do rc h a r a c t e r i s t i c so fi t so p e r a t i o n t h e ns t r u c t u r ea n du n i t so f s i m u l a t i o nm o d e ii sd e s i g n e da c c o r d i n gt ot h e s em o d u l e s , w h i c hs p e c i f i e st h e s i m u l a t i o nm o d e lo n t ot h ea l l o c a t i o no fs l o t s f i n a i l v as p e c i f i ct e r r a i n a li st a k e na so b j e c t , w h i c hi sa p p l i e dt h et r a d i t i o n a l s t r a t e g i e sa n dt h es t r a t e g i e sg i v e ni nt h i sd i s s e r t a t i o n a n dt h ep e r f o r m a n c ei ss t u d i c d b yc o m p a r i n gt h es i m u l a t i o nr e s u l t s k e yw o r d s ：c o n t a i n e r , t e r m e d , s t a c k ss t r a t e g y , s i m u l a t e da n n e a l i n ga l g o r i t h m ， w i t n e s s ，s i m u l a t i o nm o d e l 武汉理工大学硕士学位论文 1 1 课题概述 第1 章绪论 1 1 1 课题的来源 本研究课题来源于教育部重点科技项目“基于无线局域网的集装箱堆场机 械调度与监控系统研究”和天津港科技项目“北港池集装箱码头物流系统分析”。 1 1 2 课题研究的背景 当今世界上6 0 以上的海路运输采用集装箱运输的方式，特别是在某些经 济发达的国家之间，集装箱化已达到1 0 0 1 1 1 随着世界贸易的增长，集装箱运 输量持续增加，集装箱港口作为集装箱海路运输的起点和终点，同时也是衔接 海路与陆路的枢纽，港口之间的竞争越来越激烈，地理位置较近的港口之间表 现得尤为突出 集装箱运输量的增加，使得集装箱船舶大型化趋势日益明显，最近建造的 p o n lm o n d r i a a n 的容量已达到8 4 5 0 t e u l 2 1 。大型船舶的投入使用，使得集装箱 码头的作业效率成为集装箱运输的瓶颈，如何提高集装箱码头的作业效率以适 应集装箱运输的发展已经成为许多国家的重要研究课题。 随着我国对外贸易的持续增长，集装箱运输量保持着较高的增长速度，2 0 0 6 年1 至1 1 月，全国主要港口累计完成国际标准集装箱吞吐量8 3 5 4 3 2 万t e u ， 比去年同期增长2 3 3 。其中沿海港口完成7 7 9 0 0 7 万t e u ，比去年同期增长 2 2 3 ；内河港口完成5 6 4 2 5 万t e u ，比去年同期增长3 8 5 。据预测，到2 0 1 0 年，中国港口集装箱吞吐量将达到1 5 亿t e u 3 1 。如此快速的增长为我国的集装 箱港口带来了巨大的机遇和挑战，除了加大力度建设新的码头之外，在现有的 港口规模下，如何挖掘潜力，改进管理水平，提高生产效率，是港口面临的共 同问题。而且，我国的港口管理水平与发达国家的现代化港口有较大的差距， 相同规模的港口，其吞吐能力远逊于国外，单纯地依靠增加设备投入并不是最 经济的办法1 4 j ，因此提高港口的管理水平，研究更合理的码头装卸工艺流程也是 武汉理工大学硕士学位论文 港口的当务之急。 1 1 3 课题研究的目的及意义 随着我国经济的不断发展，集装箱码头资源日益紧张，而我国大部分集装 箱码头的生产调度却依然延续着过去的方式，仍然在很大程度上依靠经验来组 织生产，在堆场资源相对紧缺的现状面前，传统的生产计划方式显然无法满足 新的要求，近年来，在我国主要枢纽港口的集装箱码头，班轮等待泊位的现象 频频出现，集装箱码头超负荷运行相当严型5 】。传统的堆场作业策略使得堆场 效率相对低下，严重地约束了集装箱码头整体效率的提高。因此，深入研究堆 场作业的客观规律，改进或优化堆场作业策略无疑具有重要的学术价值和工程 意义。 1 2 课题研究现状 依据描述系统模型的数学基础，系统可分为连续变量动态系统( c 、，d s ) 和离 散事件动态系统( d e d s ) 。 c v d s 的动态过程服从物理学定律和广义物理学规律，其数学模型可表为微 分方程或差分方程；电路系统、机械动力学系统就属于此类系统。 d e d s 的行为进程是由离散事件驱动，遵循的是一些复杂的人为规则，而不 是物理学定律和广义物理学规律。离散事件是指d e d s 中发生在离散时刻的事 件，所谓事件则是使d e d s 状态发生变动的一个行动或事情。交通系统、码头 装卸系统、工业生产线系统、物流系统、服务系统等就属于此类系统。d e d s 是 系统和控制领域一门新的分支，是由哈佛大学y c h o 教授等人于2 0 世纪8 0 年 代前后创立的。d e d s 的主要特点是状态变化的异步性、并发性、不确定性、服 从人为规则且状态只能在离散时间点上发生跃变 2 1 。d e d s 的分析模型主要建立 在随机过程、运筹学、控制论、人工智能与自然语言等多学科的基础上对于 复杂的d e d s ，一般用计算机仿真技术来研究。 集装箱码头装卸系统是一个复杂的离散事件动态系统，几乎涉及到物流运 输学科里各种复杂的问题。作为一个复杂的离散事件动态系统，码头内部可分 为许多子系统：岸边装卸船系统、水平运输系统、堆场堆存系统、闸口进出系 统、计算机生产管理系统以及其它设备生产辅助系统等。这些予系统相互联系， 2 武汉理工大学硕士学位论文 相互制约，有机地组合在一起。整个系统主要有两个与外部发生关系的有形输 入输出边界，船舶的输入输出涉及到海域边界，它与岸边装卸船系统直接发生 关系；集疏运卡车和铁路列车的输入输出涉及到陆域边界，它与闸1 3 进出系统 发生直接关系；还有一个无形的输入输出边界，即信息交换。它通过i n t e r n e t 、 传真或e d i 专线与港口联系。系统内部各子系统之间的输入输出，也是在一系 列离散事件和各种随机因素的作用下，相互传递。整个系统在船舶和陆域集疏 运车辆的到达事件驱动下，演绎着整个码头的动态进程。 在集装箱码头装卸系统里有多种实体在流动，既有有形实体，又有无形实 体。有形实体包括船舶、集疏运卡车、进出口集装箱、内部拖车、堆场起重机、 岸边起重机等；无形实体有船舶计划、堆场计划、装船计划、卸船计划、提箱 计划、装卸设备状态信息等。船舶、集疏运卡车、船舶计划，集装箱等属于临 时实体，从码头系统外部进来，经过一系列的装卸作业过程后又离开系统。另 外一些动态实体属于内部实体只在港口内部各子系统之间流动。这些实体的流 动触发了一系列的离散事件，改变着码头内部各子系统的状态。码头内部状态 变化呈现异步性、并发性和不确定性。船舶和集疏运卡车到港时同间隔的随机 性，决定了系统内部状态变化的异步性；而船舶和集疏运卡车的到达可触发码 头各子系统状态同时变化，使码头内部状态变化呈现并发性l 硎。 离散事件动态系统是在人为逻辑规则下运行的。集装箱码头有许多管理制 度、交通规则和生产调度策略。这比其它类型码头的规则性更强。这些制度、 策略和规则把码头内部各系统有机地统一起来，以最大限度减少船舶在港时间 为总目标，高效地运作。 近十年来国内外许多专家学者都对集装箱码头做了多方面的研究，概括如 下： 船舶计划方面。h a j c t a l ( 1 9 9 7 ) 用非线性整数规划模型、h s i e h ( 1 9 9 9 ) 用修正的 时空网络等方法进行了研究，目标是减少船舶待泊时闻，提高泊位使用率 6 1 ， 集装箱岸桥调度方面。d a g a n z o 采用整数规划模型和一个简单的分配策略， 分析岸桥的作业效率，计算在高峰期泊位的最大吞吐量，解决静态岸桥调配问 题，达到了减少船舶待泊费用的目的。d a g a n z o 又认为岸桥调度是个并行工作的 “开放程序站”调配闯题，建立整数规划模型来减少船舶待泊费用，并采用分 支和跳跃方法来获得优化结果。基于上面的结论，d a g a n z o 假定船舶的工作量分 布与船舶数量分布相同，进一步研究了岸桥的调配策略对码头的吞吐量和船舶 武汉理工大学硕士学位论文 等待的远影响。t a b e m a c l e 将学习理论应用到岸桥分析中以提高岸桥对时间的效 率川。 具体就堆场集装箱区域的划分( 堆放策略) 和堆场设备调度而言，目前的文献 资料主要是研究集装箱在码头堆场的配位问题，并由此考虑如何在最小化翻箱 作业量与最大化集装箱码头堆场利用率之问达成妥协，而且绝大多数研究都以 静态的方式进行考虑。此外，关于码头堆场装卸机械的作业调度问题的文献也 很少。国内目前对这些方面的研究几乎还是一个空白，大部分研究仅停留在堆 存方式和原则的定性讨论上。 国外很少有关于集装箱堆存的研究文献发表，r o m m e r td e k k e r 和p a t r i c k v o o g d 2 】认为主要原因在于集装箱堆存的实际情况极其复杂，很难得到解析解。 瑙曲1 6 l 考察了不同码头堆场的布局及其对疏运过程中平均倒箱次数的影响，为 简化求解建立了回归方程。l ( i m 等人在文献 7 1 中研究了堆存空问分配策略，分别 分析了集装箱按固定速率到达、按周期到达及动态到达的情况，以极小化总倒 箱次数期望值为目标函数，给出了一些算例。m 等人在文献【8 】中以最小化装船 过程中倒箱次数期望值为目标，就出口箱堆存位置问题提出了动态规划模型， 此模型中考虑到了堆场的布局、在场集装箱重量的分布、以及到达的集装箱重 量，并从动态规划的最优解集中导出了快速决策树以供实时决策。p r e s t o n 和 k o z a n 【9 】提出了基于遗传算法以最小化船舶装卸时间的方法，他们将不同作业顺 序( 随机顺序，先到先服务，后到先服务) 下如何确定最优堆存位置的问题抽 象成一个n p 难的混合整数规划( m 坤) 模型，其计算结果表明，堆场布局较合理 的情况下作业顺序对船舶的装卸时间并没有影响，而当堆场利用率在1 0 - 5 0 之 间变动时，装卸时间线性变动。k m 和p a r k l l 0 】研究了出口箱堆放空问动态分配 方法以提高对场空间利用效率和装船作业的效率，提出了基本的混合整数规划 模型，根据算例比较了两种启发式算法：近视算法( m y o p i cm e t h o d ) 和次梯度 法( s u b g r a d i e n tm e t h o d ) 。郝聚民等提出过“混合顺序作业堆场b a y 优化模型”， 利用图搜索技术和模式识别理论研究堆场的优化问题【1 1 】。荷兰的m a r kb d u i n k e r k e n 等人提出了堆场堆码的最大剩余堆存空间( r e m a i ns t a c kc a p a c i t y ) 策略，其仿真结果显示，采用这种策略堆码的倒箱次数明显少于常规的堆码方 式1 1 2 1 。t a l e b i b r a h i m i 、c a s f i l h o 和d a g a n z o 分别比较了进口箱和出口箱在不同堆 放策略下所需的堆场面积并得出了工作量。k i m 和p a r k 研究了多种数学算法和 费用模型以寻找在不同标准下的堆放策略。对于场桥分配和计划的研究，l a 和 4 武汉理工大学硕士学位论文 l a m 比较分析了集中不同的大型集装箱堆场的堆场设备分配策略。k i l n 通过将 整个过程作为一个复杂的整数规划来建模，减小了集装箱堆场起重机的起动和 运行时间。张楚谦用整数规划模型来研究轮胎式起重机的配置问题，以减少堆 场工作的延迟，并通过拉格朗日放松启发式理论来获得接近最佳解决方案。也 有些文献同时考虑到几项对集装箱码头通过能力影响较大的因素。k o z a n 和 p r e s t o n 使用整数规划决定优化的堆放策略和相应的堆场起重机分配，以减少用 于一艘船的所有起重机的最大工作时间。b a u i s 和a b a c o u m k i n 建立了一个包括 由于设备不匹配而引起的交通堵塞和延迟的仿真模型。他们使用这个模型来评 价一个码头的堆场设计、设备数量、集卡到达、运行规则等。上述研究基本上 只涉及了一个作业流程，如疏运作业流程或卸船作业流程，很少考虑堆场机械 的调度及其作业中产生的消耗，而且上述研究基本局限于堆场的某个箱区，对 于整个堆场箱区在作业中动态分配问题少有涉及，正因为如此，这些研究所取 得的成果在面对集装箱码头堆场复杂的实际情况时，依然束手无策。 计算机仿真方面： 在国外，1 9 9 5 年由德国i s l ( i n s t i t u t eo fs h i p p i n ge c o n o m i c sa n dl o g i s t i c s ) 开发的集装箱装卸系统模拟器s c u s y ( s i m u l a t i o no fc o n t a i n e ru n i th a n d l i n g s y s t e m s ，s c u s y 模型包括i n p u t ，s i m u l a t i o n 和o u t p u t 三大部分，输 入欲仿真港口相应的资料和参数，通过模型仿真即可输出计算结果) ，已成功的 应用于研究不同堆码方式对整体的影响，比较采用不同设备组合的堆场作业方 式、分析不同设备的选用对码头生产的影响等；美国公司j w d ( j o r d a nw o o d m a n d o b s o ng r o u p ) 开发了一个集装箱码头系统的仿真软件包，在加拿大温哥华港 d e l t a p o r tc o n t a i n e rt e r m i n a l 规划中，用计算机仿真手段把场地规划和成熟的运 作方式分析结合起来。仿真运行生成码头泊位利用率、船舶等待时间、设藏和 设备利用率、营运成本等方面的数值结果。但该公司在这个仿真中忽略了船舶 和外部集卡到港的随机性，而是借助于其在该领域的丰富经验选择“特殊情形0 并将通过附加较大的裕量将仿真结果修正到合适的范围。澳大利亚的r e a l t i m e r u s i n e s s s o l u t i o n r t y 公司推出的港口运作仿真软件x w j l i d o w ，以集装箱码头 等多种码头为仿真对象，以二维图形方式对包括设备配置、堆场规划等在内的 一些问题进行仿真，为港口决策者提供了很好的规划依据，从而提高了港口的 生产效率1 9 1 埘。 在国内，1 9 9 6 年上海海运学院开发了一个应用于港口生产调度的动画模拟 5 武汉理工大学硕士学位论文 模型；1 9 9 9 年北京水运科学研究所的邓晓云采用a u d i t i o n 软件建立了集装箱 码头装卸系统动画模拟模型。大连海事大学的肖青、刘翠莲对港口通过能力进 行了专门的研究( 国家自然科学基金资助项目) ，应用g p s s 系统模拟语言，建 立了港口通过能力系统的动态模拟，试图为实现对港口生产的组织、指挥、控 制与调整提供决策依据和方法例。 北京水运科学研究所的彭传圣等利用加拿大h a l i f a x 港h a l t c r m 集装箱装卸 有限公司的码头操作管理规则开发了一个集装箱码头模拟模型，此外还研究了 天津港集装箱公司码头模拟模型、加拿大v a n t e r m 集装箱码头模拟模型、天津港 改扩建集装箱码头工程计算机模拟模型等。研究的主要内容有：在吞吐量一定 的情况下，岸边集装箱起重机数量配备的研究；堆场作业设备和拖挂车配备的 研究；要达到一定的吞吐量港口码头的。瓶颈”位置。 河海大学的鲁子爱教授把港口生产视为随机服务系统例，建立了模拟港口 营运状况的计算机仿真系统。仿真的输出为港口吞吐量、船舶的平均等待时间、 平均服务时间和平均排队长度等港口营运参数。仿真模型中，船舶占用泊位时 间根据船舶装卸量、码头泊位装卸效率、气候影响等条件计算确定；天津大学 的别设安教授，提出了利用循环网络模拟方法将排队论、网络计划技术、计算 机模拟技术结合起来，对港口的营运过程进行模拟，从而得到港口泊位、仓库 等的利用情况；对具体的装卸工艺进行模拟，可以得出合理的调度方案。 2 0 0 1 年上海海运学院为上海国际航运中心某新建集装箱码头的装卸工艺系 统进行了计算机仿真研究，应用离散随机系统思想，以排队系统建立了仿真模 型。该离散系统仿真模型的建立，是在分析港口装卸工艺、港口的生产的基础 上，主要根据随机发生的离散事件、代表系统中所描述主要对象的实体流以及 仿真时问的推进机制，按照港口的生产和管理系统地运行来建立模型例。 2 0 0 2 年，一航院完成了集装箱码头模拟模型的开发，该模型可划分为码头 前沿装卸船作业、堆场堆取箱作业、大门接收箱作业三个系统。另外有部分文 献表明，国内对码头三维虚拟现实的图像表现也进行了一定的研究闭。 从以上的研究文献可以看出，人们对集装箱码头这样一个复杂的离散事件 动态系统的认识和研究有一个深化的过程。过去，由于理论和方法手段的制约， 人们主要是针对码头内某些局部问题单独抽取出来做研究和分析，比如，船舶 靠泊分析、岸边机械配置与调度、水平运输机械配置与调度、闸口的排队问题、 装卸船路径优化等，另外由于集装箱堆场问题复杂，人们往往简化或避开它。 6 武汉理工大学硕士学位论文 所以，尽管以前的研究和分析成果对集装箱码头的规划设计和管理起到了一定 的促进作用，但是这些研究成果缺乏对整个集装箱码头装卸系统全面、深入、 系统的描述，各部分研究内容缺乏有机的联系，研究缺乏清晰的层次构架，很 少考虑并发、异步和不确定性等复杂系统的特征。总之，不是以一个随机、动 态的系统处理方式来研究整个集装箱码头装卸系统的运作过程。随着离散事件 动态系统理论的日趋完善和计算机软件的高速发展，尤其是面向对象编程方法 的出现，为人们解决复杂的离散事件动态系统研究问题提供了新手段。 1 3 本课题研究的内容 本课题集中于集装箱码头堆场的分配策略研究，根据集装箱码头堆场作业 的特点，对集装箱码头堆场的倍内箱位分配和箱区分配过程进行深入分析，建 立理论模型，并通过优化算法对分配策略进行优化，最后提出新的动态箱位分 配策略。 本论文的主要研究内容如下： ( 1 ) 集装箱堆存过程研究及倍内具体箱位分配优化策略。根据堆场进箱的具 体过程，建立堆存过程的数学模型，并给出生成取，倒箱决策的算法，并以减少 倒箱量为目标，利用优化算法对堆存策略进行优化； ( 2 ) 箱区动态分配策略。根据集装箱流在堆场上箱区何的分配过程，分析各 项约束条件，建立箱区动态分配的优化模型，并通过启发式算法给出较优策略； ( 3 ) 动态箱位分配仿真模型的开发。利用w i t n e s s 仿真平台，根据码头作 业的特点，划分集装箱码头的功能模块，据此设计仿真模型的结构和单元，并 将仿真模型细化到具体箱位的分配，最后以具体码头为对象，将现行策略与本 论文提出的策略分别应用于仿真模型，通过仿真结果的对比来考察策略的优劣。 7 武汉理工大学硕士学位论文 第2 章集装箱码头堆存过程研究 2 1 集装箱码头堆存过程概述 集装箱码头( c o n t a i n e rt e r m i n a l ) 是专供停靠集装箱船舶并对其进行装卸作 业的场所，它一般由泊位、集装箱堆场、控制室、闸口、集装箱专用机械设备 等组成。一个典型的集装箱码头布局如图2 - 1 所示。 图2 - 1 某集装箱码头布局示意图 集装箱码头的作业是以集装箱装卸与搬运为中心，调度全码头的人力、设 备和管理资源以完成集装箱交接的过程。总体上可以分成集港作业、卸船作业、 装船作业和疏运作业四个部分，各部分作业流程如下： 糖集港作业：外部集装箱卡车把将要出口的集装箱运送到码头，经过闸1 3 后进入堆场，到指定地点由堆场机械将集装箱堆码到指定的位置，以备 将其装上船舶。 纛卸船作业：岸边起重机械把船舶上需卸载的集装箱卸下，然后集装箱卡 车将其运送到堆场上计划的地点，由堆场机械将集装箱堆码到指定位 8 武汉理工大学硕士学位论文 置，卡车回到前沿继续装载集装箱。 l i t 装船作业：堆场机械把要出口的集装箱从堆场中依照取箱计划按顺序提 出，装载到集装箱卡车并由其运送到岸边，由岸边起重机械装到船舶上 指定位置。 霹疏运作业：外部集装箱卡车经过闸口，到达堆场中指定地点，堆场机械 将卸下的集装箱提出，交给卡车，卡车在闸口处经确认后将集装箱运离 码头。 集装箱堆场作为码头装卸作业的缓冲区，其存取箱效率是整个码头作业效 率的重要因素。通常集装箱码头的堆场被划分成更小一些的长方形场地，这些 场地被称为块、街( b l o c k ) 或箱区，每一块里沿长边一个t e u 长度被称为倍( b a y ) 。 沿短边一个t e u 宽度被称为排或行( r o w ) ，倍中的一排成为垛或栈( s t a c k ) ， 每一垛在竖直方向上可以堆码多层，垛中的每一层空间称为一个箱位( s l o t ) 。 图2 - 2 堆场某块局部示意图( 每一个小方块表示1 t e u ) 9 武汉理工大学硕士学位论文 通常，码头在获得某一船舶船联船图等资料后，将结合堆场的占用状况， 为该船计划进出口箱的堆存区域，安排集港作业时间，为堆场机械指派任务。 当外部集装箱卡车将集装箱送达码头之后，在闸口处由码头的管理系统依据集 装箱的尺寸、重量、船名、目的港等信息，在计划的出口箱区内为其指定箱位， 卡车驶往箱位附近，由堆场机械堆码到指定箱位。集港作业完成后，码头根据 船图及堆场出口箱堆存状况安排每一箱的装船顺序，如果需要先装船的集装箱 被后装的箱压住，则在装船作业时须先移开其上的箱，即为倒箱( r c s t a c k , r c s h u f f l e , 或r e - h a n d l e ) 。由于集装箱到达码头时其装船顺序并未确定，因而倒 箱通常不可避免。 集装箱堆场倒箱的主要原因有： 1 ) 不同船名、航次的重箱混合进场。许多船公司先把重箱收迸场，然后根 据情况给出船名、航次，这样就可能产生不走船压走船的现象。为顺利进行装 船作业，需将走船的集装箱取出，放至适当位置。 2 ) 船公司临时改变某集装箱的航次或目的港。码头必须修改装卸船计划， 导致部分集装箱必须倒箱。 3 ) 不同重量级的集装箱混合堆放。码头接收的重箱进场是随机的，从而导 致轻箱压重箱、轻重箱混合在一起的现象。为了保持集装箱船舶的稳定和纵向 强度，充分利用集装箱船舶箱位，需在装船前倒箱。 4 ) 为防止中途挂港船上倒箱，集装箱班船航线中途挂靠港较多，根据集装 箱船舶挂港顺序和集装箱到达各挂靠港的情况，考虑途中挂靠港的装卸情况， 码头装船时，防止产生后挂港集装箱压前挂港集装箱，堆场必须对集装箱按到 港顺序进行调整，从而产生堆场倒箱。 5 ) 特殊箱型的重箱由于在船上有比较周定的位置，装卸作业前必须在堆场 内单独堆放，以便于装箱，从而导致倒箱，如冷藏箱、危险箱、框架箱、高箱 等。另外，进口重箱发放给收货人或内陆承运人时，所产生的倒箱也是比较常 见的，因为他们来码头提箱是陆续和随机的，不可避免地要产生倒剁1 3 】【1 4 1 。 为尽量降低倒箱操作次数，堆场集装箱的堆放一般遵循p s c w 原则，所谓 p s c w 原则就是指同一日的港( p o r t ) 、同一尺寸( s 缸r c ) 、同一种类( c a t e g o r y ) 和同 重量级别( w e i g h o 的集装箱尽量堆放在堆场的同一倍内【1 1 】。当同一批集装箱中 目的港的数目较多、种类较多，重量比较分散时，采用p s c w 原则就需要为该 批集装箱分配较多的倍位，而实际上每个倍内的箱数可能会很少，这样大大地 武汉理工大学硕士学位论文 降低了堆场的利用率，倒箱次数与堆场利用率在码头的操作中成了一对矛盾。 由于倒箱操作被认为是非生产性的操作，因此，减少倒箱操作是码头管理中的 重要课题。 本章将讨论集装箱在集装箱码头内的存取过程。 2 2 集装箱存取过程 2 2 1 集装箱存取过程描述 集港作业中，卡车通过闸口时，管理系统获取当前车上集装箱的箱号、船 次、目的港、尺寸、种类和重量等信息，然后在相应的区域内搜索合适的倍位， 考虑倍内已分配箱位上集装箱的信息，将某一合适的箱位分配给当前箱。 装船作业时，码头依照船图，按一定的顺序从堆场中取箱，由于要满足船 舶平稳的要求，对于同一目的港、同一类型、同一尺寸的集装箱，较重的箱需 要先装船，因而，在集港时，应尽量将较重的箱堆在较轻箱之上。 如图2 - 3 所示，其中( a ) 表示2 0 个集装箱先后到达堆场，为此2 0 个集装 箱在某一倍位中按p s c w 原则堆存的状况，( c ) 中的数字表示该箱位上集装箱出 场的顺序，深色标出的箱为障碍箱，即其下压着需要先取出的箱，按照中的 取箱顺序，至少需要倒箱三次。 - - 团回回回田曰回回回团团田团口固囡团团团口 ( a ) 团曰固 团团回回回 固团囡囡团囡 田曰团回曰回 口口口 团团圆圈曰 团固团团囡团 团回团回曰田 ( c ) 图2 3 集装箱存取过程示意图 1 1 武汉理工大学硕士学位论文 2 2 2 集装箱存取过程模型 ( 1 ) 基本假设 设某一批集装箱数目为n ，先后到达堆场，箱的出场优先级别工( 1 x 肼) 相互独立且服从相同分布f ，倍位容量为r x l ( r 排l 层，r x l n ) ，取箱时 才进行倒箱操作。 ( 2 ) 存取过程 存箱过程可用下式表示： 垦- e - l4 - s t k ( 马_ l ，x j ) ( i = l ，2 ，n ) ( 2 1 ) 其中： e l r 矩阵，第i 箱堆存后倍位状态，其元素为各箱位上的出场优 先级别； s t k ( b , 。，置) 基本假设条件下生成堆存决策的策略函数。 设出场优先级别为k 的箱数量为开。，取箱过程可表示为： - 0 一b s 群+ l o - 磁, i t k 磁，j r 鲥七饿，卜l ，七) 一s 似，1 ，七) ( k - - 1 ，2 ，m ，= 1 ，2 ，j 厅t ) ( 2 - 2 ) 其中： o 一取箱前倍位状态矩阵 以o 一取出优先级别为k 的箱之前倍位的状态 r s t k ( 雕d - 1 , 七) 生成倒箱决策的策略函数 5 似- ，| i ) 一出场序为l 【的箱及其箱位 取箱中总的倒箱次数为，显然，是取箱前倍位状态o 和倒箱策略如旋 的函数，又 或，。一一薹s t k ( b i _ , ，x i ) ( 2 - 3 ) 从可写成： n r nr q l ，s t k ，r s t k ) ( 2 - 4 ) 武汉理工大学硕士学位论文 即，存取过程的倒箱次数由集装箱进场过程、堆存策略、及倒箱策略确定。根 据假设，集装箱的出场优先级服从一定分布，因而在此条件下，倒箱次数的统 计量取决于堆存策略和倒箱策略。 2 2 3 集装箱取倒箱策略 在倍内的箱都堆放完毕后，倍内各箱的出场优先级别以及之间的位置关系 已经完全确定，以每搬动一个箱子为一个决策，以倒箱次数最小化为目标，则 倒箱策略问题为一个确定性规划问题。然而，每一次倒箱决策都可能改变之后 若干步决策的空间，不满足动态规划的无后效性条件，因而不能使用传统的动 态规划来求解。 ( 1 ) 取，倒箱作业优化的启发式算法 设一( 6 1 ，6 2 ，) ，其，中岛一 ，岛：，k ) ，表示某个垛的状态，定义 f 为该垛的复杂程度，表示取出该垛内最上层优先级别最高的箱需移走的箱 数。定义_ i l a ) 为f 垛已堆层数。定义操作c p ( 彰，i ，j ) ，o ( ，o r 时，表示将i 垛顶 层箱移到，垛，。0 时表示取走i 垛最磺层箱，研为第f 步操作前的倍位状态。 令 印m d - 0 描( 2 - 5 ) 则最优的策略的目标为： m i l l o p ( 耳，i ，) ( 2 - 6 ) 舌刍。箍商蟊 。 约束条件为： _ j i ( ，) 厶，- 0 j i l a 卜0 构造一个无向图g ，e ) 以为节点，以耳到占：n 为边，以f o ) 为边的权值。 设z 是g 的一个生成树，若把z 中各边的权值相加，则这个和数称为生成树z 的 权数，在g 的所有生成树中权数最小的生成树称为的最小生成树。 树z ( v ，e ) 为图g ( v ，e ) 最小生成树的充分必要条件是对z ( v ，e ) 以外的任意 边 ，v j ) 有： 武汉理工大学硕士学位论文 ( 吩，”，) 之m a x , o ( v , ，h 1 ) ，( 屹l ，u 2 ) ，珊( ，v ，) ) ( 2 - 7 ) j t e e ：“，q ：，v a ， ，) 为生成树中连接q 和v ，的路径，为连接边的权重，故 图g ，e ) 的最小生成树z ，e ) 为必然由那些权重较小的边组成且不会形成回 路。因而，倒箱数最小的路径即为g ，e ) 的最小生成树。 k u r s k a l 最小生成树算法步骤描述如下： 设g ( 以e ) 为由辨个节点组成的连通赋权图， 1 ) 先将g ，e ) 所有边按权数大小由小至大重新排列，并取权数最小的一边 为z ，e ) 中的边； 2 ) 从剩下边中按( 1 ) 中排列取下一条边，若该边与前已取进z ，e ) 中的边形 成回路，则舍去该边，否则把该边也取进z ，e ) 中； 3 ) 重复步骤( 2 ) ，直到有册一1 条边取迸z ，) 中为止，这i n 一1 条边就组成的 最小生成树【1 5 1 。 基于k u r s k a l 最小生成树算法，可给出倒箱问题的一个启发式算法，其步骤 如下： 1 ) 计算f 0 ，g - 1 2 ，r ) ； 2 ) 搜索整个倍中优先级别最高的箱所在垛，毛，f ，；若倍已空，转到5 ) ； 3 ) 若存在f 瓴) - 0 ，则印( 彰，o ) ，转到步骤2 ) ；否则，转到步骤4 ) ； 4 ) 搜索f 以) - m i n t r 瓴) ，f ( f 2 ) ，f ( ) ) ，开始确定垛中的障碍箱应该倒往 哪一垛，转到4 1 ) ； 4 1 ) 如果印( 群，1 ) 后，f 瓴1 ) 一0 ，则印( 耳，1 ) ，转到3 ) ；否 则转到4 2 k 4 2 ) 如果垛，为空垛，则印( 耳，j ) ，转到3 ) ；否则，转到4 3 ) ； 4 1 3 ) 记f 7 ( 力为印倒，j ) 后的f ( ，) ，搜索f u ) 一m i n 扛( ，) ，( j - ) ， c 少( 蟛，厂) ，转到3 ) ； 5 ) 结束。 ( 2 ) 算例 如图2 - 4 ，( a ) 为随机生成的某一倍位状态，为启发式算法生成的倒箱决策。 该倍有4 排4 层，1 表示最大优先级别，4 为最小优先级别，( 1 4 ) 表示把垛1 的最顶层箱倒到垛4 上，( 1 0 ) 表示把垛i 的最顶层箱取走。 定义倒箱次数箱数比为某倍取箱过程中，倒箱的次数与该倍中箱数之比。 1 4 武汉理工大学硕士学位论文 当各箱位按平均分布随机生成倍位状态时，在不同倍位规模下分别做2 0 0 0 0 次 实验f 不同的优先级别数取m - - 4 ) ，实验结果如表2 - i 所示 从表中可以看出，随堆存高度的增加倒箱次数有较大的增加，并且即使仅 限堆三层，倒箱次数箱数比仍然高达2 7 5 0 。 ( 1 4 ) 囝 1 2 3 4 ( a ) ( 1 - 0 )( 1 - 4 )( 1 _ 0 ) 图2 4 倒箱决策举例 圈圆圈一田 圈圈固一田口圈圈圈田田 武汉理工大学硕士学位论文 表2 - 1 平均倒数次数箱数比 x 5 67891 0 平均值 32 6 1 5 2 6 8 4 2 7 4 9 2 7 9 3 2 8 2 3 2 8 3 5 2 7 5 0 4 3 6 1 3 3 6 4 3 3 6 9 l 3 7 0 3 3 7 2 2 3 7 3 7 3 6 8 5 5 4 4 4 6 4 5 0 5 4 5 2 9 9 64 4 9 1 4 5 0 4 4 5 0 2 4 4 9 6 65 3 0 1 5 2 7 2 5 2 6 6 5 2 6 8 5 2 1 9 5 1 9 1 5 2 5 3 7 6 0 2 9 5 9 9 9 5 9 0 3 5 8 8 7 5 8 6 0 5 8 3 1 5 9 1 8 平均值4 4 0 1 4 4 2 1 4 4 2 8 4 4 2 8 4 4 2 6 4 4 1 9 2 2 4 集装箱堆存策略 ( 1 ) 堆存策略表示 在码头操作中，通常把具有相同尺寸、船名、目的港等属性的出口箱安排 堆存到同一倍中，因而对于某一倍而言，各箱位上集装箱的差别仅仅在于重量 的不同。集装箱按重量被划分成若干重量级别，不同的码头有不同的划分标准， 常见的划分方法是将集装箱划分成三个重量级别：h 、m 、l 【1 6 1 ，即m = 3 。在已 确定倒箱策略时，堆存策略的优劣直接决定了倒箱操作的数量水平 当某一集装箱到达该倍时，考虑倍内的堆存状况，假设堆商限3 层，则备 选箱位所在垛的堆码状况可能有1 3 种，如图2 - 5 ： 1 23456 t 8g l o1 11 2 1 3 图2 - 5 限高三层时可能的堆码状况 因此，为该箱做出的堆存决策即对此1 3 种状况进行排序，然后从倍中选择 最优先的垛。用1 到1 3 来表示垛的状态，则该倍的状态又可以表示为一个向量， 如图2 - 6 ： 武汉理工大学硕士学位论文 ：吠态( l5 ，3 ) 图2 - 6 用垛状态表示的倍状态向量( 表示已堆满) 而堆存策略可以表示成1 到1 3 的一个排列，例