（计算机应用技术专业论文）码头集装箱卡车优化调度及其仿真.pdf

摘要 本论文研究码头集装箱卡车优化调度问题，重点研究码头集装箱卡车的优化调 度算法，并以集卡传统调度算法、最短路径调度算法、最小等待时间调度算法为基 础，采用a r e n a 仿真软件平台对青岛前湾港集装箱卡车优化调度进行了仿真。 讨论了集卡传统调度方式，提出了集卡传统调度方式的数学表达式；将最短路 径法应用于集卡优化调度，建立了最短路径法集卡优化调度的数学模型；以集卡最 小等待时间为依据，整体考虑集卡在装货、卸货与转堆过程的综合调度问题，提出 了集卡最小等待时间优化调度算法，建立了基于最小等待时间的集卡优化调度算法 的数学模型；对优化调度算法与传统调度算法、基于最短路径法的集卡调度与基于 最小等待时间算法的集卡调度进行了比较。 基于a r e n a 仿真软件平台，以集卡传统调度算法、最短路径调度算法、最小 等待时间调度算法为基础，综合青岛前湾港机械设备参数，进、出口作业流程图等 港口实际数据，模拟集卡运输过程，分析了单船与多船的集卡配置数量、集卡等待 时间、集卡运输时间、集卡行驶距离等集卡相关参数；讨论了集卡的空、重载速度 及岸桥桥吊服务时间的改变对集卡配置数量的影响，对青岛前湾港集装箱码头进行 了仿真，计算了集卡空、重载速度与岸桥桥吊服务时间的最优值，为港口作业人员 合理选择集卡、桥吊、轮胎吊机械设备提供依据。 通过本文的研究能够减少集卡的运输时间、等待时间、配置数量，提高集卡重 载率与利用率，进而提高整个集装箱码头的吞吐量。 关键词：集卡；优化；调度；算法；仿真 a b s t r a c t t h i sp a p e rm a i n l yi l l u s t r a t e st h eo p t i m i z a t i o n a ld i s p a t c h i n gq u e s t i o nt oc o n t a i n e r t r u c ki nt h ec o n t a i n e rt e r m i n a l ，e s p e c i a l l ye m p h a s i z e st h eo p t i m i z a t i o n a ld i s p a t c h i n g a l g o r i t h mo fc o n t a i n e rt r u c k t h r o u g ha r e n as i m u l a t i o ns o f t w a r ep a c k a g e ，t h ep a p e r s i m u l a t e st h ep r o c e s so fc o n t a i n e rt r u c ko p t i m i z a t i o n a l d i s p a t c h i n gi nq i n g d a o q i a n w a nc o n t a i n e rt e r m i n a lo nt h ef o u n d a t i o no ft h et r a d i t i o n a ld i s p a t c h i n ga l g o r i t h m a n dd i j k s t r aa l g o r i t h ma n dm i n i m a lw a i t i n gt i m ea l g o r i t h m t h i sp a p e re x p r e s s e st h et r a d i t i o n a ld i s p a t c h i n gm e t h o di nm a t h e m a t i cw a y , i n t r o d u c e st h ea p p l i c a t i o no fd i j k s t r a a l g o r i t h mt oo p t i m i z a t i o n a ld i s p a t c h i n go f c o n t a i n e rt r u c ka n de s t a b l i s h e si t sm a t h e m a t i cm o d e l i na d d i t i o n ，t h i sp a p e rp r o p o s e s m i n i m a lw a i t i n gt i m e ( m w a 3a l g o r i t h mi n c l u d i n ge s t a b l i s h m e n to fi t sm a t h e m a t i c m o d e l ，w h i c hc o n s i d e r st h ec o m b i n e dd i s p a t c h i n gp r o c e s so fl o a d i n g ，u n l o a d i n ga n d t r a n s f e r r i n go fc o n t a i n e rt r u c k ，b a s e do nt h em i n i m a lw a i t i n gt i m eo fc o n t a i n e rt r u c k m o r e o v e r , t h i sp a p e rc o m p a r e st h eo p t i m i z a t i o n a ld i s p a t c h i n ga l g o r i t h mw i t ht h e t r a d i t i o n a ld i s p a t c h i n ga l g o r i t h ma n dd e m o n s t r a t e sd i f f e r e n c e sb e t w e e nt h ed i j k s t r a a l g o r i t h ma n dm i n i m a lw a i t i n gt i m ea l g o r i t h m b a s e do nt h ea r e n as i m u l a t i o ns o f t w a r ep a c k a g e ，b yt a k i n gi n t oc o n s i d e r a t i o n p a r a m e t e r so fe q u i p m e n ta n di m p o r t i n ga n de x p o r t i n gf l o wc h a r ti nq i n g d a oo i a n w a n c o n t a i n e rt e r m i n a l ，t h i sp a p e rs i m u l a t e st h et r a n s p o r t i n gp r o c e s so fc o n t a i n e rt r u c k a c c o r d i n gt od i f f e r e n td i s p a t c h i n ga l g o r i t h mm e n t i o n e d t h ep a p e ra n a l y z e sd i f f e r e n t k i n d so fd a t a ，s u c ha st h ed e p l o y i n gn u m b e r , t h es e r v i n ga n dw a i t i n gt i m eo fc o n t a i n e r t r u c ka n di t st r a n s p o r t i n gd i s t a n c eo fas i n g l es h i po rm u l t i - s h i p w h a t sm o r e ，t h i sp a p e r e x p l o r e si n f l u e n c e so nd e p l o y i n gn u m b e ro fc o n t a i n e rt r u c kw h i c hi sc a u s e dt h ev e l o c i t y o ft h ee m p t ya n dh e a v yc o n t a i n e rt r u c ka n ds e r v i n gt i m eo fq u a yc r a n e ，i n v e s t i g a t e st h e o p t i m u ms e r v i n gt i m ea n d s i m u l a t e st h ew o r k i n gp r o c e s so fq i n g d a oq i a n w a nc o n t a i n e r t e r m i n a l t h e r e f o r e ，t h e s ew i l lg u a r a n t e et h eo p e r a t o r st oc h o o s ep r o p e rc o n t a i n e rt r u c k ， q u a yc r a n e a n dy a r dc r a n e a c c o r d i n gt oo u rr e s e a r c h ，t h i sp a p e rp r e s e n t st h ep o s s i b i l i t yo fd e c r e a s e so fs e r v i n g a n dw a i t i n gt i m ea n dt h ed e p l o y i n gn u m b e ro fc o n t a i n e rt r u c k a tt h es a m et i m e ，t h i s p a p e ra l s oi l l u m i n a t e st h ep o s s i b i l i t yo fi n c r e a s e st h er a t e so fe q u i p m e n tu t i l i z a t i o na n d h e a v yr a t e f u r t h e r m o r e ，t h et h r o u g h p u to ft h ec o n t a i n e rt e r m i n a lw i l lb ee n h a n c e d k e yw o r d s ：c o n t a i n e rt r u c k ；o p t i m i z a t i o n ；d i s p a t c h i n g ；a l g o r i t h m ；s i m u l a t i o n 学位论文独创性声明、学位论文知识产权权属声明 学位论文独创性声明 本人声明，所呈交的学位论文系本人在导师指导下独立完成的研究成果。文中 依法引用他人的成果，均已做出明确标注或得到许可。论文内容未包含法律意义上 已属于他人的任何形式的研究成果，也不包含本人已用于其他学位申请的论文或成 果。 本人如违反上述声明，愿意承担由此引发的一切责任和后果。 论文作者签名：弦纱历r 期：踢年f 月4r 学位论文知识产权权属声明 本人在导师指导下所完成的学位论文及相关的职务作品，知识产权归属学校。 学校享有以任何方式发表、复制、公开阅览、借阅以及申请专利等权利。本人离校 后发表或使用学位论文或与该论文直接相关的学术论文或成果时，署名单位仍然为 青岛大学。 本学位论文属于： 保密口，在年解密后适用于本声明。 不保密阢 论文作者签名：双矽番 日期：秒叼年，f 月盆e l 翩摊：f 易军 醐瑚彻肌 ( 本声明的版权归青岛大学所有，未经许可，任何单位及任何个人不得擅自使用) 第一章绪论 1 1 研究背景目的和意义 第一章绪论 1 研究背景 集装箱码头( c o n t a i n e rt e r m i n a l ) 是指在一定空间里，由泊位、岸边起重机( 简 称岸桥) 、龙门吊( 轮胎吊和轨道吊) 、水平运输机械设备( 集装箱卡车) 、堆场、道路、 大门、人员等若干要素相互联系、相互制约的有机整体；是专供停靠集装箱船舶， 装卸集装箱的作业场所，海上运输和陆路运输连接点；它一方面接受( 发送) 由铁路 或公路运来的集装箱，一方面向( 从) 集装箱船装( 卸) 集装箱。集装箱( c o n t a i n e r ) 能长期反复使用，具有足够强度、便于货物的装满和卸空的具有1 m 3 以上容积的容器。 用集装箱运输货物可以保证途中转运不移动箱内的货物，可以直接换装；可以快速 装卸，可从一种运输工具直接方便地装卸到另一种运输工具上。其国际计量单位通 常以度为2 0 英尺为标准，这样标准的集装箱也称国际标准箱t e u ( t w e n t ye q u i v a l e n t u n i t ) ，它表示船舶装载集装箱能力，也是集装箱港口吞吐量的重要统计标准。 据国家统计局调查显示，2 0 0 5 年中国港口完成吞吐量4 9 1 亿吨，同比增长1 7 7 ；完成集装箱吞吐量7 5 8 0 万标准箱，增长2 3 。至2 0 0 6 年底完成吞吐量5 5 7 亿吨，同比增长1 4 8 ，其中沿海港口完成3 5 3 亿吨，同比增长1 7 3 ，内河港口 完成2 0 4 亿吨，同比增长1 0 6 ；全国港口完成集装箱吞吐量9 3 6 1 万标准箱，同 比增长2 3 8 ，沿海港口完成8 5 7 9 万标准箱，同比增长2 2 5 ，内河港口完成7 8 2 万标准箱，同比增长3 9 1 。2 0 0 7 年中国集装箱吞吐量突破1 亿标准箱，业内专家 预测2 0 0 8 年全国港口集装箱吞吐量将达到1 3 亿标准箱左右，较2 0 0 7 年增长1 6 。 为了成为主干线上的集装箱枢纽港，大型集装箱码头必须有预见性地发展港口规模、 航道和水域水深、作业设备尺度和性能、集疏运条件等方面，以适应设想的大型船 舶作业能力，挽留或吸引大型船舶挂靠；把港口系统内各种机械设备有机地结合起 来，从系统化、集成化的角度分析港口系统内的各类机械设备、研究和改进集装箱 码头的机械设备参数，对现有集装箱码头系统更加合理有效的规划与设计，有效地 和高效地满足集装箱运输要求。 集装箱卡车( 简称集卡) 是集装箱码头重要水平运输设备，在装货、卸货、转堆 过程中运用最灵活、数量最大、运载复杂的水平运输机械设备，要想完成整个作业 的高效运载必须合理调度集卡、配置集卡；集卡调度、配置的合理性与否极大地影 青岛大学硕十学位论文 响港口机械设备的装卸速度、港口堆场利用率、港口生产成本等多个方面，极大地 影响着集装箱码头的发展。 2 研究目的和意义 目前水平运输机械设备一集装箱卡车的调度方式是根据码头的实际操作业务量 配置桥吊，对每台岸桥桥吊配备5 6 辆集卡，配备集卡始终为该岸桥服务直至船舶 离开，整个作业过程中岸桥桥吊、集卡、轮胎吊形成一条固定作业路线，集卡沿作 业路顺时间方向运输，司机操作简单，不易出错，但在运输过程中造成运输距离增 加，作业成本上升，集卡在集装箱运输过程中不能被充分调度与利用，集卡空运载 率高，在桥吊或轮胎吊下等待时间过长，不利于提高集装箱码头机械设备利用率等 问题。 本文主要考虑集卡优化调度算法一最短路径法在集卡调度中的应用，以集卡等 待时间为判断依据，提出集卡最小等待时间调度算法。船舶靠港，集装箱经过桥吊、 集卡、轮胎吊一系列机械设备运输；桥吊、集卡、轮胎吊组成运输过程中的各个节 点，提高集装箱码头的吞吐量就是提高各种机械设备利用率。本文所论述的集卡优 化调度算法打破了集卡的传统调度方式，在装货、卸货、转堆一系列需要集卡的运 输过程优化综合调度，集卡任意时刻在多项任务中使用，为桥吊、轮胎吊共享，保 证空闲集卡随时投入其他作业路线中，不仅仅局限在同一条作业路线等待工作，减 少空载率，提高集卡利用率，达到重进重出；同时桥吊也可以调用多辆集卡，而不 局限在分配的5 - 6 辆集卡，桥吊吊起集装箱需要集卡运输，空闲集卡根据集卡不同 优化调度算法为桥吊服务，这种基于最小等待时间算法的集卡优化调度在主要考虑 集卡在桥吊或轮胎吊等待时间，减少集卡等待时间的基础，综合了青岛前湾港实际 数据，集装箱装卸量，计算了集卡行驶时间、距离、集卡空、重载率和集卡利用率， 提高了码头机械设备利用率，减少集卡配置数量；应用a r e n a 仿真软件进行模拟， 证明优化调度算法的合理性与可操作性，服务于生产、提高码头机械设备利用率与 集装箱吞吐量。 从整个码头来看，只有让每一个环节机械设备利用率达到最优，合理调度各种 机械设备，才能给集装箱码头的发展带来巨大变革，获得更大的利润。本文通过模 拟仿真使集装箱码头的使集装箱码头的集卡达到预期的最优调度，有效并高效地满 足集装箱码头运输要求。 1 2 国内外研究动态 2 第一章绪论 1 集卡国内外研究动态 港口集卡调度是一个复杂、随机系统，贯穿于码头、堆场，承担着集装箱位置 转移的作用。国内外对此研究不是很多，在实施方面也不是很理想，真正能用在实 际港口中的更是少之甚少。 国外研究：g o b a l 和k a s i l i n g a m ( 1 9 9 1 ) 堙3 给出基于a g v s ( 自动导引小车) 空闲时间 和集装箱港口装卸设备等待时间仿真模型，求解在满足水平条件下a g v s 需求数量的 最优，主要研究桥吊与轮胎吊的等待时间，对集卡的等待时间研究比较少。k i m 和 b a e ( 1 9 9 9 ) 口1 采用事件发生时间方法研究a g v 的调度问题，利用整数规划和启发式算 法以船舶延误时间和a g v 车辆消耗时问最小为目标分配a g v 车辆。b o s e 等( 2 0 0 0 ) h 1 研 究几条船同时操作，用遗传算法使岸桥的总耽搁时间最短讨论集卡调度优化问题。 c h i n il i u ，h o s s e i nj u l a ，k a t a r i n av u k a d i n o v i c ，p e t r o si o a n n o u ( 2 0 0 4 ) 3 介 绍a g v 在不同结构集装箱堆场运输，应用多属性决策方法评价码头实施情况，计算每 个码头使用a g v 的最优数。v i s 吲利用网络优化模型确定一定任务条件下自动导引小 车的最小数量。o i u 等口3 指出在集装箱码头管理系统中，有效的分派车辆方案的重要 性。d e r - h o r n gl e e ，z h ic a o ，o i a n gm e n g ( 2 0 0 6 ) m 1 主要讨论在两个不同堆放顺序 的堆场中使用模拟退火算法转堆，但在文献中只考虑了转堆过程，没有考虑集装箱 的装、卸过程。y i n g c h i nh o ，h a o - c h e n gl i u ( 2 0 0 6 ) 1 研究多辆a g v 在装箱过程的 调度仿真，主要研究装箱过程，没有考虑卸箱过程。a y o u bi n s ac o r r e a ，a n d r e l a n g e v i n ，l o u i s m a r t i nr o u s s e a u n 们研究了在生产制造系统中的a g v 调度问题与路 径冲突问题，采用混合整数规划算法解决问题，建立相应的解析模型。j o s e p h j m e v e r s 和s t i j na j k o p p e r s ( 1 9 9 6 ) 1 基于自动化设备a g v 导向问题，提出集装 箱码头a g v 车流控制系统，使用信号层次传递方法研究集装箱码头a g v 交通控制问题。 荷兰d u i n k e r k e nm b 等( 1 9 9 9 ) n2 1 3 1 研究a g v s 从码头前沿到堆场的车流控制系统； 2 0 0 1 年又将a g v s 排队运输系统与集装箱堆存模型整合以优化堆场堆存高度、a g v s 数 量，并将研究结果应用于鹿特丹港的自动化集装箱码头。y o n g l e o n gc h e n g ， h o c k - c b a ns e n ，k a r t h i kn a t a r a j a n ( 2 0 0 3 ) n q 基于贪心算法与最小费用流算法提出 a g v 的调度与配置，对a g v 的阻塞问题研究较少。韩国的b y u nj a e - w o o k ，j ok a n g h y u n ，l e ey o u n g s u k n 印提出应用最短路径算法，寻找最短时问路径，建立集卡监控 系统。h a n s - o t t og u n t h e r ，m a r t i ng r u n o w ，m a t t h i a sl e h m a n n 【i 町主要研究自动化集 装箱码头a g v 小车的两种调度策略：o n l i n e 调度与o f f - l i n e 调度算法，研究港口装 卸操作并加以仿真。 国内研究：2 0 0 3 年上海港集装箱股份有限公司曹志伟n 7 1 列举集卡调度系统的优 3 青岛大学硕士学位论文 点，分别讨论以岸桥为目标和集卡为目标，讨论了集卡与桥吊的流程，没建立实际 的数学模型。同年杨静蕾，丁以中n 踟以上海港外高桥集装箱码头为例，研究整个码头 机械设备的最优比，考虑桥吊与轮胎吊的配置，在集卡配置问题研究较少。2 0 0 4 年 上海海事大学关秀光n 们基于b p r 思想集装箱码头集卡作业系统的模拟及优化，帮助港 口经营者确定可靠、经济的港口设备配置与调度方案。2 0 0 5 年上海海勃物流软件有 限公司钱永兴汹3 对t p s 的优点用数字模型进行阐述。同年武汉科技大学的容芷君，张 煜盥研究 6 v 的路径布置及其优化，合理配置、调度、避碰，用遗传算法面向对象p e t r i 网建立a g v 的数学模型。上海海事大学的韩晓龙瞳羽研究集装箱港口装卸作业资源配置 问题并详细地介绍集装箱卡车的配置流程图，给出集卡配置和优化模型。2 0 0 5 年周 鹏飞旺3 1 研究面向不确定环境的集装箱码头优化调度问题，主要研究了泊位一岸桥桥吊 的分配、堆场箱位分配、集卡作业流程，在研究集卡方面将集卡与龙门吊和桥吊结 合在一起，考虑集卡装卸时间、等待时间，但没有考虑在分配过程中，以集卡等待 时间为依据。同年邱跃龙位4 矧研究基于时间p e t r i 网集装箱码头a b v 调度与仿真，主 要研究集卡的调度，将集卡的装、卸过程分开讨论，包括外集卡作业流程，最后使 用w i t n e s s 仿真软件给予仿真过程。2 0 0 6 年张莉、霍佳震啪3 建立了基于码头前沿至堆 场的整体道路网络的单船装卸运输仿真模型，主要研究车速对船装卸时间与效率的 影响。同年大连理工大学张维英，林焰，纪卓尚乜刀应用h o p f i e l d 神经网络模型对集 装箱卡车进行计算机模拟，目的是减少集卡的运行距离，提高集装箱装载效率，主 要考虑集卡行驶距离。武汉理工大学的严政，陶德馨汹1 从探索集装箱堆场机械设备 调度入手，提出了基于动态优化组合的港区内集装箱集卡调度规则，应用作业调度 信息系统和无线局域网络实现集卡作业实时监控和动态优化调度功能，并用离散事 件动态仿真方法进行模拟，验证其有效性。南开大学杨静蕾汹3 以集卡行走距离最短 为目标研究集卡调度。缪强啪对传统作业路存在的不足给予工艺变革，提出两种方 案，并给出文字描述。 2 仿真理论国内外研究动态 国外研究： w o ny o u n gy u n * ，y o n gs e o kc h o i ( 1 9 9 9 ) 汹1 使用面向对象仿真软件 对集装箱码头系统进行仿真，分析在p u s a n 和k o r e a 港口中的应用及执行过程；对整 个码头进行仿真，但对集卡的运行过程没有具体仿真模型。r o n gy e ，v o o n y e ev e e ， w e n j i n gh s u ，s n e h as h a h ( 2 0 0 0 ) b 2 1 对集装箱码头的集卡进行并联仿真，以时间驱 动方法进行建模，运用多线程平行运算程序语言- - c i l k 进行仿真，考虑集卡拥塞现象 与行车路线。a a s h a b a y e k 嘲亏= 2 0 0 2 年采用w it n e s s 仿真软件对香港k w a ic h u n g 集 装箱港口建立仿真模型并对其运输模型加以模拟和改进。e k o z a n m l ( 1 9 9 7 b ) 比较最 4 第一章绪论 优化方法与仿真模型在沿海集装箱港口中的应用，指出对于小型问题，最优化方法 可行，对于大型问题，采用仿真模型更具实际意义。l m g a m b a r d e l l a 等啪瑚1 ( 1 9 9 8 ) 讨论仿真模型在港口资源配置中的应用，运用混合整数规划模型对桥吊等港口资源 进行配置。 国内研究：1 9 9 9 年鲁子爱1 把港口生产视为随机排队服务系统，建立模拟港口 营运状况的计算机仿真系统，开发了用于港口生产调度d d s 和评价港口生产调度c e 改造原则的动态图形仿真系统。2 0 0 2 年北京水运科学研究所的彭传圣嘲1 等利用 a u d i t i o n 开发了集装箱码头模拟系统，研究岸边集装箱起重机、堆场作业设备和集 卡配置，及一定吞吐量港口码头的“瓶颈问题。沙梅1 ( 2 0 0 3 ) 拟用离散系统仿真 模型对集装箱码头工艺系统设计进行建模与仿真。高玮，周强h 们利用排队论对集装 箱码头集卡作业模式进行研究，提出p e t r i 网对集装箱港口物流系统的整体建模思 路，借助于离散事件动态系统仿真语言w i t n e s s 建立集装箱码头物流系统的计算机仿 真模型，利用码头实际营运数据验证仿真模型的可靠性。2 0 0 3 年高玮h 通过w i t n e s s 仿真软件对集装箱码头整个物流系统进行模拟与仿真，主要讨论装、卸船的动态模 型，对桥吊与轮胎吊机械设备讨论较多，对集卡的动态的模型讨论较少。2 0 0 5 年武 汉理工大学周强，吴继红n 2 1 基于离散事件动态系统理论，研究建立了集装箱码头物 流系统的装卸流程模型和道路交通模型，分析评价规划建设中或正在使用中的集装 箱码头生产能力，识别系统中的瓶颈，提出改进策略，优化码头物流方案。2 0 0 6 年 武汉理工大学尚晶，陶德馨h 3 1 提出在数字化技术环境下集装箱码头集卡实时调度规 则。 3 a r e n a 仿真软件研究动态 w d a v i dk e l t o n m 4 5 1 应用a r e n a 仿真软件详细地讨论汽车维修车间模型和小型 制造系统，建立离散与连续相结合模型。2 0 0 0 年西南交通大学陈旭、武振业m 一刀介 绍a r e n a 仿真软件的层次结构体系，讨论了其功能特点及在各个领域的应用，介绍了 基于v b a 和e x c e l ，a r e n a 仿真输出的可视化表达。2 0 0 4 年北京航空航天大学李涛、冯 允成、但蕾“8 用v is u a lb a s ic 实现a r e n a 仿真控制模型，介绍内部控制与外部控制 流程。2 0 0 6 年大连理工大学赵璐、金淳、于越脚1 总结a r e n a 仿真软件的最新进展，结 构、外部接口及将来发展趋势。同年，苗明、郭晓霞、姚夏莉刚介绍基于a r e n a 仿真 软件集装箱港口装卸工艺系统方案，离散事件建模理论对集装箱港口装卸工艺系统 建模与仿真的作用，分析仿真结果得出最优的装卸工艺系统。2 0 0 6 年郭晓霞瞄基于 离散事件仿真技术及排队理论研究港口设备调度方案，使用a r e n a 仿真软件进行优化 仿真。 青岛大学硕士学位论文 如前所述，虽然已有不少学者对港口集装箱系统问题进行了研究，但绝大部分 模型都是经过相当程度的简化，且研究问题局限于某几个环节：桥吊或轮胎吊，对 集卡调度大多数是基于最短路径法，没有充分地考虑集卡的等待时间和集卡的等待 数量。国内应用仿真来研究集装箱码头的深度和广度与国外相比较，还有一些差距， 尤其是在一些较复杂的集装箱码头的集卡调度问题上。本课题采用a r e n a 仿真软件， 对港口集装箱码头集卡调度系统仿真模拟，是一项应用于实际的有价值研究。 1 3 研究内容及创新点 1 研究内容 通过对集装箱码头集卡调度分析、建模、仿真，采用青岛前湾港实际参数分析 仿真结果，具体研究内容如下： ( 1 ) 集卡系统分析：分析集装箱码头平面布局、装卸机械设备，集卡调度传统算 法一作业路法，着重分析青岛前湾港集装箱码头进、出口流程图： ( 2 ) 集卡优化调度算法研究：对集卡调度的传统方式用数学公式加以表达；研究 最短路径法在集卡调度上的应用，建立数学模型及求解过程；提出基于最小等待时 间的集卡优化调度算法：以集卡最小等待时间为判断依据，整体考虑集卡优化调度， 建立数学模型，减少集卡等待时间、集卡配置数量，充分利用集卡，提高集卡利用 率； ( 3 ) 基于a r e n a 仿真软件对集卡调度进行模拟与仿真：运用a r e n a 仿真软件，以 集卡调度传统算法、最短路径法、最小等待时间算法为基础，对集装箱码头船舶、 岸桥桥吊、轮胎吊、集卡等主要随机事件进行模拟仿真； ( 4 ) 综合青岛前湾港集装箱码头运输各种因素：船到港时间、桥吊服务时间、集 卡运输速度、轮胎吊服务时间、集装箱数量、堆场平面图等等，模拟集卡运输过程， 分析集卡不同调度算法单船与多船的集卡配置数量、等待时间、运输时间、行驶距 离等等参数；考虑集卡的空、重载速度及岸桥桥吊服务时间的变化对集卡配置数量 的影响，为港口作业人员合理选择集卡提供可靠保证。 2 创新点 ( 1 ) 建立了最短路径法集卡优化调度数学模型；以集卡等待时间为判断依据，提 出了基于最小等待时间的集卡优化调度算法，并进行了理论推导； ( 2 ) 理论与实践相结合，基于a r e n a 仿真软件，采用青岛前湾港实际数据，分析 讨论集卡在不同调度算法下的配置数量、运输时间、等待时间等等各个参数；分析 6 第一章绪论 集卡空、重载速度及岸桥桥吊服务时间在不同集卡调度算法中对集卡配置数量的影 响； ( 3 ) 对仿真结果进行了深入分析和讨论，分析了集卡空、重载速度及岸桥桥吊服 务时间与集卡配置数量的关系，得到了集卡空、重载速度及岸桥桥吊服务时间的最 优值，证明了最短路径法与最小等待时间算法优于集卡传统调度算法。 本文主要研究集卡调度环节，通过不同的集卡调度算法使集卡配置达到最优， 仿真模拟应用于青岛前湾港，满足青岛前湾港集装箱卡车的调度与码头运输要求。 7 青岛大学硕士学位论文 第二章集卡优化调度算法 2 1 集卡调度的传统方式及其算法 集卡是集装箱码头重要的水平运输设备，是在岸桥桥吊与堆场轮胎吊之间及堆 场与堆场之间运输集装箱的机械设备。目前集卡的传统调度方式是根据码头的业务 量配置桥吊，按着桥吊台数配备一定集卡数量，集卡始终为该岸桥桥吊或轮胎吊服 务直至船舶离开，操作比较简单，不易出错，但其弊端在于集卡在集装箱运输过程 中不能被充分调度与利用，不利于集装箱码头扩展。 2 1 1 集卡调度的传统方式 船靠泊后，港口调度人员根据船配载图、集装箱进、出口数量、堆场贝位图等 配置机械设备，也就是说当船舶到港时，判断是装船还是卸船，根据集装箱量为船 配置岸桥桥吊与轮胎吊，依据桥吊数，每台桥吊配备5 6 辆集卡，集卡按规定作业 路线沿顺时针方向运输，集卡始终为该桥吊、轮胎吊服务直至船离开泊位。整个装 卸过程中桥吊、轮胎吊和集卡形成固定作业线路( 如图2 1 所示) 运输集装箱。 图2 1 集卡调度传统方式 优点：司机操作比较简单，沿着单一作业路线不易出错啪1 ；缺点：集卡配置数 量依靠调度经验，中控室二十四小时实时监控，实时现场调配，浪费大量人力、物 力，缺乏集卡的灵活调度。若集装箱运输量小，造成集卡在运输过程中等待时间过 长，影响集卡利用率；集装箱运输量过大造成集卡欠缺，致使生产衔接不上，岸桥 桥吊服务时间与轮胎吊服务时间都将影响集卡的配置与调度，传统调度方式很难满 足集装箱码头的快速发展，合理地调度集卡、改进集卡调度算法是当务之急。 8 第二章集卡优化调度算法 2 1 2 集卡调度的传统方式数学模型 传统调度算法是现场调度人员，按着桥吊配置数量，每台桥吊配置5 或6 辆集 卡，统一作业路线运输集装箱，传统调度方式集卡配置数量为： t r o u 。i + i m , i ) c o n 8 ( 辆) 集卡总服务时间为： ( q c ) + y c ( j ) ) 事n 1 6 0 m 毒t r 集卡等待时间为： 集卡的总服务时间一集卡运行时间 集卡空载率为： 集卡运输空载时间( 集卡空载运输时间+ 集卡重载运输时间) 。 即r r ( i ) 。( r r ( i ) 。+ r r q ) 。) ) 宰1 0 0 现实运输过程中集卡空载率达到5 0 。集装箱总量非常小，n 保持不变，桥 吊被充分利用，导致多辆集卡仅仅服务于几个或几十个t e u ，将会造成部分集卡浪 费；集装箱总量无限大，集卡配置数量仅仅局限于桥吊个数，产生少数集卡服务 于多个集装箱，集卡在运输过程中，空、重载速度不变，空载率保持不变，桥吊服 务时间不变，高速运输集装箱，导致桥吊等待集卡现象。 综上所述，在实际操作过程中，集卡总服务时间与集卡的等待时间过大，集卡 配置数量不合理，岸桥桥吊会发生等待集卡现象，集卡也会在码头前沿或堆场中排 队等待装卸集装箱，空闲集卡等待集装箱现象比较严重，交通堵塞情况时有发生。 2 2 基于最短路径法的集卡优化调度算法 鉴于集卡传统调度算法一固定作业路法导致集卡空载率过高，集卡利用率低，本 节将最短路径法应用在集卡的优化调度模型中，打破传统固定作业路线安排集卡的 方式，动态地将装货、卸货、转堆一系列需要集卡的运输过程进行综合调度，集卡 在任意时刻根据路径距离的选择在多项任务中使用，为桥吊、轮胎吊共享；随时投 入到其他作业路线中，而不仅仅局限在同一条固定作业路线等待工作，减少空载率， 提高集卡利用率，达到重进重出。 9 青岛大学硕士学位论文 2 2 1 基于最短路径法的集卡优化调度算法数学模型 最短路径法眦 驺3 也称为d i j k s t r a 算法，在一个非负权值图找到两个指定节点间 最短路径，也可以找到从给定的一个源顶点到所有其他顶点的最短路径。集卡在调 度过程中，遵循最短路径法进行优化调配。起始点( 桥吊或轮胎吊) 依据最短路径调 度算法总是选择离本起始点路径最短集卡为其服务，减少集卡的总行驶路程，减少 集卡配置数量，提高集卡利用率。缺点：集卡在调度过程中易产生阻塞状态，多辆 集卡选择一台桥吊或轮胎吊，导致集卡等待时间过长，调度混乱。 集卡在行驶过程中考虑水平运输距离最短，不考虑集卡维修、保养成本及集卡 在等待装卸集装箱发生的油耗、损耗成本，集卡通过最短路径法选择桥吊或轮胎吊 运输集装箱。集卡配置数学模型：鼍一l o r o ，1 表示集卡i 选择对应桥吊或轮胎吊服 务，给予分配；0 表示集卡f 没有选择桥吊或轮胎吊服务，不给予分配。 目标函数为： ， 打- 毛 i e l i - i 2 一( 1 ) c 一善1 荟k 荟j ( 舰叫砷r 砂宰m i n ( s 疆 + ( 触州嗍蛐慨 + j f l 8 9 i p r i o r i t y m t n s 让 + # a g | ( p r i o r i t y - o 章m i n s o 】 2 一( 2 ) 约束条件为： 善荟善肭+ 删( f ) 弦+ 胁a ) 矗。i l 瓯- i # a g l 枣乃o ) 一+ l t l a g - 1 1 n o ) 一匕 & 一i 堙 奉乃a ) 4 。痂。匕+ i 夕妇一1 毒打a ) i 。黼搴屹 乃o ) 一打( f ) 2 + t q o ，k ) + s a f e 打( f ) 一a a ) 乞乙+ t q ( i ，j ) + s a f e n ( f ) ：一一打a 碓钿 n ( f ) 一打( f ) 名 1 0 2 一( 3 ) 2 一( 4 ) 2 - ( 5 ) 2 一( 6 ) 2 一( 7 ) 第二章集卡优化调度算法 毛一 三篇 2 一c 8 ， 毛2 1 0 不分配集卡 z 弋浏 2 一( 1 ) 和2 - ( 2 ) 为目标函数，其中2 一( 1 ) 计算集卡配置数量；2 一( 2 ) 计算集卡行驶 的最短距离。2 一( 3 ) - 2 - ( 8 ) 为约束条件，其中2 一( 3 ) 表示集卡的运输次数和与所需要 运输的集装箱数量相等；2 一( 4 ) 计算集卡到轮胎吊的运输距离；2 一( 5 ) 计算集卡到桥 吊的运输距离；2 一( 6 ) 集卡计划到达轮胎吊或桥吊的时间等于集卡完成上一循环的运 输时间与集卡到达本桥吊或轮胎吊时间之和，s a f e 为集卡阻塞因子：2 一( 7 ) 集卡运输 过程中无阻塞现象；2 一( 8 ) 集卡配置数量变量。 2 2 2 基于最短路径法的集卡优化调度算法求解过程 l 。最短路径法啼2 峭1 求解步骤 从屹出发，逐步向e 寻找最短路。执行过程中，给每一个顶点予以标号：p 标 号为永久性标号，一旦某点得到p 标号，其值在整个求解过程中不再改变；t 标 号为临时性标号或试探性标号，r 标号的值会随着求解过程而改变。具体步骤如下： 给起始点吒标上尸标号，尸( h ) 1 0 ，即d “，h ) 一o ；其余各点标上丁标号， r o ，) t + o o ，s 为已经标记p 标号点的集合，即s 一似 ，s = 屹，屹，屹。 设u 是刚刚得到p 标号的点，所有与u 相邻的点y j ，化，v j ) 彳，r v j 的标号为 r 标号，修改 ，的丁标号使得r o ，) - m i n t ( v a p o ，) + ；对于所有与吩不相邻的 点y ，其z 标号值保持不变。 若d 中没有z 标号点，则算法终止，即已求得从起始点b 到各点的最短路径。 否则，t ( v j o ) f f i m i n t ( v j ) ；若有多个r o j ) 最小，则任取其一，然后将点y 扣的r 标 号修改为p 标号，转入第二步。 d i j k s t r a 算法每一步修改z 标号，某一点的z 标号改为p 标号，最多经过n l 步( n 为图d 中的顶点数) ，求解出从起点到各点的最短路径。 2 基于最短路径法的集卡优化调度算法求解过程 青岛大学硕士学位论文 依据船运输配载图，集装箱数量，装、卸状态，桥吊、轮胎吊服务时间，桥吊 位置，堆场人员确定运输的集装箱堆放b l o c k 及堆场平面图。桥吊定义为，堆场 b l o c k 所服务轮胎吊定义为y ，集卡定义，h ，屹屹。根据上述集卡最短路径法调 度算法，首先考虑( ，唯，y ，) 是否存在( 即判别集卡、桥吊和轮胎吊是否存在路径) ， 考虑集卡到达指定位置的路径和轮胎吊、桥吊的服务时间，若存在，再取( u ，屹， ，；) 是否存在，如果也存在，将( ，v k ，) 与( h ，h ，) 进行比较取出最短距离 岛，岛 或 叉，& ) 所对应的集卡或h ，再进一步取集卡( 屹，咋， ，) 依次进行比较，最终取 出最短距离对应的( 屹，唯，y ，) ，将屹集卡分配给桥吊心与轮胎吊y ，之间运输集装箱。 在整个调度过程中，配置集卡是基于最短路径调度算法，也就是说集卡优先配 置给行走距离最短的桥吊或轮胎吊为其服务，会产生某一时刻所有集卡到达某一 b l o c k 或桥吊的距离最短，导致集卡堵塞在某一b l o c k 或桥吊中等待运输，不利其 他作业路集卡的均衡调度，某一瓶颈点阻塞，集卡等待时问过长。 2 3 基于最小等待时间算法的集卡优化调度研究 最短路径法应用在港口集卡调度以运输路径为参考依据，易产生多辆集卡阻塞 状态，集卡根据集卡行驶距离选择一台桥吊或轮胎吊为其服务，导致集卡在某点等 待时间过长，调度混乱，产生瓶颈。本节提出新的优化调度算法一基于最小等待时间 算法的集卡优化调度，以集卡的等待时间为判断依据调度、配置集卡。打破传统固 定作业路方式，解决基于最短路径法的集卡瓶颈问题，集卡优先选择等待时间最短 的桥吊或轮胎吊作业路为其服务，理论分析论证基于最小等待时间集卡调度算法优 于集卡传统调度算法及基于最短路径法集卡调度算法。优点：保证集卡、桥吊、轮 胎吊等待时问最短；最大限度调度集卡，减少集卡配置数量，降低集卡空载率，提 高集卡利用率，减少道路交通堵塞；提高码头机械设备利用率，缩短船在泊停靠时 间，提高装、卸船准确率。 2 3 1 基于最小等待时间算法的集卡优化调度优先级 ( 1 ) 空闲集卡优先选择人为干预作业路线； 第二章集卡优化调度算法 ( 2 ) 空闲集卡优先选择重点船、重点作业路线； ( 3 ) 码头前沿空闲集卡优先选择卸船作业路线； ( 4 ) 堆场空闲集卡优先选择装船作业路线； ( 5 ) 码头前沿集卡完成装船作业路线优先选择卸船作业路线； ( 6 ) 堆场中集卡完成卸船作业路线后优先选择装船作业路线； ( 7 ) 当装卸船作业路线达到平衡时，空闲集卡选择转堆作业路线； ( 8 ) 当三条作业路达到平衡，也就是集卡等待时间均等，集卡选择路径最短作业 路线。 2 3 2 基于最小等待时间算法的集卡运输状态图 集卡运输四种状态：堆场重载、堆场空载、码头重载、码头空载。如图( k 表示 岸桥桥吊，j 表示堆场轮胎吊) ： f l q = o p l a g = l f l a s = 2 图2 2 堆场重载 f l a g = o f l a g = l f l a 商 f l a u = o f l a g = l f l a f 2 图2 3 堆场空载 图2 4 码头重载图2 5 码头空载 图2 2 堆场重载，集卡在堆场中，由轮胎吊j 提箱放入集卡，集卡选择到指定 桥吊装船或到指定堆场b l o c k 中转堆；图2 3 堆场空载，集卡在堆场