（管理科学与工程专业论文）基于蚁群算法的港口泊位调度优化与仿真.pdf

捅要 在全球贸易经济越来越多的聚焦在中国的同时，为了迅速与国际贸易接轨， 中国经济贸易进入快速增长时期，港口也承担起了作为国内外贸易的重要枢纽的 作用。但是随着国内经济贸易迅速发展，对港口的吞吐量及运营能力的要求也越 来越高。目前港口的吞吐能力和港口与日俱增的业务量成为目前港口业的主要矛 盾。这不仅影响到港口的运营成本以及客户的满意程度，也是影响港口竞争能力 的重要因素之一。在港口运营系统中，泊位作为限制港口工作效率、吞吐量的重 要环节之一，泊位的调度近年来成为港口管理者以及学者研究的重要内容。因此， 如何提高泊位这个环节的运作能力，在现有的有限资源的条件下，尽可能的减少 船舶在港时间，增加港口的吞吐能力是本文的主要研究对象。 一 本文采取优化算法与仿真模型相结合的研究方法，根据泊位系统的特点，分 析影响船舶停泊时间的因素，引入蚁群算法优化，将泊位调度问题转化为旅行商 问题，以所有在港船舶时间最短为目标函数。同时综合考虑了岸桥资源对船舶在 港时间的影响，建立数学模型，得到最佳调度方案，缩短船舶在港等待时间总和。 同时利用仿真软件p r o m o d e l 对泊位系统的工作流程建立仿真模型，模拟船舶到港， 泊位分配及岸桥卸货整个过程。建立两个仿真模型分别模拟船舶先来先服务的泊 位调度方案及通过蚁群算法优化得到的最佳泊位调度方案，比较这两种方案得到 的结果中，所有船舶在港的时间。再次验证泊位调度优化结果的有效性，同时观 察在不同的调度方案下，系统中的资源及各个环节的利用率等数据，以更好的指 导港口实际的泊位调度。 关键词：港口；泊位调度；蚁群算法；p r o m o d e l 仿真模拟 基于蚁群算法的港口泊位调度优化与仿真 a b s t r a c t w i t ht h ea t t e n t i o no fg l o b a lt r a d ea n de c o n o m i c sf o c u s i n go nc h i n a ，i n t e r n a t i o n a l t r a d ea n de c o n o m i c so fc h i n ah a st u r n i n gi n t oaq u i c kd e v e l o p i n gp e r i o di no r d e rt o m e e tt h ep a c ea n dn e e do fg l o b a le c o n o m i c s p o r ti so n eo ft h em o s ts i g n i f i c a n tn e x u s c o n n e c t i n gt h eg l o b a la n dd o m e s t i ce c o n o m i c s h o w e v e r , a l o n gw i t ht h eh i g hs p e e do f i n t e r n a t i o n a ld e v e l o p m e n to ft r a d ea n de c o n o m i c s ，t h er e q u i r e m e n to ft h et h r o u g h p u t a n dc a p a c i t yo fo p e r a t i o ni sb e c o m i n ge v e nh i g h e r t h ep r i n c i p a lc o m r a d i c t i o no fp o r t i n d u s t r yi si n c o m p a t i b l eo ft h r o u g h p u tc a p a c i t ya n dt h ei n c r e a s i n gn e e dt ot h ep o r t w h i c hw i l ln o to n l ya f f e c tt h ec o s to fp o r tm a n a g e m e n ta n dt h es a t i s f a c t o r yo ft h e c u s t o m e r , b u ta l s ot h ec o m p e t i t i v e n e s so ft h ep o r t i nt h eo p e r a t i o no ft h ep o r ts y s t e m , b e r t hi so n eo ft h em o s ti m p o r t a n tf a c t o r so ft h a tr e l a t e dt ot h ee f f i c i e n to fp o r to p e r a t i o n a n dt h r o u g h p u t b e r t hs c h d d u l i n gh a sb e c o m ea l li m p o r t a n t , r e s e a r c hr e c e n t l y t h em a i n o b j e c to ft h i sp a p e r i sf o c u s e do ni m p r o v i n gt h ec a p a c i t yo fb e r t ho p e r a t i o nw i t hl i m i t e d r e s o u r c e ，i no r d e rt or e d u c et h eo v e r a l lt i m ev e s s e l ss p e n ti nt h ep o r t t h i sp a p e ru t i l i z e st h ec o m b i n a t i o no fo p t i m i z e da l g o r i t h ma n ds i m u l a t i o nm o d e l a c c o r d i n gt ot h es p e c i a l t yo fp o r ts y s t e m , a n a l y z e st h ef a c t o r st h a ta f f e c ti n p o r tt i m e a n di m p o r t st h ea n tc o l o n yo p t i m i z a t i o n ( a c o ) t ot r a n s f o r mt h eb e r t hs c h e d u l i n g i s s u ei n t ot r a v e l i n gs a l e s m a np r o b l e m ( t s p ) i s s u e t h eo b j e c t i v ef u n c t i o ni st h el e a s t i n p o r tt i m ec o s t i n go fa l lv e s s e l s a tt h es a m et i m e ，c r a n er e s o u r c ei s a l s oo n e i n f l u e n t i a lf a c t o ro ft h ei n p o r tt i m ew h i c hi sa l s oc o n s i d e r e di nt h eo p t i m i z a t i o n t h e m o d e lw a se s t a b l i s h e du p o na l lt h e s ef a c t o r sa n dt h em o s ts u i t a b l es c h e d u l i n gs o l u t i o n w a ss u g g e s t e db yt h er e s u l t s t h es i m u l a t i o nm o d e lt o o lp r o m o d e li su s e dt oe s t a b l i s ht h es i m u l a t i o ns y s t e mo f b e r t hs y s t e ma n ds i m u l a t et h ew h o l ep r o c e s so fa r r i v i n go fv e s s e l s ，d i s p a t c h i n gb e r t h a n du n l o a d i n gb yc r a n e s t w od i s p a t c h i n gm o d e l sw h i c ha r ef i r s tc o m ef i r s ts e r v i c e s t r a t e g ya n ds t r a t e g yb a s e do na c o a r ee s t a b l i s h e dt o c o m p a r et h ei n p o r t t i m e d i f f e r e n c e s v e r i f yt h es o l u t i o no fb e r t hs c h e d u l i n go p t i m i z a t i o ni se f f e c t i v ea n do b s e r v e t h eu t i l i z a t i o no fr e s o u r c ea n do t h e rs e c t i o n si nt h es y s t e mu n d e rt h e s et w om o d e l si n o r d e rt ob em o r eu s e f u lt od i r e c tt h ep r a c t i c a lp o r to p e r a t i o n k e yw o r d s ：p o r t ；b e r t hs c h e d u l i n g ；a n tc o l o n yo p t i m i z a t i o n ；p r o m o d e l s i m u l a t i o nm o d e l 大连海事大学学位论文原创性声明和使用授权说明 原创性声明 本人郑重声明：本论文是在导师的指导下，独立进行研究工作所取得的成果，撰写成博硕 士学位论文 = = 基王蚁登簋洼的鲞旦泊僮遢廑垡丝量值真：。除论文中已经注明引用的内容 外，对论文的研究做出重要贡献的个人和集体，均已在文中以明确方式标明。本论文中不包 含任何未加明确注明的其他个人或集体已经公开发表或未公开发表的成果。本声明的法律责 任由本人承担。 学位论文作者签名： 学位论文版权使用授权书 本学位论文作者及指导教师完全了解大连海事大学有关保留、使用研究生学位论文的规 定，即：大连海事大学有权保留并向国家有关部门或机构送交学位论文的复印件和电子版， 允许论文被查阅和借阅。本人授权大连海事大学可以将本学位论文的全部或部分内容编入有 关数据库进行检索，也可采用影印、缩印或扫描等复制手段保存和汇编学位论文。同意将本 学位论文收录到中国优秀博硕士学位论文全文数据库( 中国学术期刊( 光盘版) 电子杂志 社) 、中国学位论文全文数据库( 中国科学技术信息研究所) 等数据库中，并以电子出版物 形式出版发行和提供信息服务。保密的论文在解密后遵守此规定。 本学位论文属于：保密口在年解密后适用本授权书。 不保密( 请在以上方框内打“”) 论文作者签名： 日期：弘，。年6 月日 l 千 冉取。 i 导师签名：拶 基于蚁群算法的港口泊位调度优化与仿真 第一章绪论 1 1 研究背景和意义 随着经济的发展，全球化的趋势和区域性经济合作、互相促进的趋势愈加明 显。各个国家、地区都积极利用一切可能的渠道开展国内外贸易、文化交流等活 动。十九世纪以来，各国经济中心城市相机在沿海地区形成，并以港口为中心进 行新的经济发展布局。因为港口是一个社会关联度极高的产业，港口的发展繁荣 了城市，而中心城市经济的发展又促进了港口的发展。回顾港口的发展历程极其 经济、社会、历史地位、作用的变化，我们可以了解到港口与城市的密切关系， 港口对城市、区域、腹地经济的发展和社会进步有着重要的作用，而城市、区域、 腹地经济的繁荣，是港口得以发展的重要依托。港口作为一个重要的交通枢纽， 是连接国内外贸易的重要环节之一。从制造业的角度来说，一个国家或地区港口 经济的发展和竞争力，越来越影响着其制造业的发展和竞争力。区域工业与临港 工业的联动性在增强，工业化进程快的国家或地区，港口经济扩张迅速，同时， 港口经济发展快，也对工业化起了有力的促进作用。 中国正在成为全球最具竞争力的世界工厂，也正在成为最具吸引力的世界市 场。这就意味着从世界各地进口大量的原材料、零部件和消费品。所以每年中国 港口数以千万计的集装箱吞吐量是一个必然的趋势，中国已经成为全球航运业争 夺的主战场。我国大陆海岸线长达1 8 0 0 0 多千米，自北向南濒临渤海、黄海、东 海和南海，1 3 个沿海省份，约4 8 个沿海城市，因此中国港口的发展，对全国的经 济发展及文化交流有着重要的意义。到2 0 1 0 年初，中国大陆的“亿吨大港”已经 达到十七个，稳居世界前列。同时，随着物流业近年来的迅速发展，港口间的竞 争也愈加激烈。因此，加速港口建设，提高港口工作效率，以提高船舶的利用率 和客户的满意度，成为热门研究的问题。 港口的服务系统是一个十分复杂的系统，需要各个环节高度协调发展，各种 有效资源都应该被合理高效的利用。由于港口的装卸设备都较大型且价格昂贵， 增加大量装卸设备来提高港口的物流运作效率并不是管理者的最佳选择。因此如 何有效的利用现有的资源，提高设备使用率，合理规划调度，成为了港口服务系 绪论 统最重要的管理环节。船舶停泊是船舶入港的第一关，是提高港口效率首先要面 临的问题，也是衡量一个港口的整体吞吐能力的重要指标，系统中的其他设施都 根据港口泊位能力进行相应的配置。船舶到港后，能够在最短时间内靠港卸货， 对泊位占用时间越短，货物的周转量也越大，港口的物流效率也会大大增加。为 了不使港口的泊位分配成为整个港口系统的“瓶颈 环节，优化港口泊位调度， 缩短船舶接受服务的等待时间，同时对泊位系统的工作流程进行仿真，深入了解 在某种泊位调度方法下，泊位中各个环节的表现情况，并验证泊位调度的有效性， 成为本文研究的重点。 1 2 国内外研究现状 1 2 1 港口泊位调度建模研究现状 目前国内外学者针对港口的优化调度问题从不同的角度和层面展开了深入的 研究，当前的研究主要包括以下几方面n 1 ：泊位分配、岸边吊装设备的规划、港内 的车辆调度、堆场空间的分配、堆场起吊设备的调度、闸门资源的分配和码头的 整体优化调度。 对泊位调度的研究从对象上来看，分为单纯的研究泊位以及把泊位与岸桥或 者把整个港口作为一个整体相结合同时研究。从方法上来看，分为通过仿真模拟 技术来评价和优化资源调度策略以及通过数学模型的方式来优化最优解。 对港口泊位调度系统建立数学模型，求解得出最优解。这种方法的使用有较 长的历史，在实际的研究中应用也比较广泛。在通过数学模型来分析优化的研究 中，对于泊位单独的研究主要有：a k ii m a i 采用改进的启发式算法对泊位进行调度 分配乜3 。“和s h i h 口1 提出了一种针对泊位分配问题的启发式算法，这种算法是基 于先来先服务( f c f s ) 的分配策略。e d o m a l 等h 1 也提出了利用排队论对码头泊位分 配以及货物处理规划问题建立了模型并且进行了讨论。i m a i 晦3 等以最小化船舶等待 时间为目标，用非线性整数规划模型来分别模拟静态记忆动态码头的泊位调度问 题。同时他们也通过研究，证明了在多用户的集装箱码头系统中，在不考虑先来 先服务( f c f s ) 原则的情况下，可以获得较短船舶停泊时间的分配方案，但在这种 情况下，会出现某些船舶等待时间过长的情况。n i s h i m u r a 1 等迸一步扩展了上面 提到的集中模型，综合考虑了水深泊位对泊位调度产生影响的情形，并应用了遗 基于蚁群算法的港口泊位调度优化与仿真 传算法对模型求解。w a n g 盯1 等设计了应用随机集束搜索算法对泊位分配问题进行 求解的方法。李平随3 等提出利用混合优化策略来提高遗传算法的种群多样性，并加 速算法的进化过程，用来求解泊位分配问题。b o r w n 等旧1 以船舶在港总效益最优为 目标，建立了分配洎位的模型。a k i o 和e t s u k o 等把泊位分配问题分为静态泊位分 配和动态泊位分配两个方面，同时还给出了两种分配问题的模型及其求解方法， 重点研究利用拉格朗日松弛法解决动态泊位的分配问题。j e a n f r a n s c o i sc o r d e a u 等总结了泊位分配中的连续系统模型，并且运用禁忌搜索算法对这个连续模型进 行了求解。c h e n 和h s i e h n 叼通过时空网络模型来帮助决策者有效地进行泊位分配， 模型中综合考虑了船舶在港、到港和离港的时间，将这个问题转化成一个边约束 的普通网络模型，用分支定界法求得了模型的最优解。p a r k 等1 利用基于拉格朗 日的次梯度算法对泊位分配问题进行了求解。戈闻怡n 2 1 用遗传算法求解泊位资源 配置调度，得到了所有船舶在港时间最短的最优解。z h o u 等n 3 3 利用模糊理论对泊 位调度中的不确定性因素进行了初步探索性研究，得到了良好的效果。 而对于将泊位与岸桥相结合的研究主要有：l i n 钔等将泊位岸桥调度问题看作一 个可以同时处理多个任务的处理机调度问题，并假设所有船舶在系统开始时就已 经在港等候停泊，建立了以船舶在港时间最小为目标的模型，提出了启发式算法 求解。类似的，g u a n n 印等将泊位岸桥分配问题作为处理机调度问题，优化目标是 将带权重的任务完成最小化时间。韩晓龙n 明等利用回溯算法求解了泊位岸桥配置 优化模型。蔡芸口7 3 等采用遗传算法求解泊位分配及岸桥的调度问题，目标是所有 船舶在港时间最短。周鹏飞n 踟等重点考虑了船舶抵港时间和装卸时间的随机性， 建立了面向随机环境的集装箱码头泊位岸桥调度模型。d a g a n z o n 钔乜们等将船舶在港 的卸货过程划分成几个不同的区域，使用了整数规划模型对静态岸桥的规划问题 进行研究，达到了船舶的等待时间最小的目标。随后，又将岸桥调度过程看作成 一个开放的生产计划问题，建立了整数规划模型，利用分支定界法求解模型。b 6 s e 等窿建立了岸桥等待时间最短的模型，并且建立仿真模型来模拟岸边有缓冲区的 集装箱码头的工作流程，在给定集装箱装卸序列的要求前提下为桥吊配备了跨越 车并确定了相应的作业序列。韩骏等瞳2 3 将泊位调度与岸桥分配这两个相联系的问 题进行了系统分析与集成，以船舶在港时间最小为目标，利用免疫遗传算法对泊 位与岸桥协调调度问题建立了优化模型，缩短船舶在港停留时间。柴志刚心3 3 为了 绪论 解决缩短船舶在港作业时间而产生的负面效应，提出了一种均衡理念的优化思想。 基于集装箱码头的班轮制特点及泊位调度中的不确定性因素影响，建立了综合考 虑船舶靠泊位置、靠泊时刻及装卸速度的均衡优化模型。在求解中采取人机交互 与自适应遗传算法相结合的方式，设计了相应的优化算法，并通过算例对模型及 算法的有效性进行了验证。y o u n gm a np a r k 口4 1 针对同时调度规划泊位和岸桥问题， 建立了一个混合整数的计算模型。首先确定船的停泊位、停泊的时间以及将与之 配备的岸桥数目，用动态规划技术分配每个泊位的岸桥数量。 1 2 一系统仿真技术的研究现状 目前对现实系统进行仿真的可以分为三种方案乜副：基于专用的仿真语言或通 用过程语言进行开发；选用仿真器；通用过程仿真平台。这三种方案中，第一种 方案的优点是建模灵活，但编程较复杂并容易出错；选用仿真器这种方法则相反， 虽然简单易用，但却缺少建模的灵活性，适用于功能比较单一的仿真；而通用过 程仿真平台这种方法是在前两者的基础上进行二次开发，目前用途比较广泛的方 案并且比较成功的方案都有既简单易用又很灵活的特点。例如，b r o o k s 公司研制 的a u t o m o d ，r o c k w e l l 公司的a r e n a ，c a c i 公司开发的s i m p r o c e s s ，p r o m o d e l 公 司的p r o m o d e l 和l a n n e r 公司的产品w i t n e s s 的等都是性能很好的仿真软件，目前 在各个领域用途均较为广泛乜6 1 。其中，p r o m o d e l ( p r o d u c t i o nm o d e l i n g ) 仿真软件是 由美国p r o m o d e l 公司开发出来用于构造多种生产、服务和系统模型的计算机仿真 工具，也是在美国和欧洲使用最广的系统仿真软件之一盟嗣。作为当前较流行的一 种仿真工具，它能够精确地建立一个经营过程及其资源配置模型，保证模型的随 机性、不确定性和相互依赖性，并同时具有为设计者提供连续或离散事件、动态 以及随机的分析功能。 国外已有采用二维动态仿真技术来研究港口生产系统的运作方式硷”，以及在 港口设计中确定港口资源的合理配置的问题，并已研制出成熟软件，例如澳大利 亚的r e a l t i m eb u s i n e s ss o l u t i o n p t y l t d 推出的港口码头运作仿真软件一一 x w i n d o w ，以集装箱码头为主要仿真对象，利用二维图形对资源配置、堆场规划 等问题进行仿真，为港口决策者提供规划依据，并且提高了港口的生产效率。 仿真技术在泊位调度方面的研究成果主要有，蔡芸啪1 利用e m p l a n t 仿真软件 建立了以总体船舶在港时间最短为目标的仿真优化模型，生成满足停泊条件和岸 基于蚁群算法的港口泊位调度优化与仿真 桥调度策略的可行分配方案，凭借仿真模型来解决数学模型中的约束条件和岸桥 调度问题，当方案不满足约束时，仿真模型终止仿真，调用且返回给遗传算法一 个足够大的个体适应度数值，将该方案淘汰，以保证优化结果的可行性。最终得 到了包括船舶的停泊时间、停泊位置和为其服务的岸桥数目等要素的优化解。 p a s q u a l el e g a t o 和r i n am m a z z a 晒3 运用排队网络模型，采用面向过程的v i s u a l s l a m 语言，对港口泊位计划和装卸资源分配进行了研究。唐臣跚1 等也在排队论 的基础上，使用w i t n e s s 仿真软件对集装箱码头的最优泊位数进行研究。鲁子爱口妇 把港口生产视为随机服务系统，建立了模拟港口营运状况的计算机仿真系统。仿 真模型中，船舶占用泊位时间根据船舶装卸量、码头泊位装卸效率、气候影响等 条件计算确定。在这些研究中，涉及到的一些船舶停泊方面的问题都是在“先到 先服务”的基础上，再考虑一些其他的约束条件来提供泊位分配方案，然后依据 船舶在港的逗留时间越短越好、泊位利用率越高越好、费用支出越少越好等因素 来对各个方案进行评价，选取合理的方案。n a m k c 等口2 3 为韩国釜山g a m m a n 集装 箱港口评估今后发展方案，设计了四类仿真场景，采用不同作业策略，优化港口 泊位和岸桥数量大小。汪锋应用w i t n e s s 仿真软件建立某集装箱码头仿真模型， 具体研究在一定吞吐量情况下配备合理泊位数，以及在一定的泊位数的情况下岸 桥的合理调度问题，指出了应根据不同的船泊到港密度安排合理的调度方式。 1 3 课题的研究内容和方法 港口泊位，一般指供一艘船舶停靠系泊的位置，称为一个泊位。具体来说， 是指港区内码头岸线供船舶安全靠离、进行作业或停泊所需要的水域和空间。有 码头泊位、浮筒泊位、锚地泊位等。船舶在泊位停靠必须满足一定的岸线长度要 求以及泊位水深要求，其长度一般为设计船长的1 2 0 ，接待的船舶越大，泊位就 越长，前沿水域就越深。 岸桥乜5 1 ，简称桥吊或装卸桥，是集装箱港口使用的最大型的、价格最昂贵的 装卸机械。它是港口装卸设备的龙头，主要负责装卸集装箱船舶。 泊位调度是指根据码头泊位的数量、使用情况和物理条件为到港船舶或即将 到港船舶安排停泊顺序以及泊位停泊。由于泊位是码头的主要稀缺资源，因此在 整个港口服务系统中，具有极为重要的影响，直接决定了港口的吞吐量、工作效 绪论 率。泊位调度理想的结果是船舶不需要等待就可以直接停泊、泊位的利用率达到 1 0 0 ，而这在现实中是不可能达到的。假如由于不可预测的原因，同一时间段内 进港船舶较多时，由于泊位数量的限制，船舶就不可避免的要在锚排队等待，而 假如泊位的分配不合理，不仅将会造成巨大的经济损失而且会降低港口的竞争力， 影响到整个港口未来的发展。为了解决这一“瓶颈 问题，如何提高泊位调度效 率，减少船舶等待服务时间是人们一直关注研究的问题。影响泊位调度的主要因 素有：船舶相关信息，如到港时间、装卸量等；码头资源情况，如泊位状态、岸 桥设备等；物理条件限制，如泊位水深、长度等。目前我国大部分港口泊位调度 主要是依靠码头工作人员的经验分配的，或者是由船舶的运营者与港口公司双方 的合同规定，在一些现代性国际化的集装箱码头，多采用整数规划或模拟方法， 借助智能决策系统来进行码头泊位调度。 泊位调度的研究分为离散型和连续型m 3 。离散型的泊位指船舶在停泊时不能 同时占用多个泊位，只能停泊在某一个泊位所限定的位置和空间中，受泊位物理 条件的限制。连续型泊位是指船舶在停泊时可以同时占用多个泊位停泊。在这种 情况下，船舶的停泊将会有更大的选择性，同时对于岸线的要求也更高。另一方 面，根据船舶到达时间与泊位分配时间的先后之间的关系，泊位调度还可以分为 静态和动态两种。静态调度指在进行泊位分配时，所有需要安排停泊的船舶都已 到达港口，这些船舶都将被考虑到下一个停泊时间段中；而动态泊位调度是指泊 位分配开始时仍有船舶未到港，但将会在分配时间段中的某时刻到达。 本文拟针对船舶靠港“第一关”：停泊，这一动作，研究泊位调度分配的最优 方式。在综合考虑船舶本身的条件，包括船长、吃水深度、货运量等条件下，以 船舶的总服务时间( 包括等待泊位以及卸货时间) 最短为目标。由于每个泊位的 物理位置不同，船舶停泊后能够为其提供卸货服务的岸桥的数量及状态也不同， 因此也影响到船舶的服务时间。我们在研究泊位调度时，应该在考虑泊位空闲的 同时，考虑该泊位可用岸桥的数量和状态选择使船舶在港时间最小的泊位停靠， 这里在港时间最小包括分配泊位的时间及在该泊位上可用的岸桥的服务时间。若 是将两个环节单独调度，先根据最小等待时间为船舶选择泊位停泊，停泊后再等 基于蚁群算法的港口泊位调度优化与仿真 待分配岸桥，则忽视了岸桥的分配对船舶在港时间的影响，造成其他船舶的等待 时间加长，具有一定局限性。将岸桥与泊位共同调度则会避免单独调度的局限性， 可以使船舶总在港时间更短，并且将提高岸桥的工作效率。因此本文的研究对象 是泊位调度以及与泊位相配合的岸桥调度，使得船舶在靠港及卸货过程中，各子 系统协同作业。 本文拟采用蚁群算法建立数学模型，并利用仿真软件p r o m o d e l 模拟船舶到港， 泊位分配及岸桥卸货整个过程。通过模拟结果分析模型的优劣性，以便求得更符 合实际情况的最优解。 1 4 文章内容安排 本文共分为五章。 第一章绪论。说明本文的研究问题的背景及研究意义，确定本文的研究内容 及研究方法，并且确定本文的技术路线。详细介绍了目前针对泊位调度问题、仿 真模型等方面的国内外研究现状。 第二章基本技术方法介绍。详细介绍本文中将用到的泊位调度优化模型 蚁群算法的原理、特点及算法描述；仿真模型的基本概念、方法及本文中用到的 p r o m o d e l 软件的应用及基本元素。 第三章泊位调度优化。重点论述了蚁群算法求解泊位调度的步骤，设定目标 函数、模型的假设约束条件、具体的参数设定及模型求解步骤。将数据代入模型 中，求得最优解，分析结论。 第四章泊位调度仿真。使用p r o m o d e l 仿真模型，对泊位调度及岸桥分配的 整个过程进行仿真模拟。设计符合实际情况的各种基本元素，建立仿真逻辑模型， 模拟泊位调度及岸桥分配的处理过程。并且根据第三章中蚁群算法模型求得的最 优分配策略，对实际情况进行模拟。分析结果。 第五章结论。分析本文得到的泊位调度模型求得的最优解以及泊位调度仿真 结果，总结在研究过程中发现的问题及不足以及对未来的研究的展望。 基本技术方法介绍 第二章基本技术方法介绍 2 1 蚁群优化算法 2 1 1 蚁群优化算法的基本原理及特点 2 0 世纪9 0 年代意大利学者m d o r i g o ，v m a n i e z z o ，a c o l o r n i 等从生物 进化的机制中受到启发，通过模拟自然界蚂蚁搜索路径的行为，提出来一种新型 的模拟进化算法一蚁群算法，是群智能理论研究领域的一种主要算法m 1 。用该 方法求解旅行商( t s p ) i h - j 题、分配问题、车间调度问题o o b s h o p ) 、车辆路由问题、 图着色问题和网络路由问题等1 ，取得了较好的试验结果虽然研究时间不长， 但是现在的研究显示出，蚁群算法在求解复杂优化问题，尤其是离散优化问题方 面有一定优势，这表明它是一种有发展前景的算法这种方法能够被用来解决大 多数优化问题或者能够转化为优化求解的问题。 蚁群算法7 3 是对自然界蚂蚁的寻找路径的方式进行模拟得出的一种仿生算 法。这种算法区别于传统的编程模式，它的主要优势在于，有效的避免了冗长的 编程和筹划过程，算法本身是基于一定的规则，随机运行来寻找最优解。也就是 说，当蚁群最开始找到目标的时候，路径几乎不可能是最优的，甚至可能是包含 了很多错误的选择，结果非常不理想的。但是，蚁群算法可以通过蚂蚁寻找食物 的时候释放信息素的原理，不断地去修正原来的路线，使所有经过的路径越来越 短，由于这种原理，算法被执行的时间越长，所获得的路径就越可能接近最优路 径。这种寻径方式类似于我们以前经常用到的通过大量的数据、实验，对结果进 行总结分析，最终形成最佳路径的过程。这实际上是类似算法的一个自我学习的 过程。蚂蚁在运动过程中，能够在它所经过的路径上留下一种称之为外激素的物 质进行信息传递，而且蚂蚁在运动过程中能够感知这种物质，并以此指导自己的 运动方向，因此由大量蚂蚁组成的蚁群集体性的行为便表现出一种信息正反馈现 象：某一路径上走过的蚂蚁越多，则后来者选择该路径的概率就越大。 基于自然界中蚁群寻找食物时的最优路径选择问题，可以构造人工蚁群，来 解决最优化问题。在人工蚁群中，我们把具有简单功能的工作单元作为蚂蚁。二 者的相似之处表现在，两者都是优先选择信息素浓度较大的路径。较短路径的信 基于蚁群算法的港口泊位调度优化与仿真 息素浓度高，所以能够逐渐被所有蚂蚁选择，也就是产生了最终的优化结果。两 者的区别表现在人工蚁群具有一定的记忆能力，能够记住已经访问过的节点而不 重复访问。同时，人工蚁群在选择下一条路径的时候是按一定算法规律有意识的 寻找最短路径，并不是盲目的。蚂蚁选择下一个目标，向下一个目标的运动是通 过一个随机原则来实现的，也就是运用当前所在节点存储的信息，计算出下一步 可到达节点的概率，比较并按照这个概率实现一步移动，反复几个过程之后，越 来越接近最优解。蚂蚁在寻找路径的过程中，或者找到一个解后，会评价这个解 或解的一部分的优化程度，并把这个解的评价信息保存在相关的信息素中。信息 素的更新方式有两种，一是挥发，也就是所有路径上的信息素以一定的比率进行 减少，这是模拟了自然蚁群的信息素随时间挥发的过程；二是增强，在评价值较 好的路径上增加信息素。 这种优化过程的本质在于蚁群算法的三个独特机制：选择机制、更新机制和、 协调机制。所谓选择机制是指信息素残留越多的路径，被蚂蚁选择的概率越大； 更新机制表示的是路径上的信息素会随着蚂蚁经过次数的增加而增长，而与此同 时也会随时间的以一定的速率有一部分挥发；协调机制是指蚂蚁之间事实上是通 过这种信息素的分泌来实现彼此之间的通信，共同工作的。 蚁群算法通过候选解组成群体来寻求最优解的进化过程，它包含两个基本的 阶段啪3 ：适应阶段和协作阶段。在适应阶段，各个候选解根据积累的信息不断调 整自身结构；在协作阶段，候选解之间通过信息交流，以期望产生性能更好的解。 蚁群算法正是充分利用了选择、更新和协调的优化机制，即通过个体之间的信息 交流与相互协作最终找到最优解，使它具有很强的发现较优解的能力。 2 1 2 蚁群算法描述 为了说明蚂蚁系统模型，首先引入旅行商问题静引。旅行商问题就是指定几个 或n 个城市之间的距离，要求确定条经过各城市当且仅当一次的最短路线。为 模拟实际蚂蚁的行为，首先引入如下记号： i i 】蚁群中蚂蚁数量； b i ( t ) 叫时刻位于城市i 的蚂蚁的个数，m = b i ( t ) ； i = 1 如两城市之间的距离； 基本技术方法介绍 1 1 i j 边( i ，j ) 的能见度，反应由城市i 转移到城市j 的启发程度，这个数值在 蚂蚁系统的运行中不改变； 旬边( i j ) l - i 拘信息素轨迹强度； 旬蚂蚁k 在边( i ，j ) 上留下的的单位长度轨迹信息素量； 磁蚂蚁k 的转移概率，j 是尚未访问的城市。 每只蚂蚁都是具有如下特征的简单主体： ( 1 ) 在从城市i 到城市j 的运动过程中或是在完成一次循环后，蚂蚁在边( i j ) 上释放一种物质，称为信息素轨迹； ( 2 ) 蚂蚁概率的选择下一个将要访问的城市，这个概率是两城市间距离和连 接两城市的路径上存有轨迹量的函数； ( 3 ) 为了满足问题的约束条件，在完成一次循环以前，不允许蚂蚁选择已经 访问过的城市。 初始时刻，各条路径上的信息素量相等，设( o ) = c ( c 为常数) 。蚂蚁k ( k = l ，2 ，3 ，m ) 在运动过程中根据各条路径上的信息素量决定转移方向。蚂蚁系统 所使用的状态转移规则被称为随机比例规则，它给出了位于城市i 的蚂蚁k 选择移 动到城市j 的概率。在t 时刻，蚂蚁k 在城市i 选择城市j 的转移概率嘭( t ) 为： 啪，- 孥 。j a l l o w e dk ( 2 1 ) 其中a l l o w e d k = 0 ，1 ，n 一1 ) 表示蚂蚁k 下一步允许选择的城市。与之对应的是 禁忌表t a b u k ，表中记录了蚂蚁k 已经走过的城市，蚂蚁k 在本次循环当中将不再 访问t a b u 表中的城市。t 1 i i 为能见度因素，a 和p 为两个参数，分别反映了蚂蚁在 运动过程中所累计的信息以及启发信息在蚂蚁选择路径中的相对重要性。当本次 循环结束以后，禁忌表中的数据将被用来计算该蚂蚁所建立的城市访问方案( 即 蚂蚁所经过的路径长度) 。之后，禁忌表被清空，该蚂蚁出发时又可以自由的进行 选择。 经过n 个时刻，蚂蚁完成一次循环，各路径上信息素量根据下式调整 基于蚁群算法的港口泊位调度优化与仿真 t i j ( n + 1 ) = p 。旬( t ) + t 日( t ，t + 1 ) a x i j ( t ，t + 1 ) = 露( ”+ 1 ) k = l ( 2 2 ) ( 2 3 ) 其中，a 露( f ，f + 1 ) 表示第k 只蚂蚁在时刻( t ，t + 1 ) 留在路径( i ，j ) 上的信息素量， 信息素的值是根据蚂蚁表现的优劣程度而决定的。蚂蚁经过的路径长度越短，信 息素相应的释放的就越多；a t i j ( t ，t + 1 ) 表示本次循环中路径( i j ) 的信息素量的增量； ( 1 一p ) 表示的是信息素轨迹的衰减系数，通常情况下，设置系数p - 0 ( p i - k ) x i j o ， o h 1j - j ( 3 2 ) y k j m a x c j ( 3 1 0 ) j = l y j k l - y j k + l - y j k = 一1 ，0 ，1 ( 3 1 1 ) 其中，式( 3 2 ) 表示每条船必须被服务一次且仅能被服务一次；式( 3 3 ) 表示每 个泊位一次只能停靠一条船；式( 3 4 ) 表示船舶不会同时到港；式( 3 5 ) 表示船必须到 达锚地等待后才能被服务；式( 3 6 ) 表示船必须在到达泊位等待后才能接受卸货服 务；式( 3 7 ) 表示在泊位i 停泊的船j 吃水深度小于泊位i 的水深；式( 3 8 ) 表示在泊 位i 停泊的船j 长度小于泊位j 的泊位长度；式( 3 9 ) 表示岸桥为一条船舶卸货完成 之后才能为下一条船舶服务；式( 3 1 0 ) 表示为船j 分配的岸桥数不得超过其能接受 的最大岸桥数；式( 3 1 1 ) 表示为船舶分配的多个岸桥必须是相邻的，y k 1 、yk 、y “1 功 $ d 乃印 0 0 p p p 0 p 基于蚁群算法的港口泊位调度优化与仿真 是三个相邻的泊位，假如y k 1 和y k + l 在为船j 卸货，而y k 没有在为船j 卸货，则 y 州+ y 阶1 一y j f 2 ，不符合假设条件要求。 此外，还有以下几条假设条件： ( 1 ) 船舶的到港时间是确定的； ( 2 ) 船舶的卸货时间等于为船舶卸货的岸桥的服务时间，船舶仅能接受这个 泊位上的岸桥的卸货服务； ( 3 ) 船舶卸货时间与船舶类型相对应，是根据船舶的装载量预先确定的。船 舶卸货需要的岸桥数与其装卸量的相对应关系如下：当船舶装卸量 3 0 0 箱时，为 其安排1 台岸桥服务；当船舶装卸量为3 0 1 5 0 0 箱时，为其安排2 台岸桥服务， 当船舶装卸量为5 0 1 。7 0 0 箱时，为其安排3 台岸桥服务。岸桥的卸货速度规定为 3 5 箱小时。 3 2 4 算法的设计与实现 整个泊位调度的过程与t s p 问题类似，但是相较t s p 问题要复杂一些，其特 殊性在于以下几点： 1 ) 在泊位调度问题中，我们将船舶的载货量h i 看做t s p 问题中城市之间的 距离，把船和泊位共同作为需要遍历的城市。城市之间距离的具体表示方法为： 如果两个城市都是船舶，则距离用两个船的载货量之和表示；如果两个城市都是 泊位，则距离用所有船舶的载重量之和表示，以减少连续选择两个泊位的概率； 如果两个城市中一个是船舶一个是泊位，则距离就用这条船舶的载重量表示； 2 ) 每只蚂蚁的出发点都必须是泊位； 3 ) 在最终的结果中，为了区别泊位与船舶，在给每个城市编号的时候，采取 以下规则：船舶从0 开始编号，依次递增；泊位的编号则从最后一个船舶的号码 开始顺次加1 ，也就是说，编号比所有船舶编号都大的城市就是泊位。两个泊位之 间的编号的船舶，停在前面的泊位上，停泊的顺序与寻径的顺序相同； 4 ) 由于泊位的物理条件的限制，蚂蚁在寻径的过程中，要搜索符合这个泊位 限制的船舶，并且要考虑这个泊位上可用的岸桥数量，不符合条件的泊位将不会 出现在最优路径中； 5 ) 与t s p 问题不同的是，泊位岸桥调度的目标是所有船舶的总等待时间最优 化，因此要考虑一个循环的总距离最小。 泊位调度算法设计 算法中基本的参数设定如下： 1 、蚂蚁数量：设m 是蚂蚁的数量，通过综合考虑算法的全局搜索能力和收敛 速度，有研究表明3 ，蚂蚁数量的选择宜选取m = ，z n 2 之间( 其中n 为问题的 规模，即共有多少条船舶需要停泊) 。每当一个泊位空闲下来，蚂蚁将开始选择下 一个节点，即需要停泊的船舶。 2 、状态转移概率：在搜索过程中，蚂蚁根据下一个可供选择的船舶的信息量 及路径的启发信息来计算下一步的转移概率。呓( t ) 表示在t 时刻蚂蚁k 在i 点出发 选择j 船舶的选择概率： 唠( t ) =揣水以 蚴 o 其中a 代表信息素浓度的权重，即路径( i ，j ) 上残留信息量t 如) 的相对重要 性。1 3 代表可选结点信息的权重，即蚂蚁在运动中的启发期望值7 7 ；，的相对重要性。 a l l o w e d k 代表蚂蚁下一步允许访问的城市。根据相关的研究陋3 ，p 选取1 5 左右，伍 选取0 5 5 之间，蚁群算法均能获得较好的搜索结果。 3 、信息素更新规则：在常用的三种信息素更新模型中，根据之前的分析，蚁 周模型的效果最好，因此我们采取蚁周模型来更新信息素。信息素更新公式如下： x i j ( t + n ) = ( 1 一p ) 。x i j ( t ) + ax i j ( t ) ( 3 13 ) 其中，p 为信息素残留系数，是一个常数，p 值的选取直接影响到算法的收敛 速度及是否能得到全局最优解。为提高蚁群算法的全局搜索能力，提高其搜索速 度，可以自适应的改变p 的值。根据近年来的研究结果，以及本问题的特殊性， 我们选取p 的初始值为o 8 5 ，( 1 p ) - t ；，( t ) 表示蚂蚁走完全程之后所有留下的信息 素的挥发，t ，( t ) 表示信息素的修改。 t ；，( t ) ：j 笋 第k 只蚂蚁经过( ) 这条路径 ( 3 1 4 ) io 否则 其中，q 为信息素强度，表示第k 只蚂蚁在整个路径中的目标函数值，即 基于蚁群算法的港口泊位调度优化与仿真 船舶等待时间。 当算法求得的最优值在n 次循环内没有明显改进时，p 减为 p ( t ) - p 5 以卜1 ) 若o 9 5 “t - ” p 凼 ( 3 1 5 ) 【 p 耐n 否则 其中p , m 为p 的最小值，可以防止p 过小降低算法的收敛速度。 具体的蚁群算法步骤如下： s t e p1 初始化蚁群，时间计数器t = 0 ，迭代次数i t _ c o u n t - - 0 ，z i j ( t ) = c ， a f i j ( t ) - - 0 ，合理的设置各项参数。同时设定好问题中的具体数据，包括船舶的物理 条件、泊位的物理条件、船