(交通信息工程及控制专业论文)基于GAAA算法的码头集卡优化调度研究.pdf_第1页
(交通信息工程及控制专业论文)基于GAAA算法的码头集卡优化调度研究.pdf_第2页
(交通信息工程及控制专业论文)基于GAAA算法的码头集卡优化调度研究.pdf_第3页
(交通信息工程及控制专业论文)基于GAAA算法的码头集卡优化调度研究.pdf_第4页
(交通信息工程及控制专业论文)基于GAAA算法的码头集卡优化调度研究.pdf_第5页
已阅读5页,还剩45页未读, 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

中文摘要 摘要 集装箱卡车( 简称集卡) 是在集装箱码头起重要作用的一种水平运输设备,在 卸下货物、装载货物、转堆的过程中运用极其灵活、具有很大规模的数量、运载 过程较为复杂。因此我们只有合理调度集卡、并对集卡进行优化配置,才能使整 个作业过程能够高效的运载:集卡的调度、优化配置的合理性与否能够极大地推动 堆场的利用率、影响堆场的生产成本等多个方面、并且还能影响堆场的机械设备 的装卸速度,因此对集装箱码头的发展有着极大的影响。 论文首先介绍遗传算法和蚁群算法的概念、特点,以及每种算法的不足,然 后提f 采用遗传蚁群十l j 融合的g a a a 算法,该算法能够避丌遗传算法和蚁群算法这 两种算法的缺点,更好的发挥各自的优势。 其次论文重点研究了集卡的动念实时调度,包括实时调度的原则、实时调度 的原理以及动念实时调度算法的基本步骤。并且本文针对目自i 研究现状的不足提 出了拥塞的定义,并在考虑搠塞的条件下对集卡的动念实时调度进行了研究。 最后,本论文还着重研究了g a a a 算法在集卡优化调度中的应用,确定了可行 点集,以及信息素的更新策略和路径点的选择方法,并将信息熵引入蚁群算法, 把信息熵作为算法终止的准则,提高算法的运行速度,实现自适应调节。本文运 用m a t l a b 和w i t n e s s 对实时调度算法进行仿真,其结果表明本文提出的集卡实时 调度策略是合理可行的,对提高码头资源的利用率有明显的作用。本文研究成果 为集装箱码头改进作业调度提供了可靠的科学依据。 关键词:集装箱卡车;调度;仿真 英文摘要 a b s t r a c t c o n t a i n e rt r u c k si nt h ec o n t a i n e rt e r m i n a l sp l a ya ni m p o r t a n tr o l ei nl o a d i n g , u n l o a d i n ga n ds h i f t i n gc a r g o ,w i t hal a r g en u m b e ra n dc o m p l i c a t e dt r a n s p o r tp r o c e s s e s t h e r e f o r e ,o n l yr e a s o n a b l ed i s p a t c ha n do p t i m i z e dc o n f i g u r a t i o no f c o n t a i n e rt r u c k sc a n g u a r a n t e et h ee f f i c i e n c yo ft h ew h o l et r a n s p o r t a t i o np r o c e s s a l s o ,t h ef e a s i b i l i t yo f o p t i m i z e dd i s p a t c hf o rc o n t a i n e rt r u c k sc a np r o m o t et h eu t i l i z a t i o no fc o n t a i n e ry a r d s a n dt h eh a n d l i n gv e l o c i t yo ft h em e c h a n i c a le q u i p m e n ta n dr e d u c et h ep r o d u c t i o nc o s t o fc o n t a i n e ry a r d s ,s oi th a sa g r e a ti n f l u e n c eo nt h ed e v e l o p m e n to fc o n t a i n e rt e r m i n a l s t h i sp a p e rf i r s ti n t r o d u c e st h ec o n c e p ta n dc h a r a c t e r i s t i c sa sw e l la st h ed e f i c i e n c y o ft h ea n tc o l o n ya l g o r i t h ma n dt h eg e n e t i ca l g o r i t h m t h e np r o p o s et h eg a a a a l g o r i t h mc o m b i n i n gt h eg e n e t i ca l g o r i t h ma n dt h ea n tc o l o n ya l g o r i t h m t h ea l g o r i t h m c a na v o i dt h es h o r t c o m i n g so ft h eg e n e t i ca l g o r i t h ma n da n tc o l o n ya l g o r i t h m ,a n dp l a y t h e i rr e s p e c t i v ea d v a n t a g e s s e c o n d ,t h i sp a p e rm a i n l ys t u d i e st h ed y n a m i cd i s p a t c h i n go ft h ec o n t a i n e rt r u c k s , i n c l u d i n gt h ep r i n c i p l e s , t h e o r i e s ,b a s i cp r o c e d u r e sa n da p p l i c a t i o no ft h eg a a a a l g o r i t h m c o n g e s t i o ni sa l s or e f e r r e dt oi n t h i sp a p e r , i n c l u d i n gi t sd e f i n i t i o n , t h e f e a s i b l ep o i n t sd i s t r i b u t i o n ,t h eu p d a t es t r a t e g yo fp h e r o m o n ea n dt h es e l e c t i o nm e t h o d s o fp a t hp o i n t s f i n a l l y , t h i sp a p e rs h o w st h es i m u l a t i o ne x p e r i m e n tb a s e do nm a t l a ba n d w i t n e s sa l g o r i t h ma n dt h ea n a l y s i so ft h er e s u l t s t h er e s u l t ss h o wt h a tt h e p r o p o s e ds e to fc a r d sr e a l t i m es c h e d u l i n gp o l i c yi sf e a s i b l e ,i m p r o v i n gt h eu t i l i z a t i o n o ft e r m i n a lr e s o u r c e s ,s i g n i f i c a n tr o l e t h i sr e s u l t so ft h ec o n t a i n e rt e r m i n a lp r o v i d e sa r e l i a b l es c i e n t i f i cb a s i st oi m p r o v ej o bs c h e d u l i n g k e yw o r d s :c o n t a i n e rt r u c k s ;d i s p a t c h i n g :s i m u l a t i o n 大连海事大学学位论文原创性声明和使用授权说明 原创性声明 本人郑重声明:本论文是在导师的指导下,独立进行研究工作所取得的成果,撰写 成博士硕士学位论文二基于g a a a 算法的码头集卡优化调度研究二。除论文中已 经注明引用的内容外,对论文的研究做出重要贡献的个人和集体,均已在文中以 明确方式标明。本论文中不包含任何未加明确注明的其他个人或集体己经公开发 表或未公开发表的成果。 本声明的法律责任由本人承担。 论文作者签名:绚久硷“b 年f 月刁日 l 学位论文版权使用授权书 本学位论文作者及指导教师完全了解“大连海事大学研究生学位论文提交、 版权使用管理办法 ,同意大连海事大学保留并向国家有关部门或机构送交学位论 文的复印件和电子版,允许论文被查阅和借阅。本人授权大连海事大学可以将本 学位论文的全部或部分内容编入有关数据库进行检索,也可采用影印、缩印或扫 描等复制手段保存和汇编学位论文。 保密口,在年解密后适用本授权书。 本学位论文属于:保密口 不保密i ( 请在以上方框内打“4 ) 论文作者签名:哥移文甭 日期:硼 一7 弘歹 基于g a a a 算法的码头集卡优化调度研究 第1 章绪论 1 1 课题意义 集装箱码头( c o n t a i n e r t e r m i n a l ) 就是指那些在一定空间里,由泊位、轨道吊、 集装箱卡车、堆场、岸边起重机( 岸桥) 、轮胎吊、道路、大门、人员等若干有密 切关系的要素相互制约、相互联系所组成的有机整体:是对集装箱进行装卸的作 业场所,专供停靠集装箱船舶,而且还是陆路运输和海上运输的关键的连接点: 它一方面从( 向) 集装箱船舶装( 卸) 集装箱,一方面发送( 接受) 由铁路或公路运送 而来的集装箱。集装箱( c o n t a i n e r ) 是能够长期反复使用的,具有i m 3 以上容积 的,并且有利于货物的装满和卸空;具有足够的硬度和强度的容器。用集装箱来 对货物进行运输可以保证箱内的货物在途中和在转运的途中不移动,既可以快速 装卸:又可以直接换装,可从一种运输工具方便而又直接地装卸到另外一种运输 工具上n 儿胡副。 集装箱卡车( 简称集卡) 是在集装箱码头起重要作用的一种水平运输设备,在 卸下货物、装载货物、转堆的过程中运用极其灵活、具有很大规模的数量、运载 过程较为复杂。因此我们只有合理调度集卡、并对集卡进行优化配置,才能使整 个作业过程能够高效的运载:集卡的调度、优化配置的合理性与否能够极大地推 动堆场的利用率、影响堆场的生产成本等多个方面、并且还能影响堆场的机械设 备的装卸速度,因此对集装箱码头的发展有着极大的影响h 引。 1 2 国内外研究动态 堆场集装箱卡车的优化调度贯穿于整个码头、堆场,是一个复杂的随机系统, 转移集装箱位置的重要作用也由集装箱卡车的优化调度来承担。近年来,国际上 的很多著名的集装箱码头都致力于堆场移动设备最优路径的研究【刀f 8 】1 9 】,以图通 过堆场设备的行驶距离,提高效率,节约成本。然而,在我国集装箱码头在路径 优化方面仍以经验管理为主。所以在集卡调度中,进行路径优化算法的研究就显 得十分重要【1 0 1 。 第1 章绪论 1 2 1 国外研究动态 国外研究:1 9 9 1 年e o b a l 和k a s i l i n g a m 主要研究了桥吊与轮胎吊的等待时 间,但是对集卡的等待时间研究比较少,他们主要做了在满足水平条件下a g v s 需求数量的最优的求解工作,并且给出了基于a g v s ( 自动导引小车) 空闲时间的 仿真模型,也给出了集装箱堆场装卸设备等待时间的仿真模型。 1 9 9 9 年k i m 和b a e 以船舶延误时间和a g v 车辆消耗时间最小为目标,利用 整数规划和启发式算法分配a g v 车辆。他们是采用事件发生时间方法研究a g v 的调度问题。次年b o s e 等讨论集卡的调度问题,几条船同时操作进行了研究, 为了使岸桥的总耽搁时间最短,b o s e 等学者运用了遗传算法。 。2 0 0 4 年c h i n il i u ,h o s s e i n 比肠,k a t a r i n a v u k a d i n o v i e ,p e t r o s x o a n n o u , 在评价码头实施情况时应用了多属性决策方法,计算每个码头使用a g v 的最优 数。 2 0 0 6 年y i n g e h i n h o ,h a o e h e n g l i u 主要研究装箱过程,没有考虑卸箱过 程他们研究多辆a g v 在装箱过程的调度仿真。同年,o e r h o r n gl e e ,z h i e a o , q i a n gm e n g 运用模拟退火算法在两个不同堆放顺序的堆场中转堆,但他们没有 考虑集装箱的装、卸过程,只考虑了转堆过程。 a y o u b i n s a c o r r e a ,a n d r e l a n g e v i n ,三伽西一m a r t i n r u s s e a 采用混合整数规 划算法解决问题,建立相应的解析模型,他们研究了在生产制造系统中的a g v 调 度问题与路径冲突问题, 1 2 2 国内研究动态 国内研究:2 0 0 3 年上海港集装箱股份有限公司曹志伟分别讨论以岸桥为目标 和集卡为目标,讨论了集卡与桥吊的流程,列举集卡调度系统的优点,但是并没 有建立实际的数学模型。 2 0 0 5 年邱跃龙将将集卡的调度作为自己的主要研究工作,在研究的过程中 将集卡的装、卸过程分开讨论,包括外集卡作业流程,最后使用w i t n e s s 仿真软 件给予仿真过程。 同年周鹏飞主要研究了泊位岸桥一桥吊的分配、堆场箱位分配、集卡 作业流程,在研究集卡方面时,周鹏飞将集卡与龙门吊和桥吊结合在一起进行研 2 基于g a a a 算法的码头集卡优化调度研究 究。但是在周鹏飞的研究中没有考虑在分配过程中,以集卡等待时间为依据,考 虑集卡装卸时间。 2 0 0 6 年大连理工大学张维英,林焰,纪卓尚为了提高集装箱装在效率,减 少集卡的运行距离,对集装箱卡车进行计算机模拟。在模拟的时候应用h o p f i e l d 神经网络模型。 武汉理工大学的严政,陶德馨为了实现集卡作业实时监控和动态优化调度功 能,他们应用了作业调度信息系统和无线局域网络,他们还提出了基于动态优化 组合的港区内集装箱集卡调度规则,在提出集卡调度规则时从探索集装箱堆场机 械设备调度入手,最后为了验证其有效性,用离散事件动态仿真方法进行模拟。 南开大学杨静蕾以集卡行走距离最短为目标研究集卡调度。缪强对传统作业 路存在的不足给予工艺变革,提出两种方案,并给出文字描述。 1 3 研究目标及内容 1 3 1 研究目标 本研究针对目前堆场资源的有限性和实际吞吐能力需求大幅增长的矛盾,以 及目前国内外的研究现状的不足,针对堆场的具体情况,欲采用一种新的有效的 动态实时调度算法,以达到对堆场的集装箱卡车进行更加合理的调度和优化,来 提高堆场的实际吞吐能力和装卸效率,减少船舶在港时间和费用,提升堆场的竞 争能力,吸引更多船舶靠港。 1 3 2 研究内容 ( 1 ) 对集卡系统进行分析:对集装箱码头装卸机械设备、平面布局分别进行分 析,并且分析集装箱卡车的调度的传统方式。 ( 2 ) 集卡优化调度算法研究:运用g a a a 算法进行调度优化;g a a a 算法是一 种由蚁群算法和遗传算法相融合的算法【1 1 1 【1 2 1 ,是进行路径优化的一种智能算法, 本文利用该算法适用于组合优化的优越特征,针对于集卡调度的要求,考虑拥塞 情况,采用g a a a 算法进行路径优化研究,以期望从根本上降低集卡的等待时间, 整体考虑集卡优化调度,提高集卡利用掣1 3 】【1 4 】【15 1 。 3 第1 章绪论 1 4 研究方法及技术路线 本文采用一种新的有效的动态实时调度算法。首先利用遗传算法的随机搜 索、快速性、全局收敛性来产生有关问题的初始信息素分布。然后,充分利用蚁 群算法的并行性、正反馈机制以及求解效率高等特征。这样融合后的算法,是在 时间效率和求解效率都比较好的启发式算法。将这种遗传算法与蚁群算法( a n t a l g o r i t h m ,从) 融合的算 蝴c n n n 算法【1 6 】【1 7 1 。i i 阻c a a a 算法已经在其他领 域的优化中得到应用。 在考虑车辆最优路径时,由于道路网络的交通状况处在动态变化过程中,即 使是最优路径,车辆也应以当前位置为起点,根据当前路网情况,重新计算到达 目的地的最优路径【擂】;驾驶员无法获得全面的交通信息,如果最优路径只是空间 最短路径,个体的最优策略势必造成大量的车辆向最短路径蜂拥而去,产生拥塞 现象。所以最优线路不是空间距离最短,而是考虑了某些支路的阻塞情况下选择 的路线最短的线路1 1 9 3 2 0 1 。 4 基于g a a a 算法的码头集卡优化调度研究 2 1 遗传算法 第2 章遗传算法及蚁群算法 2 1 1 遗传算法的产生与发展 遗传算法是建立在自然选择和群体遗传学机理基础上的一类通用问题求解 算法,遗传算法的适应性极其广泛。美国密西根大学,日胁砌刀d 教授在1 9 6 2 年最先提出了遗传算法,但是在当时学术界并没有足够的重视j 月h o l l a n d 教授 的这种想法,1 9 7 5 年生物学家达尔文的进化论的“适者生存的理念大大的启 发了,h h o l l a n d 教授等人,于是遗传算法的基本概念便被j 眉h o l l a n d 教授等 人第一次提出,而且自然和人工系统的适配( a d a p t a t i o n i nn a t u r a l a n da r t i f i c i a l s y s t e m ) ) ) 的发表成为了遗传算法创立的基本标志,这本著作是第一本相对系统 的讲解遗传算法的专门著作。遗传算法是从自然界中生物进化的规律发展而来 的,生物进化的基本过程如图2 1 所示: 图2 1 生物进化图 f i 9 2 1o r g a n i ce v o l u t i o n 从图中可以看到,群体之间经过相互竞争,因为存在环境因素的影响,群体 之中就会淘汰一些不适应这些环境的个体,这些群体将会被淘汰掉,于是那些适 第2 章遗传算法及蚁群算法 应环境的部分就会成为新的种群。这就代表了自然界中的优胜劣汰,适者生存的 规则。遗传算法就是生物进化的这个过程的启发,把最符合要求的解从众多的满 足条件的解中选择出来,于是也就选择出了经过多次迭代后还能够保留下来的 解,也就是满足条件的最好觯2 1 之3 1 。 2 1 2 遗传算法基本概念 遗传算法是一种先进的算法,模拟自然界的各种生物群体从低级到高级的进 化过程。遗传算法是从代表问题的可能潜在的解集的一个种群( p o p u l a t i o n ) 开 始的,一定数目的种群中的个体( i n d i v i d u a l ) 通过基因( g e n e ) 的编码( c o d i n g ) 过程从而组成一个种群,染色体的不同的基因型决定了个体的形状的外部表现是 不同的,而遗传物质的主要载体又是染色体,也是多个基因的一个集合,每个单 独的个体实际上就是带有一定特征的染色体( c h r o m o s o m e ) 的实体。在每一代,个 体的挑选( s e l e c t i o n ) 都是根据问题域中个体的适应度( f i t n e s s ) 大小来进行的,同 时组合交叉( c r o s s o v e r ) 和变异( m u t a t i o n ) 都是借助于自然遗传学的遗传算子 ( g e n e t i co p e r a t o r s ) 进行来进行的,在第一代种群产生之后,越来越好的近似解是 按照适者生存,优胜劣汰的原理逐代( g e n e r a t i o n ) 演化产生出的,于是就产生了 代表新的解集的种群。最后,通过解码( d e c o d i n g ) 末代种群中的最优个体,可以 将这些最优个体作为问题近似最优解。 遗传算法的形式化描述可以按如下方法表示: g a = ( p ( 0 ) ,n ,z ,s ,g ,p ,f ,f ) 其中,p ( o ) = ( b ( 0 ) ,p 2 ( o ) ,见( 0 ) ) ,表示初始种群;,则表示编码串的长度; s 表示选择的策略;n 表示种群所包含的个体的个数;遗传算子的操作概率用p 来 表示,包括表示交叉概率的p c 、表示选择概率的p r 和表示变异概率的p r o ;遗传算 子用g 来表示,通常包括表示选择算子的q ,、表示交叉算子的q 和表示变异算子 的q m ;适应度函数用厂表示;终止准则用f 表示。 6 基于g a a a 算法的码头集卡优化调度研究 2 1 3 遗传算法的特点 遗传算法是一种基于空间搜索的算法,遗传算法通过自然选择、遗传、变异 等操作,模拟自然界的进化过程来得出所求问题的解答,符合达尔文的适者生存 的进化理论。 遗传算法的特点有以下四点: 1 遗传算法并不是针对参数本身而进行进化,而是对参数集合的编码进行进 化; 2 遗传算法并不是从单个解开始搜索,而是从问题解的编码组开始进行搜索: 3 遗传算法并不是利用导数或其他辅助信息来指导搜索,而是利用目标函数 的适应度这一信息来指导搜索: 4 遗传算法并不是利用哪个确定性规则进行随机操作,而是利用选择、交叉、 变异等算子进行随机操作。 2 1 4 遗传算法基本步骤 遗传算法是一种由两部分组成的迭代搜索算法,这两部分分别为:搜索和生 成。遗传算法包括以下几个步骤: 1 编码 遗传算法只能对基因编码形式的个体进行处理,而并不能直接处理问题空间 的参数,在使用遗传算法的时候,很有必要把问题空间的解的参数形式转化成基 因编码的形式。这一转换操作就是我们通常所说的编码,也可以把编码称为问题 的表示。 通常来讲,由于交叉操作是由编码的形式所决定的,因此,编码的策略和方 法就会对遗传算法造成很大的影响【2 4 】。 在设计编码策略时,要遵循以下三个原则: 1 ) 健全性原则:任何一个染色体都对应有一个可能解和它对应; 2 ) 完备性原n :j h - j 题空间的所有的可能解都能用所设计的染色体的形式来表 示; 3 ) 非冗余性原则:染色体与可能解存在一一对应的关系。 2 初始种群生成 7 第2 章遗传算法及蚁群算法 种群就是由一定数量的个体组成的群体的总称,所研究问题的一个解与种群 中的每个个体是对应的。在对种群初始化的策略以及相关的参数进行设计时,必 须权衡种群多样性和算法的进化时间,这么做的原因就是:算法的性能直接受到 初始种群的选择影响,在一般情况下,那些随机生成的初始种群一般都需要较长 的进化时间,而基于某一特定的初始化策略虽即使可以降低进化时间,但却也有 可能使种群的多样性降低,从而使我们能够在可接受的时间内得到近似最优解满 意解或满意解。 3 适应度函数设定 为了体现染色体的适应能力,引入适应度函数的感念,这种函数对问题中的 每个染色体都能进行度量。染色体的优劣程度也决定于染色体的适应度函数。 适应度函数的设定主要有以下几种方法: 1 ) 以待求解的目标函数f ( x ) 转化为适应度函数 f i t ( f ( x ) ) ( 2 1 ) 若目标函数为最大化问题 j

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论