（计算机应用技术专业论文）集装箱码头物流优化调度关键技术研究.pdf

摘要 随着集装箱运输的快速发展，港口要不断研究新技术，优化码头的物流系统， 以提高竞争力。本文在分析集装箱码头传统作业方式的基础上，研究了集装箱卡车 的路径优化以及岸桥调度的模型，并且应用蚁群算法对集装箱卡车的路径进行优化， 然后采用遗传算法对岸桥的调度模型进行求解。 在分析集装箱码头的作业流程及其传统作业工艺的基础上，改变集装箱卡车路 线相对固定的约束，以集装箱卡车到达目的地的距离最短为目标，建立集装箱卡车 的路径优化数学模型，使用蚁群算法为码头集装箱卡车寻求出发点与目的地之间的 最短路径，以缩短集卡的行走距离。算例分析表明，该方法能够有效解决集卡的最 短路径搜索问题，从而减少岸桥等待集卡的时间，提高码头装卸设备的利用率； 分析了集装箱码头岸边桥式起重机的调度问题，考虑同一轨道的岸桥不能相互 交叉、不同岸桥的台时效率不同等实际因素，以岸桥的作业时间最短为目标，建立 符合实际的岸桥调度模型；并使用遗传算法对本研究提出的岸桥调度模型进行了求 解，通过计算给出的算例得知，遗传算法可以有效地求解本文的岸桥调度模型，减 少岸桥的服务时间，从而缩短船舶的在港时间，提高码头的运作效率。 通过本文的研究能够缩短集卡的行走距离、岸桥的服务时问以及船舶的在港时 间，提高码头各种装卸设备的利用率，进而提高整个集装箱码头的吞吐量。 关键词：集卡：岸桥；物流优化；蚁群算法；遗传算法 a b s t r a c t w i t ht h er a p i dd e v e l o p m e n to fc o n t a i n e r i z a t i o n , t h ep o r to w n e r s n e e dt om a k e s c i e n t i f i cr e s e a r c h e so nn e w t e c h n o l o g yf o rt h es a k eo ft h eo p t i m i z a t i o no ft h el o g i s t i c s s y s t e ma n dt h ei m p r o v e m e n to ft h ea b i l i t yf o rc o m p e t i t i o n i nt h i sp a p e r ，t h ep r o c e s so f c o n t a i n e rt e r m i n a lo p e r a t i o n sa n dt h e 仃a d i t i o n a lm o d ew e r ea n a l y z e d ，a n dt h e nt w o q u e s t i o n sa r ei l l u s t r a t e d ，o n ei st h er o u t i n go p t i m i z a t i o nf o rc o n t a i n e rt r u c k s ，t h eo t h e ri s t oe s t a b l i s ht h ed i s p a t c h i n gm o d e lf o rq u a yc r a n e si nt h ec o n t a i n e rt e r m i n a l f i n a l l y , t h e a n tc o l o n yo p t i m i z a t i o na n dg e n e t i ca l g o r i t h ma r er e s p e c t i v e l yu s e dt os e e kt h e s o l u t i o no ft h et w om o d e l sw h i c ha r ea b o u tt h er o u t i n go p t i m i z a t i o nf o rc o n t a i n e rt r u c k s a n dt h ed i s p a t c h i n go ft h eq u a yc r a n e si nt h ec o n t a i n e rt e r m i n a l b a s e do nt h ea n a l y s i so ft h ep r o c e s so fc o n t a i n e rt e r m i n a lo p e r a t i o n sa n dt h e t r a d i t i o n a lm o d e ，t h er o u t i n go p t i m i z a t i o n , w h i c ht a r g e t si nt h em i n i m u mr o u t eo f c o n t a i n e rt r u c k si so nt o po fp r e s e n t e d t h em o d e li st os e e kt h es h o r t e s tr o u t eo f c o n t a i n e rt r u c k sw h i c ht r a v e l sf r o mt h es o u r c et ot h ed e s t i n a t i o n ，a n dt h ea n tc o l o n y o p t i m i z a t i o ni su s e dt os o l v et h em o d e l i ti sp r o v e db yt h ee x a m p l e st h a tt h ep r o b l e mf o r t h ec o n t a i n e rt r u c k st os e a r c ht h es h o r t e s tp a t hc a nb es o l v e dw i t ha n tc o l o n ya l g o r i t h m e f f e c t i v e l y a f t e r w a r d s ，t h et r a d i t i o n a ld i s p a t c h i n gm o d eo ft h ec o n t a i n e rq u a yc r a n e si s p r e s e n t e d , t h e n ，t h ea c t u a lf a c t o r so ft h eq u a yc r a n e sa r et a k e ni n t oa c c o u n ta n dt h e d i s p a t c h i n gm o d e lw h i c ht a r g e t si nt h em i n i m u ms e r v i n gt i m eo ft h eq u a yc r a n e si s e s t a b l i s h e d a f t e rt h a t , t h eg e n e t i ca l g o r i t h mi sa p p l i e dt os e e kt h es o l u t i o no ft h em o d e l i ti si n d i c a t e db yt h ee x p e r i m e n t st h a tt h ea l g o r i t h mc a ns o l v et h em o d e lw h i c hi s e s t a b l i s h e di nt h et e x te f f e c t i v e l y ，d e c r e a s et h es e r v i n gt i m eo ft h eq u a yc r a n e sa n dt h e t i m ei np a r to ft h es h i p s ，a n du l t i m a t e l yt 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 li s e n h a n c e d a c c o r d i n gt oo u rr e s e a r c h ，t h ep o s s i b i l i t yo fd e c r e a s e so fc o n t a i n e rt r u c k s t r a n s p o r t i n gd i s t a n c e ，t h es e r v i n gt i m eo ft h eq u a yc r a n e sa n dt h et i m ei np a r to ft h e s h i p sw e r ep r e s e n t e d f u r t h e r m o r e ，t h er a t eo fu s i n gt h ee q u i p m e n ta n dt h et h r o u g h p u to f t h ec o n t a i n e rt e r m i n a la r 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 ；q u a yc r a n e ；l o g i s t i c so p t i m i z a t i o n ；a n tc o l o n y o p t i m i z a t i o n ；g e n e t i ca l g o r i t h m 学位论文独创性声明、学位论文知识产权权属声明 学位论文独创性声明 本人声明，所呈交的学位论文系本人在导师指导下独立完成的研究成果。文中 依法引用他人的成果，均已做出明确标注或得到许可。论文内容未包含法律意义上 已属于他人的任何形式的研究成果，也不包含本人已用于其他学位申请的论文或成 果。 本人如违反上述声明，愿意承担由此引发的一切责任和后果。 论文作者签名：黝鼢日期：砷年岁月，。日 学位论文知识产权权属声明 本人在导师指导下所完成的学位论文及相关的职务作品，知识产权归属学校。 学校享有以任何方式发表、复制、公开阅览、借阅以及申请专利等权利。本人离校 后发表或使用学位论文或与该论文直接相关的学术论文或成果时，署名单位仍然为 青岛大学。 本学位论文属于： 保密口，在年解密后适用于本声明。 不保密 ( 请在以上方框内打“4 ) 论文作者签名：葛鼢翰 导师签名： ( 本声明的版权归 日期：m 7 年岁月，。日 日期：纠年歹月尸日 所有，未经许可，任何单位及任何个人不得擅自使用) 4 7 第一章绪论 1 1 研究背景目的和意义 第一章绪论 1 1 1 研究背景 集装箱运输是指把多种多样的杂货集装于具有统一长、宽、高规格的箱体内进 行运输。集装箱可以通过铁路、公路和水路运输。集装箱具有坚固、密封的特点， 使用集装箱既可以避免箱内货物受到损坏，又可以简化包装，节约包装费用，降低 运输成本；货物装入集装箱并铅封后，运输途中不需要拆箱倒载，所以采用集装箱 运输不易损坏箱内货物，能够降低货损率；由于集装箱装卸受气候影响较小，所以 集装箱运输能够缩短车船的停留时间，加快车船周转，提高装卸效率；采用集装箱 运输，有利于机械化操作，减轻繁重的体力劳动，同时降低对人的安全威胁。集装 箱运输完全改变了传统运输方式劳动强度大、周转慢、装卸效率低、货损货差大等 缺点。 港口是交通运输的枢纽、是水陆联运的咽喉，海洋和主要内河干线的轮船和拖 驳船队载重量大，航道航线通过能力所受的限制小，运输成本也较低，主要担负大 宗、笨重货物的长途运输。随着经济全球化速度的加快，越来越多的资源配置过程 和生产经营活动在整个世界范围内进行，现代港口在社会经济发展中的作用与地位 也因此发生了深刻的变化，成为一个国家经济能否有效地参与经济全球化并保持在 国际竞争中主导地位的重要依托。 近年来，集装箱运输已经遍及全球，船舶以较快的速度朝着大型化方面发展。 我国集装箱运输是从2 0 世纪5 0 年代开始起步的，随着我国国民经济的快速发展， 对外贸易和外向型经济的不断发展，我国集装箱运输发展很快。近年来我国国际集 装箱运输船舶运量年均增长2 9 2 ，港口吞吐量以平均2 7 左右的速度递增。2 0 0 5 年，中国内地已拥有1 0 个亿吨港口，即上海、宁波、广州、天津、深圳、青岛、秦 皇岛、大连、南京、苏州；其中上海港2 0 0 5 年的货物吞吐量达到4 4 3 亿吨，首次 超过新加坡港，成为世界第一货运港口。2 0 0 6 年1 1 月2 5 日和1 2 月1 8 日山东日照 港和江苏南通港先后成为中国内地新的亿吨大港，截至2 0 0 6 年底，中国内地已拥有 1 2 个亿吨大港。目前，中国是世界上拥有亿吨港口最多的国家，也是世界上港口吞 吐量和集装箱吞吐量最大的国家。 尽管受到全球经济减速、我国宏观经济以及外贸出口下滑的影响，2 0 0 8 年沿海 青岛大学硕士学位论文 港口总吞吐量、外贸吞吐量以及集装箱吞吐量的相对增幅有一定幅度的下降，沿海 港口吞吐量增速已经进入下降通道，但是其绝对增量仍处于高位2 0 0 8 年1 8 月份， 全国规模以上港口完成国际标准集装箱吞吐量8 3 5 7 6 万t e u ( t w e n t y f e e te q u i v a l e n t u n i t ，标准箱) ，比2 0 0 7 年同比增长1 6 0 ，增速最快的是连云港“，营口和广 州分别是4 7 和2 9 ，其中沿海港口完成7 7 2 0 1 万t e u ，同比增长1 5 5 ，内河港 口完成6 3 7 5 万t e u ，同比增长2 2 9 。表1 1 所示为来自交通运输部的2 0 0 8 年9 月份中国主要港口的集装箱吞吐量及总量。 表1 12 0 0 8 年9 月中国主要港口集装箱吞吐量及总量 吞吐量( 万t e u ) 港口 2 0 0 9 年9 月2 0 0 9 年1 - 9 月同比增长( ) 全国总计1 0 7 4 5 59 4 4 7 8 91 1 4 9 大连4 0 33 3 4 4 21 2 2 4 天津7 3 2 26 2 2 1 71 1 9 1 青岛8 3 9 47 5 1 8 91 0 7 3 上海2 3 52 1 0 8 41 0 9 宁波舟山港9 6 2 28 1 5 8 41 1 7 厦门4 1 83 7 9 7 61 1 2 1 深圳2 5 31 6 2 3 0 91 0 8 1 广州7 8 0 58 4 9 6 81 2 4 6 随着集装箱运输的发展，港口之间的竞争也变得越来越激烈。港口的竞争因素 不仅包括港口的地理位置和腹地经济条件，港口的机械设备、作业效率、技术条件 和管理水平也是体现其竞争力的重要因素。港口要在新一轮的竞争中取得优势，需 要为船舶的装卸提供一个良好的物流作业平台，而实现这一目标的唯一有效途径就 是优化港口物流系统的调度。在这种背景下，合理地规划集卡行走路径和改进岸桥 的调度方式成为港口增强竞争力的关键。要真正提高港口的作业效率，集装箱码头 还需要在码头的设施和设备配置、高新技术的应用、机械和车辆的操作、设备和车 辆的调度管理和生产组织水平的提高等方面做出努力。 1 1 2 研究目的和意义 集装箱运输是一种先进的现代化运输方式，是一个复杂的运输系统工程，具有 2 第一章绪论 多个优点，发展迅速，尤其是港口码头集装箱运输。目前世界各地主要集装箱码头 都面临着吞吐量急剧增长的压力，为进一步降低运输成本，港口采用越来越大的集 装箱船舶，在一个港口装卸的集装葙量就会增加，而与此同时，却要保持船舶的在 港时间不变，这样，集装箱港口为增强竞争力，提高装卸作业效率的压力也越来越 大。港口为缓解压力，配置大量人员、车辆和堆场，导致管理难度和营运成本大幅 增加。影响集装箱港口效率和效益的因素有很多，其中包括装卸设备资源的配置， 堆场空间的安排，泊位、岸桥和集卡的分配与分派，以及港口机械的路径选择。 潞露瓣 港口集装箱码头由岸边桥式起重机( 简称岸桥) 、泊位、集装箱龙门起重机( 简 称龙门吊) 、水平运输设备一集装箱卡车( 简称集卡) 、堆场等组成。图l _ 1 所示为 集装箱码头的现场图。其中集装箱卡车是集装箱装货、卸货、转堆过程中的运输设 备，在码头与堆场间作集装箱水平运输，集装箱卡车的行走路线、运行时间与码头 的运作效率、岸桥的利用率、港口装卸速度等具有极为密切的关系：岸桥是在码头 前沿进行集装箱装卸作业的装卸设备，承担着连接水陆运输的集装箱装卸作业任务， 是制约集装箱码头作业效率的主要瓶颈，是其他优化问题的重要基础及主要约束条 件。集装箱运输的增长，集装箱运输船舶的大型化、高速化趋势，要求码头全面提 高装卸能力和集疏运能力，配备高效、合理的装卸工艺系统，而集装箱卡车的路径 优化及岸桥的调度则是关键点。 青岛大学硕士学位论文 目前，大部分港口采用传统的固定作业路的集卡作业模式，一般情况下，按照 一定的比例为岸边桥式起重机配备集卡数量，如青岛前湾港，根据码头的实际操作 业务量，对每台岸边桥式起重机配备5 6 辆集卡，配备的集卡与对应的岸边桥式起 重机组成条作业路，在调度过程中，行车路线相对固定。这种作业模式便于管理 与考核，不容易发生错误，但是在集卡行走过程中，半圈为重载，半圈为空载，造 成资源浪费，并且由于集卡的路径固定，有可能造成某条作业路堵塞，降低集卡的 速度，延长了岸桥、龙门吊的等待时间，降低岸桥、龙门吊的利用率，从而影响码 头的作业效率。 另外，在我国，许多大的集装箱港口，经常发生船舶压港现刻3 0 1 ，有两个重要 的原因，方面是由于物流发展迅速，而目前我国港口的容量和设备跟不上发展的 需要，另个重要的原因就是港口的资源没有得到科学合理的使用，设备利用率较 低，导致港口的服务能力降低。而装卸运输活动是港口的主要活动，岸桥的装卸能 力和速度直接决定码头的作业效率，是决定集装箱码头吞吐能力的主要因素之一。 因此，集装箱港口岸桥的合理调度对集装箱港口的运作效率起着至关重要的作用， 基于这种考虑，国内外很多学者对岸桥调度问题进行了研究。这对于优化集装箱港 口的资源配置，合理安排资源，降低运营成本，拓宽其业务范围，提高港口的服务 水平和竞争能力，都具有非常重要的意义。 从整个码头来看，只有让各个环节的机械设备得到充分利用，合理调度各种机 械设备，使其协调运作，才能使集装箱码头更快地发展，从而获得更大的利润。 1 2 国内外研究动态 1 2 1 集卡路径优化国内外研究动态 集装箱卡车是港口码头集装箱运输的主要设备，它的行走路径影响岸桥的利用 率，关系到码头的运作效率，因而逐渐成为国内外研究的热点之一。 国外关于集卡路径优化的研究：1 9 9 9 年t e o d o r o v i cd 【1 】指出了集卡作业线模式 的缺点，不能动态调配各条作业线的集卡，导致集卡空驶严重，造成设备利用率低 下；同年k i mkh 和b a ejw1 2 】建立了混合整数规划模型，研究将集装箱分配给集 卡的调度问题；2 0 0 0 年s i m c h i l e v id 等1 3 】以船舶在港时间最小为目标，建立了基于 车辆的集装箱港口集卡分派模型，并给出了启发式算法；2 0 0 3 年e b r uk 和b i s h l 4 l 以集装箱运输船在港周转时间最小化为目标，研究集装箱装卸顺序问题和集装箱与 集卡的配对问题，采用t l s ( t r a n s s h i p m e n tp r o b l e mb a s e dl i s ts c h e d u l i n gh e u r i s t i c ) 4 第一章绪论 启发式规则求解；d ek o s t e rr ，l ea n ht ，v a n d e rm e e rjr 1 5 】使用启发式算法来确定 最佳的集卡数量和疏运路径，并通过实例说明了该规则的优越性；d i r ks ，s t e f a nv ， r o b e r ts 1 6 】指出按照关键设备的作业效率计算出的系统额定效率是5 0 - 6 f f 陋u h ，而目 前实际作业中大多数港口采用面向作业线的静态调度的模式，导致集装箱集疏运系 统的效率远远达不到额定标准，只能达到2 2 3 0 t e u h 。 国内关于集卡路径优化的研究：徐承军和陶德馨【7 1 分析了传统集卡运作模式的 不足，提出了一种新的面向作业面的动态集卡运作模式，对动态调度中最复杂的单 集卡多作业路选择工况，采用多目标模糊决策算法和层次分析法进行了研究，并结 合算例阐明了最优工作路选择的过程：刘海威、黄有方和史建民1 8 1 分析了模糊自动 控制的原理和模糊控制器的设计，并将模糊控制应用于集卡调度系统中，以实现集 卡在码头范围内的智能调度，集卡实际运行时根据具体条件查询系统通过离线模糊 计算产生的智能调度决策查询表就能够很好地满足码头实际生产的需要；邱跃龙和 陶德馨1 9 】提出了利用时间p e t r i 网对集卡调度系统( t r a c t o rp a g i n gs u b s y s t e m ，简称 1 1 p s ) 建模和性能分析的基本思路：韩晓龙和丁以中【l o 】分析了采用面向作业面和装 卸同时进行工艺的集装箱港口中桥吊、集卡和龙门吊的装卸作业流程，将装卸过程 中设备事件分为l i f t i n g 、d r o p p i n g 、m o v i n g 、w a i t i n g 和v i r t u a l 五类，采用v b 6 0 编 程实现了基于事件驱动的集装箱港1 3 装卸作业仿真系统；张维英、林焰和纪卓尚i l l j 以场内集卡将码头堆场集装箱送到岸桥所运行的距离最短为目标，建立配载模型并 应用h o p f i e l d 神经网络模型进行计算机模拟，提高集装箱装卸效率；曹志伟【1 2 j 介绍 了集卡调度系统的产生、优点及优化t p s 的设想，t p s 的应用大大提高了码头的集 装箱作业效率，改变了装卸模式；缪强【1 3 】针对传统作业工艺的不足，提出两种方案： 集卡查找任务的方式实现集卡全场自动分配和任务查找集卡的方式实现集卡全场自 动分配；张海霖、江志斌和许泓【1 4 】提出了基于规则的方法实现集装箱集疏运系统的 实时动态调度，利用w i t n e s s 仿真工具分别模拟了面向作业线的静态调度和面向 作业面的动态调度两种集装箱集疏运调度模式，为集装箱码头调度问题的研究提供 了新思路和新方法；曾庆成和杨忠振【1 5 l 建立了集装箱码头作业调度双层规划模型， 上层为岸桥调度优化模型，下层为集卡动态路径模型，通过上下层模型间的反馈与 相互作用决定集装箱码头作业调度的整体优化方案，设计了基于遗传算法的求解方 法，并应用实际算例对模型和算法的有效性进行了验证；尚晶和陶德掣16 j 在集装箱 码头传统作业模式的基础上，提出了在数字化技术环境下的码头集卡实时调度规则， 并建立了这两种调度模式的动态仿真模型：高玮和周强【1 7 l 利用排队论对集装箱码头 集卡作业模式进行了研究，建立了仿真模型，并对两种集卡作业模式进行了试验研 5 青岛大学硕士学位论文 究；蔡芸、王少梅和严武元1 1 明应用仿真优化方法研究了某集装箱码头前沿布局中泊 位数、岸桥及集装箱卡车配备数量、岸桥陆侧轨外侧作业通道数等因素对作业过程 及码头通过能力的影响，开发了参数化仿真模型，该模型可生成不同集装箱码头前 沿布局方案，建立了仿真结果数据库和多目标多层次的方案综合评价指标体系，把 遗传算法与系统仿真相结合，求得了最优方案；杨静蕾【1 9 l 根据集装箱码头的工艺流 程，在满足集装箱堆场堆存要求和船舶装卸作业要求的情况下，以集卡行走里程最 短为目标，求解集卡最优行走路径。 蚁群算法是一类较新的仿生类算法，大多数国内外学者对集卡路径优化的研究 很少使用蚁群算法，本文在国内外学者研究的基础上，将蚁群算法应用于集装箱码 头，改变传统作业工艺中集卡固定作业路的状况，以集卡行走距离最短为目标，建 立集卡路径优化模型，为集卡寻求出发点与目的地之间的最短路径。 1 2 2 岸桥调度国内外研究动态 随着集装箱运输船舶大型化的蓬勃发展和技术进步，集装箱岸桥科技含量越来 越高，不断更新换代，逐渐朝着大型化、高速化、自动化和智能化，以及可靠性高、 寿命长、能耗低、环保型方向发展。在集装箱码头装卸设备中，岸桥是港口集装箱 装卸的主力设备，它的作业顺序在很大程度上制约着码头内其他设备的调度，集装 箱港口岸桥的合理分配和调度对集装箱港口的运作效率起着至关重要的作用，因此， 岸桥的优化是关键问题，基于这种考虑，国内外很多学者对岸桥调度问题进行了研 究。目前，国内外学者针对岸桥优化问题建立了数学模型，并且发展了求解模型的 算法。 国外关于岸桥调度的研究：2 0 0 4 年k i mkh 和y o u n g m a np a r k l 2 0 1 为岸桥调度 问题建立了一个混合整数规划模型，并分别用分枝定界法、贪婪随机适应性搜索算 法进行求解，最后比较了两种算法的实际效果：n gwc 和m a kkl 【2 1 l 对堆场岸桥调 度进行了研究，为了提高港口吞吐量，以最小化任务的等待时间为目标建立模型， 利用分枝定界法对模型进行了有效的求解，算例表明，该算法能够找到最优顺序； y o u n g m a np a r k 和k i mkh i 冽对泊位和岸桥调度问题建立了整数规划模型，提出了 两阶段方法，第一阶段运用次梯度法确定每个船舶的停泊位置和时间，获得一个近 似最优解，在第二阶段应用动态规划方法为每个岸桥建立详细的调度时间表；a v r i e l m 【2 3 l 和s h i e l d sj j l 2 4 】对到港船舶的装卸箱过程进行模拟，研究了港口集装箱岸桥的调 度问题，同时通过模拟还可以帮助制定堆场计划以减少翻箱率：p e t e r k o f s k y 和 d a g a n z o 研究了在静态情形下以最小化总体船舶的延迟时间为目标的岸桥调度问 6 第一章绪论 题，并提出用各种精确的启发式算法来解决岸桥调度问题1 2 - q 1 2 6 1 。 国内关于岸桥调度的研究：2 0 0 5 年交通部水运科学研究所彭传圣i 刃j 分析了影响 码头作业效率的因素，介绍我国集装箱码头刷新船时作业效率记录的情况，指出宜 以一段时间泊位作业效率、船时作业效率和岸边桥式起重机作业效率的统计平均值 作为集装箱码头作业效率的度量和比较指标；2 0 0 6 年大连海事大学曾庆成和上海交 通大学高宇【勰l 研究岸桥调度优化问题，以提高集装箱码头装卸效率，首先，建立了 混合整数规划模型，该模型充分考虑了集装箱岸桥调度优化中的各种约束条件及特 点，为了求解，设计了基于遗传算法的求解方法，并且采用随机贪婪适应性搜索方 法对算法进行改进，最后，通过实际算例对模型与算法的有效性进行了验证；同年 清华大学王辉球1 2 9 l 在深圳盐田国际集装箱港口实地考察和文献调研的基础上，建立 了符合实际的集装箱岸桥调度模型，该模型充分考虑了岸桥不可相互穿越和作业时 必须保持一定安全距离的实际约束；2 0 0 7 年上海海事大学杨阳【删建立了以最短路径 为目标函数、无碰撞为约束条件的集装箱装卸操作最优路径的单目标数学模型。 集装箱运输的快速发展要求港口不断改进技术、提高运作效率，而岸桥的分配 和调度与港口效率的提高关系极为密切，国内外很多学者对其进行了研究，清华大 学王辉球1 2 9 l 对岸桥调度的研究没有考虑岸桥的台时效率不同等因素，本文在其研究 的基础上，分析了岸桥的调度问题，考虑岸桥的台时效率不完全相同等更多的因素， 建立更加符合实际的岸桥调度模型，并使用自适应遗传算法进行优化，以减少岸桥 的作业时间，提高港口的运作效率。 1 3 研究内容及创新点 1 3 1 研究内容 本文主要研究了集装箱码头物流优化调度的两个关键问题： 第一，在分析集装箱码头作业流程及其传统作业工艺的基础上，以集装箱卡车 到达目的地的距离最短为目标，建立集装箱卡车路径优化模型，提出了使用蚁群算 法，为码头集装箱卡车寻求出发点与目的地之间的最短路径。算例分析表明，该方 法能有效地解决集卡的最短路径搜索问题，从而减少岸桥等待集卡的时间，提高码 头装卸设备的利用率； 第二，描述了码头集装箱岸桥的调度问题，以岸桥的作业时间最短为目标，考 虑同一轨道的岸桥不能相互交叉、岸桥之间须保持一定的安全距离等情况，做出假 设，建立符合实际的岸桥调度模型；并分别使用自适应遗传算法和传统遗传算法对 7j 青岛大学硕士学位论文 第三章提出的岸桥调度模型进行求解，通过对算例进行运算，证明遗传算法能够有 效地求解本文的岸桥调度模型，自适应遗传算法能够加快收敛速度、避免陷入局部 最优解，在较短时间内求得最优解，缩短岸桥的作业时间，从而缩短船舶在港时间， 提高码头的效率。 1 3 2 创新点 本研究的创新点如下： 第一，改变集卡路线相对固定的状况，建立集卡路径优化模型，使用蚁群算法 求解，优化集卡的行走路径，缩短集卡的行走距离，从而减少岸桥的等待时间，提 高岸桥的利用率； 第二，考虑岸桥作业的实际情况，建立岸桥调度模型，并使用自适应遗传算法 对其进行求解，克服传统遗传算法收敛慢、易陷入局部最优解的缺点。 通过本文的研究能够减少集卡的行走距离、岸桥的等待时间、缩短船舶的在港 时间，提高码头各种装卸设备的利用率，进而提高整个集装箱码头的吞吐量。 近年来，集装箱卡车路径优化问题和岸桥的合理调度已成为国内外研究的热点 之一，本课题主要研究的就是如何合理地规划集装箱卡车的行走路径及岸桥的调度 问题，建立模型并求解，结果表明，本文提出的集卡路径优化模型能够有效地减少 集卡的行走距离，岸桥的合理调度也有效地缩短了船舶的在港时间，提高装卸设备 的利用率，从而提高港口整个码头的运作效率。 8 第二章基于蚁群算法的集卡路径优化 第二章基于蚁群算法的集卡路径优化 随着物流业的迅猛发展，集装箱运输业面临极大的挑战，随着港口货运量的增 长、船舶的大型化，码头为降低成本、增强竞争力，不断研究新技术、加强对系统 的管理，各集装箱港口码头十分重视自身竞争力的提高，对集装箱码头的信息化管 理愈加关注，集装箱码头的运作效率，已成为国内外研究的热点之一。根据集装箱 码头的运作流程，集装箱码头运作效率的研究大致上可以分为：锚地和泊位资源的 优化配置研究1 3 1 1 3 2 】、装卸设备的优化配置研究l 冽1 3 3 1 、物流路径优化研究【3 4 l 【3 5 1 【蚓和 堆场资源的优化配置研究1 3 7 】【蚓等。其中，集装箱码头物流路径优化的研究非常复杂， 既包括集装箱操作量的优化，还涉及到装卸设备的路径优化，由于集装箱卡车的路 径与码头的效率有密切的关系，所以逐渐成为国内外研究的热点，如德国的 s t e e n k e n 3 9 l 等运用启发式算法研究了集卡在集装箱码头的运输路径安排问题，韩国 的b y u n i 删等采用最短路径算法，寻找集卡行走时间最短的路径；南开大学杨静蕾1 1 9 j 以集卡的行走里程最短为目标，建立了集卡的路径优化模型，为集卡求解最优的行 走路径；大连理工大学张维英等 1 1 l 以码头集卡将堆场集装箱送到岸边桥式起重机所 运行的距离最短为目标，建立了配载模型并运用h o p f i e l d 神经网络模型进行计算机 模拟。 目前，大部分港口采用传统作业工艺，司机操作比较简单，不容易出错，便于 管理与考核，但是随着科学技术的进步、港口物流业的发展，这一模式的弊端逐渐 暴露，集卡分配给某一岸桥后，沿固定的路径行驶，导致集卡利用率低下，还可能 发生交通堵塞，而且一旦发生堵塞，会对码头的运作效率带来很大的影响。要提高 码头的吞吐量，就需要打破传统作业工艺的束缚，为集卡选择合理的行走路径。本 文提出基于蚁群算法的集卡路径优化模型，使集卡选择行走距离最短的路径。 2 1 集装箱卡车传统作业工艺 港口集装箱码头由岸边桥式起重机、泊位、龙门吊、集卡、堆场等组成。其中 岸桥、集卡、龙门吊是港口最主要的机械设备，集装箱装卸作业需要这三种设备相 互配合、协调，形成统一的整体，集装箱码头装卸作业系统非常复杂，具有多个环 节而且并发性很强，是多维空间作业的离散事件系统。集装箱码头具有合理的平面 布局以及集装箱装卸工艺，才能保证完整高效的运作，否则会出现岸桥、龙门吊等 待集卡或者集卡等待岸桥、龙门吊等现象，影响码头的运作效率，而集卡是集装箱 9 青岛大学硕士学位论文 装货、卸货、转堆过程中的运输设备，在码头与堆场间作集装箱水平运输，衔接码 头前沿岸桥和后方龙门吊的工作，是码头作业系统中的重要环节，是提高码头整体 效率的关键设备，只有令集卡行驶路径的安排适合岸桥和龙门吊的装卸，才能确保 整体效率的提高。 目前，大部分港口采用大陆码头普遍采用的传统作业工艺，岸桥集卡场地设 备工艺组织装卸船作业，岸桥对到达港口的船舶进行装卸作业，场地设备( 龙门吊) 对堆场的集装箱进行进出场作业，集卡则完成码头与堆场间的集装箱水平运输任务。 集装箱码头装卸工艺流程如图2 1 所示： _ 卸船装船 图2 1 集装箱码头装卸工艺流程 一般情况下，由几辆集卡固定搭配组合成一组集卡，按照一定的比例为每台岸 边桥式起重机分配一定数量的集卡，一般某个特定的组合里集卡相对固定，进行作 业的岸桥也相对固定，最多也只是在卸船作业中，可以不固定集卡和岸桥的对应关 系，由集卡司机根据经验以及岸桥下卸船集卡的等待数量，选择岸桥下等待的集卡 数量相对较少的岸桥进行服务，来平衡作业线，例如，青岛前湾港，按照码头的实 际操作业务量，为每台岸桥分配5 6 辆集卡，分配的集卡与岸桥组成一条作业路， 在调度过程中，集卡按照固定的路径行走，配备的集卡始终为该岸桥服务，直到工 作终止( 见图2 2 ) 。在卸船作业中，岸桥将集装箱放置到在岸桥下等待卸船的空车 集卡上后，集卡沿固定的路线重载行驶到指定的堆场箱区内卸下集装箱，然后再空 载行驶到岸桥下等待下一个卸船作业。在装船作业中，龙门吊将堆场箱区的集装箱 放在集卡上后，集卡重载行驶到岸桥下等待装船，装船完成后集卡再空载行驶到堆 场箱区进行下一个装船作业。这种作业方式，便于管理及考核，不容易出错，但是 随着物流业的发展，这一模式的弊端逐渐暴露：第一，某条作业路上的集卡配置量 是一个固定值，配置少了可能会出现岸桥等待集卡的现象，造成前方码头作业区的 瓶颈；配置多了又容易产生资源浪费，导致资源利用率低下，一条作业路由于某种 原因效率低下时，此作业路下有可能出现集卡在排队等待，而此时其他作业路可能 集卡还不够用，致使生产衔接不上，会存在作业时间比较紧张的作业路得不到空闲 1 0 第二章基于蚁群算法的集卡路径优化 _ 重载匕= 空载 图2 2 码头集装箱卡车传统作业工艺 的集卡，造成集卡资源不能充分利用，影响港口的运作效率；第二，传统作业工艺 中，集卡固定地为某一岸桥服务，仅局限于一条“作业路 ，即集卡在完成一次作业 如装船、卸船或者转堆后，必须空载回到堆场或者码头，然后进行下一次作业，这 样造成集卡空载率较高，集卡利用率低下，运行能源消耗大，使单个集装箱的作业 能耗成本大大提高；最后，集卡沿着固定的路径行驶，当码头上集卡数量过多时， 集卡运输可能发生交通堵塞，而且一旦发生堵塞，会对码头的运作效率带来很大的 影响。 传统作业工艺有其优点，也存在不足，如果只是简单地通过增加集卡来解决矛 盾的话，同样会引发交通流量和场地管理问题。本文打破传统作业工艺中固定集卡 行走路径的束缚，基于蚁群算法建立集卡路径优化的模型，为集卡选择合理的行走 路径，使其行走距离最短，以提高集卡的效率。 2 2 蚁群算法 蚁群算法( a n tc o l o n yo p t i m i z a t i o n ，a c o ) ，又称蚂蚁算法，是由意大利学者 青岛大学硕士学位论文 d o r i 9 0 1 4 l 】等于1 9 9 1 年首先提出来的，是一种受到自然界生物的行为启发而产生的 “自然一算法，是一种用来在图中寻找优化路径的现代启发式算法，其灵感来源于 蚂蚁在寻找食物过程中发现路径的行为。蚁群算法具有许多优良的性质，为求解优 化问题提供了新的思路，在一系列困难的组合优化问题如旅行商、二次指派等问题 求解中取得了成效。 2 2 1 蚁群算法的基本原理 蚁群算法的基本原理来源于蚂蚁在寻找食物过程中发现路径的行为。研究表明， 在一个复杂的环境中，蚂蚁能够发现从蚁巢到食物源的最短路径，有效地找到食物， 把食物搬回家，而且这种最优路线具有灵活适应性，当食物的位置稍微更改的时候， 蚂蚁群体还是能够根据环境的变化而变化，搜索新的路径，产生新的选择。研究发 现，这是因为，蚂蚁在寻找食物时，能在其走过的路径上分泌一种被称为“信息素 的化学物质到环境中去，蚂蚁个体正是通过这种信息素来进行信息传递，随后的蚂 蚁具有感知这种信息素浓度的能力，而且能够根据信息素的浓度来选择自己要前进 的方向，但是这种信息素的浓度会在自然环境下随着时间过去而慢慢挥发掉，由于 走较短路径的蚂蚁能够很快返回巢穴，来回一次的时间短，并且它会马上再按原来 的路径继续搬运食物，所以在这条短路径上释放的信息素就会更多，因此，较短路 径上的信息素浓度比较长路径的浓度更高，而浓度高的信息素会吸引更多的蚂蚁， 那么这条路径上的信息素就会越多，从而形成一种正反馈。通过这种正反馈，蚂蚁 群体最终可以找到最短路径。 如图2 3 所示，蚂蚁到达分支点后，选择走哪条路，开始时如图2 3 ( a ) ，由于 两条线路上均没有蚂蚁通过，在这两条路线上都没有信息素气味，因此蚂蚁u ， l 2 ，r 1 ，r 2 选择两条线路的机会均等。令蚂蚁l 1 选择a c d 线路，蚂蚁l 2 选择 a b d 线路，蚂蚁r l 选择d b a 线路，蚂蚁r 2 选择d c a 线路，如图2 3 ( b ) 所示。 假设蚂蚁移动的速度相同，由于线路a c d 比线路a b d 短，所以当蚂蚁l 1 、r 2 均 到达终点时，蚂蚁i _ 2 、r 1 还在途中，而下一个蚂蚁也有两条路选择，哪一条线路 上信息素的气味重就选择哪一条，如图2 3 ( c ) 所示。如此继续下去，沿a c d 线路 上移动的蚂蚁越来越多，如图2 3 ( d ) ，这就是a 到d 的最短路线，蚂蚁根据线路 上留下信息素浓度的大小，确定在路线上移动的方向，蚂蚁群体向信息素浓度重的 线路集聚的现象称为正反馈。蚂蚁算法正是基于正反馈原理的启发式算法。 1 2 第二章基于蚁群算法的集卡路径优化 a c ( a ) b d b da c ( b ) b d 图2 3 蚁群算法的过程 c ( d ) d 2 2 2 蚁群算法的特点 蚁群算法的特点综合起来有以下三个方面i 蚓： 第一，自组织。 蚂蚁群体寻找食物的过程并没有受到外在的指令，而是蚁群内部自发的行为规 则。从初期的无序个体寻找食物、经过时间的推移、内部信息素的传递、蚁群觅食 规则变得有序：按照最短路径往返于蚁巢与食物源的最短路径上。 第二，多样性。 蚂蚁觅食的初期是在无规则的平面上随机地寻找食物源，而且蚂蚁在觅食过程 中不会在一个范围内无限的循环下去，总是能够在有限的过程中找到新的路径，沿 着食物源方向行进。这就保证了蚂蚁觅食过程中走过路径的多样性，多样性是找到 最佳觅食路径的有效保证。 第三，正反馈。 单只蚂蚁的觅食行为不能够保证找到食物源和最佳路径，群体的协作是蚂蚁找 到食物和路径的保障。信息素的正反馈传递为蚂蚁觅食提供了寻找合适路径的信息， 随着对信息学习的增强和正反馈作用的加大，蚂蚁逐渐行进在最优的道路上。 1 3 青岛大学硕士学位论文 自组织性保证了蚂蚁觅食行为从无序到有序的过程，多样性保证了蚂蚁在觅食 的时候能够走出死循环和避开障碍，正反馈机制则保证了相对优良的信息能够被保 存下来，正是这三点巧妙结合才使得蚂蚁寻找到最优觅食路径。 蚂蚁群体是一种社会性昆虫，它们不但有组织、有分工，而且具有通讯系统， 它们相互协作，能够完成寻找从蚁巢到食物源最短路径的复杂任务。模拟蚂蚁群体 智能的人工蚁群算法具有分布计算、信息正反馈和启发式搜索的特点，在求解组合 优化问题和连续时间系统的优化中获得了广泛的应用。 蚁群算法首先是针对旅行商问题提出的，后来逐渐应用到众多复杂的实际问题 中，包括车辆路由、二次指派、背包问题、车间任务调度问题( j s p ) 以及网络路由 等，并且取得了一系列较好的实验结果【4 3 4 4 j 【钢。国内也涌现了许多与蚁群算法相关 的学术成果1 4 6 】1 4 7 1 ，在某些具体问题中，蚁群算法的性能更是达到甚至超越了用于该 问题的其他经典的求解算法。 2 3 基于蚁群算法的集卡路径优化模型 蚁群算法具有许多优良的性质，为求解优化问题提供了新的思路，在一系列困 难的组合优化问题如旅行商、二次指派、车间任务调度及网络路由等问题求解中取 得了成效。近来也逐渐被引入到人工智能的路径规划之中，该算法通过对自然界生 物行为的模拟，能够在全局范围内动态确定车辆的最佳行走路线，以提高整个系统 的质量和效率。本文的集卡最短路径搜索问题属于组合优化问题，和t s p 等经典的 组合优化问题具有很大的相似性，传统的求解最短路径问题的方法并不十分合适， 根据这一特点，本文用求解组合优化问题的启发式方法蚁群算法来求解集卡的最 短路径问题。 假设有m 辆集卡，均从船舶a 向1 2 个箱区运送集装箱，d 盯表示泊位( 或堆场) f 与堆场( 或泊位) f 之间的距离。每个箱区的位置和将要运送到此箱区的集装箱数 量一定，每辆集卡的装箱数量一定，并且每辆集卡都从码头前沿出发，每个箱区只 有一辆集卡服务，但这辆集卡可以服务多个箱区。 由此建立的目标函数为： c m i n x x f s d o f o ，1 ，力；j = o ；1 ，。j l 2 一( 1 ) p若集卡经过路段1 5 f ，歹) 嘞。10 ，否则 1 4 2 一( 2 ) 第二章基于蚁群算法的集卡路径优化 为使用蚁群算法求解集卡的最短路径，引进以下标记：设o ) 表示f 时刻路段 ( f ，) 上的信息素强度，那么第k 只蚂蚁选择o ，j f ) 这条边的概率可表示为： 露o ) t夏t即j q ) r 0 7 0 ) p ， j a