蚁群算法的港口泊位调度优化与仿真 精品.doc

基于蚁群算法的港口泊位调度优化与仿真第一章 绪论1.1 研究背景和意义随着经济的发展，全球化的趋势和区域性经济合作、互相促进的趋势愈加明显。各个国家、地区都积极利用一切可能的渠道开展国内外贸易、文化交流等活动。十九世纪以来，各国经济中心城市相机在沿海地区形成，并以港口为中心进行新的经济发展布局。因为港口是一个社会关联度极高的产业，港口的发展繁荣了城市，而中心城市经济的发展又促进了港口的发展。回顾港口的发展历程极其经济、社会、历史地位、作用的变化，我们可以了解到港口与城市的密切关系，港口对城市、区域、腹地经济的发展和社会进步有着重要的作用，而城市、区域、腹地经济的繁荣，是港口得以发展的重要依托。港口作为一个重要的交通枢纽，是连接国内外贸易的重要环节之一。从制造业的角度来说，一个国家或地区港口经济的发展和竞争力，越来越影响着其制造业的发展和竞争力。区域工业与临港工业的联动性在增强，工业化进程快的国家或地区，港口经济扩张迅速，同时，港口经济发展快，也对工业化起了有力的促进作用。中国正在成为全球最具竞争力的世界工厂，也正在成为最具吸引力的世界市场。这就意味着从世界各地进口大量的原材料、零部件和消费品。所以每年中国港口数以千万计的集装箱吞吐量是一个必然的趋势，中国已经成为全球航运业争夺的主战场。我国大陆海岸线长达18000多千米，自北向南濒临渤海、黄海、东海和南海，13个沿海省份，约48个沿海城市，因此中国港口的发展，对全国的经济发展及文化交流有着重要的意义。到20XX年初，中国大陆的“亿吨大港”已经达到十七个，稳居世界前列。同时，随着物流业近年来的迅速发展，港口间的竞争也愈加激烈。因此，加速港口建设，提高港口工作效率，以提高船舶的利用率和客户的满意度，成为热门研究的问题。港口的服务系统是一个十分复杂的系统，需要各个环节高度协调发展，各种有效资源都应该被合理高效的利用。由于港口的装卸设备都较大型且价格昂贵，增加大量装卸设备来提高港口的物流运作效率并不是管理者的最佳选择。因此如何有效的利用现有的资源，提高设备使用率，合理规划调度，成为了港口服务系统最重要的管理环节。船舶停泊是船舶入港的第一关，是提高港口效率首先要面临的问题，也是衡量一个港口的整体吞吐能力的重要指标，系统中的其他设施都根据港口泊位能力进行相应的配置。船舶到港后，能够在最短时间内靠港卸货，对泊位占用时间越短，货物的周转量也越大，港口的物流效率也会大大增加。为了不使港口的泊位分配成为整个港口系统的“瓶颈”环节，优化港口泊位调度，缩短船舶接受服务的等待时间，同时对泊位系统的工作流程进行仿真，深入了解在某种泊位调度方法下，泊位中各个环节的表现情况，并验证泊位调度的有效性，成为本文研究的重点。1.2 国内外研究现状1.2.1港口泊位调度建模研究现状目前国内外学者针对港口的优化调度问题从不同的角度和层面展开了深入的研究，当前的研究主要包括以下几方面1：泊位分配、岸边吊装设备的规划、港内的车辆调度、堆场空间的分配、堆场起吊设备的调度、闸门资源的分配和码头的整体优化调度。对泊位调度的研究从对象上来看，分为单纯的研究泊位以及把泊位与岸桥或者把整个港口作为一个整体相结合同时研究。从方法上来看，分为通过仿真模拟技术来评价和优化资源调度策略以及通过数学模型的方式来优化最优解。对港口泊位调度系统建立数学模型，求解得出最优解。这种方法的使用有较长的历史，在实际的研究中应用也比较广泛。在通过数学模型来分析优化的研究中，对于泊位单独的研究主要有：Aki Imai采用改进的启发式算法对泊位进行调度分配2。Lai和Shih3提出了一种针对泊位分配问题的启发式算法，这种算法是基于先来先服务(FCFS)的分配策略。Edomal等4也提出了利用排队论对码头泊位分配以及货物处理规划问题建立了模型并且进行了讨论。Imai5等以最小化船舶等待时间为目标，用非线性整数规划模型来分别模拟静态记忆动态码头的泊位调度问题。同时他们也通过研究，证明了在多用户的集装箱码头系统中，在不考虑先来先服务(FCFS)原则的情况下，可以获得较短船舶停泊时间的分配方案，但在这种情况下，会出现某些船舶等待时间过长的情况。Nishimura6等进一步扩展了上面提到的集中模型，综合考虑了水深泊位对泊位调度产生影响的情形，并应用了遗传算法对模型求解。Wang7等设计了应用随机集束搜索算法对泊位分配问题进行求解的方法。李平8等提出利用混合优化策略来提高遗传算法的种群多样性，并加速算法的进化过程，用来求解泊位分配问题。Borwn等9以船舶在港总效益最优为目标，建立了分配泊位的模型。Akio和Etsuko等把泊位分配问题分为静态泊位分配和动态泊位分配两个方面，同时还给出了两种分配问题的模型及其求解方法，重点研究利用拉格朗日松弛法解决动态泊位的分配问题。Jean-Franscois Cordeau等总结了泊位分配中的连续系统模型，并且运用禁忌搜索算法对这个连续模型进行了求解。Chen和Hsieh10通过时空网络模型来帮助决策者有效地进行泊位分配，模型中综合考虑了船舶在港、到港和离港的时间，将这个问题转化成一个边约束的普通网络模型，用分支定界法求得了模型的最优解。Park等11利用基于拉格朗日的次梯度算法对泊位分配问题进行了求解。戈闻怡12用遗传算法求解泊位资源配置调度，得到了所有船舶在港时间最短的最优解。Zhou等13利用模糊理论对泊位调度中的不确定性因素进行了初步探索性研究,得到了良好的效果。而对于将泊位与岸桥相结合的研究主要有：Li14等将泊位岸桥调度问题看作一个可以同时处理多个任务的处理机调度问题，并假设所有船舶在系统开始时就已经在港等候停泊，建立了以船舶在港时间最小为目标的模型，提出了启发式算法求解。类似的，Guan15等将泊位岸桥分配问题作为处理机调度问题，优化目标是将带权重的任务完成最小化时间。韩晓龙16等利用回溯算法求解了泊位岸桥配置优化模型。蔡芸17等采用遗传算法求解泊位分配及岸桥的调度问题，目标是所有船舶在港时间最短。周鹏飞18等重点考虑了船舶抵港时间和装卸时间的随机性，建立了面向随机环境的集装箱码头泊位岸桥调度模型。Daganzo1920等将船舶在港的卸货过程划分成几个不同的区域，使用了整数规划模型对静态岸桥的规划问题进行研究，达到了船舶的等待时间最小的目标。随后，又将岸桥调度过程看作成一个开放的生产计划问题，建立了整数规划模型，利用分支定界法求解模型。Bse等21建立了岸桥等待时间最短的模型，并且建立仿真模型来模拟岸边有缓冲区的集装箱码头的工作流程，在给定集装箱装卸序列的要求前提下为桥吊配备了跨越车并确定了相应的作业序列。韩骏等22将泊位调度与岸桥分配这两个相联系的问题进行了系统分析与集成，以船舶在港时间最小为目标，利用免疫遗传算法对泊位与岸桥协调调度问题建立了优化模型，缩短船舶在港停留时间。柴志刚23为了解决缩短船舶在港作业时间而产生的负面效应，提出了一种均衡理念的优化思想。基于集装箱码头的班轮制特点及泊位调度中的不确定性因素影响，建立了综合考虑船舶靠泊位置、靠泊时刻及装卸速度的均衡优化模型。在求解中采取人机交互与自适应遗传算法相结合的方式，设计了相应的优化算法，并通过算例对模型及算法的有效性进行了验证。Young Man Park24针对同时调度规划泊位和岸桥问题，建立了一个混合整数的计算模型。首先确定船的停泊位、泊船的时间以及将与之班配的岸桥数目，用动态规划技术分配每个泊位的岸桥数量。1.2.2系统仿真技术的研究现状目前对现实系统进行仿真的可以分为三种方案25：基于专用的仿真语言或通用过程语言进行开发；选用仿真器；通用过程仿真平台。这三种方案中，第一种方案的优点是建模灵活，但编程较复杂并容易出错；选用仿真器这种方法则相反，虽然简单易用，但却缺少建模的灵活性，适用于功能比较单一的仿真；而通用过程仿真平台这种方法是在前两者的基础上进行二次开发，目前用途比较广泛的方案并且比较成功的方案都有既简单易用又很灵活的特点。例如，Brooks公司研制的AutoMod，Rockwell公司的Arena，CACI公司开发的Simprocess，ProModel公司的ProModel和Lanner公司的产品Witness的等都是性能很好的仿真软件，目前在各个领域用途均较为广泛26。其中，ProModel(Production Modeling)仿真软件是由美国ProModel公司开发出来用于构造多种生产、服务和系统模型的计算机仿真工具，也是在美国和欧洲使用最广的系统仿真软件之一25。作为当前较流行的一种仿真工具，它能够精确地建立一个经营过程及其资源配置模型，保证模型的随机性、不确定性和相互依赖性，并同时具有为设计者提供连续或离散事件、动态以及随机的分析功能。国外已有采用二维动态仿真技术来研究港口生产系统的运作方式27，以及在港口设计中确定港口资源的合理配置的问题，并已研制出成熟软件，例如澳大利亚的Realtime Business Solutionpty. Ltd推出的港口码头运作仿真软件Xwindow，以集装箱码头为主要仿真对象，利用二维图形对资源配置、堆场规划等问题进行仿真，为港口决策者提供规划依据，并且提高了港口的生产效率。仿真技术在泊位调度方面的研究成果主要有，蔡芸28利用eM-Plant仿真软件建立了以总体船舶在港时间最短为目标的仿真优化模型，生成满足停泊条件和岸桥调度策略的可行分配方案，凭借仿真模型来解决数学模型中的约束条件和岸桥调度问题，当方案不满足约束时，仿真模型终止仿真，调用且返回给遗传算法一个足够大的个体适应度数值，将该方案淘汰，以保证优化结果的可行性。最终得到了包括船舶的停泊时间、停泊位置和为其服务的岸桥数目等要素的优化解。Pasquale Legato 和Rina M.Mazza29运用排队网络模型，采用面向过程的Visual SLAM语言，对港口泊位计划和装卸资源分配进行了研究。唐臣30等也在排队论的基础上，使用Witness仿真软件对集装箱码头的最优泊位数进行研究。鲁子爱31把港口生产视为随机服务系统，建立了模拟港口营运状况的计算机仿真系统。仿真模型中，船舶占用泊位时间根据船舶装卸量、码头泊位装卸效率、气候影响等条件计算确定。在这些研究中，涉及到的一些船舶停泊方面的问题都是在“先到先服务”的基础上，再考虑一些其他的约束条件来提供泊位分配方案，然后依据船舶在港的逗留时间越短越好、泊位利用率越高越好、费用支出越少越好等因素来对各个方案进行评价，选取合理的方案。NamKC等32为韩国釜山Gamman集装箱港口评估今后发展方案，设计了四类仿真场景，采用不同作业策略，优化港口泊位和岸桥数量大小。汪锋33应用Witness仿真软件建立某集装箱码头仿真模型，具体研究在一定吞吐量情况下配备合理泊位数，以及在一定的泊位数的情况下岸桥的合理调度问题，指出了应根据不同的船泊到港密度安排合理的调度方式。1.3课题的研究内容和方法港口泊位61，一般指供一艘船舶停靠系泊的位置，称为一个泊位。具体来说，是指港区内码头岸线供船舶安全靠离、进行作业或停泊所需要的水域和空间。有码头泊位、浮筒泊位、锚地泊位等。船舶在泊位停靠必须满足一定的岸线长度要求以及泊位水深要求，其长度一般为设计船长的120%，接待的船舶越大，泊位就越长，前沿水域就越深。岸桥25，简称桥吊或装卸桥，是集装箱港口使用的最大型的、价格最昂贵的装卸机械。它是港口装卸设备的龙头，主要负责装卸集装箱船舶。泊位调度是指根据码头泊位的数量、使用情况和物理条件为到港船舶或即将到港船舶安排停泊顺序以及泊位停泊。由于泊位是码头的主要稀缺资源，因此在整个港口服务系统中，具有极为重要的影响，直接决定了港口的吞吐量、工作效率。泊位调度理想的结果是船舶不需要等待就可以直接停泊、泊位的利用率达到100%，而这在现实中是不可能达到的。假如由于不可预测的原因，同一时间段内进港船舶较多时，由于泊位数量的限制，船舶就不可避免的要在锚排队等待，而假如泊位的分配不合理，不仅将会造成巨大的经济损失而且会降低港口的竞争力，影响到整个港口未来的发展。为了解决这一“瓶颈”问题，如何提高泊位调度效率，减少船舶等待服务时间是人们一直关注研究的问题。影响泊位调度的主要因素有：船舶相关信息，如到港时间、装卸量等；码头资源情况，如泊位状态、岸桥设备等；物理条件限制，如泊位水深、长度等。目前我国大部分港口泊位调度主要是依靠码头工作人员的经验分配的，或者是由船舶的运营者与港口公司双方的合同规定，在一些现代性国际化的集装箱码头，多采用整数规划或模拟方法，借助智能决策系统来进行码头泊位调度。泊位调度的研究分为离散型和连续型34。离散型的泊位指船舶在停泊时不能同时占用多个泊位，只能停泊在某一个泊位所限定的位置和空间中，受泊位物理条件的限制。连续型泊位是指船舶在停泊时可以同时占用多个泊位停泊。在这种情况下，船舶的停泊将会有更大的选择性，同时对于岸线的要求也更高。另一方面，根据船舶到达时间与泊位分配时间的先后之间的关系，泊位调度还可以分为静态和动态两种。静态调度指在进行泊位分配时，所有需要安排停泊的船舶都已到达港口，这些船舶都将被考虑到下一个停泊时间段中；而动态泊位调度是指泊位分配开始时仍有船舶未到港，但将会在分配时间段中的某时刻到达。本文拟针对船舶靠港“第一关”：停泊，这一动作，研究泊位调度分配的最优方式。在综合考虑船舶本身的条件，包括船长、吃水深度、货运量等条件下，以船舶的总服务时间（包括等待泊位以及卸货时间）最短为目标。由于每个泊位的物理位置不同，船舶停泊后能够为其提供卸货服务的岸桥的数量及状态也不同，因此也影响到船舶的服务时间。我们在研究泊位调度时，应该在考虑泊位空闲的同时，考虑该泊位可用岸桥的数量和状态选择使船舶在港时间最小的泊位停靠，这里在港时间最小包括分配泊位的时间及在该泊位上可用的岸桥的服务时间。若是将两个环节单独调度，先根据最小等待时间为船舶选择泊位停泊，停泊后再等待分配岸桥，则忽视了岸桥的分配对船舶在港时间的影响，造成其他船舶的等待时间加长，具有一定局限性。将岸桥与泊位共同调度则会避免单独调度的局限性，可以使船舶总在港时间更短，并且将提高岸桥的工作效率。因此本文的研究对象是泊位调度以及与泊位相配合的岸桥调度，使得船舶在靠港及卸货过程中，各子系统协同作业。本文拟采用蚁群算法建立数学模型，并利用仿真软件ProModel模拟船舶到港，泊位分配及岸桥卸货整个过程。通过模拟结果分析模型的优劣性，以便求得更符合实际情况的最优解。1.4文章内容安排 本文共分为五章。第一章 绪论。说明本文的研究问题的背景及研究意义，确定本文的研究内容及研究方法，并且确定本文的技术路线。详细介绍了目前针对泊位调度问题、仿真模型等方面的国内外研究现状。第二章 基本技术方法介绍。详细介绍本文中将用到的泊位调度优化模型蚁群算法的原理、特点及算法描述；仿真模型的基本概念、方法及本文中用到的ProModel软件的应用及基本元素。第三章 泊位调度优化。重点论述了蚁群算法求解泊位调度的步骤，设定目标函数、模型的假设约束条件、具体的参数设定及模型求解步骤。将数据代入模型中，求得最优解，分析结论。 第四章 泊位调度仿真。使用ProModel仿真模型，对泊位调度及岸桥分配的整个过程进行仿真模拟。设计符合实际情况的各种基本元素，建立仿真逻辑模型，模拟泊位调度及岸桥分配的处理过程。并且根据第三章中蚁群算法模型求得的最优分配策略，对实际情况进行模拟。分析结果。第五章 结论。分析本文得到的泊位调度模型求得的最优解以及泊位调度仿真结果，总结在研究过程中发现的问题及不足以及对未来的研究的展望。第二章 基本技术方法介绍2.1 蚁群优化算法2.1.1蚁群优化算法的基本原理及特点20世纪90年代意大利学者MDorigo，VManiezzo，AColorni等从生物进化的机制中受到启发，通过模拟自然界蚂蚁搜索路径的行为，提出来一种新型的模拟进化算法 蚁群算法，是群智能理论研究领域的一种主要算法35。用该方法求解旅行商(TSP)问题、分配问题、车间调度问题(job-shop)、车辆路由问题、图着色问题和网络路由问题等36，取得了较好的试验结果虽然研究时间不长，但是现在的研究显示出，蚁群算法在求解复杂优化问题，尤其是离散优化问题方面有一定优势，这表明它是一种有发展前景的算法这种方法能够被用来解决大多数优化问题或者能够转化为优化求解的问题。蚁群算法37是对自然界蚂蚁的寻找路径的方式进行模拟得出的一种仿生算法。这种算法区别于传统的编程模式，它的主要优势在于，有效的避免了冗长的编程和筹划过程，算法本身是基于一定的规则，随机运行来寻找最优解。也就是说，当蚁群最开始找到目标的时候，路径几乎不可能是最优的，甚至可能是包含了很多错误的选择，结果非常不理想的。但是，蚁群算法可以通过蚂蚁寻找食物的时候释放信息素的原理，不断地去修正原来的路线，使所有经过的路径越来越短，由于这种原理，算法被执行的时间越长，所获得的路径就越可能接近最优路径。这种寻径方式类似于我们以前经常用到的通过大量的数据、实验，对结果进行总结分析，最终形成最佳路径的过程。这实际上是类似算法的一个自我学习的过程。蚂蚁在运动过程中，能够在它所经过的路径上留下一种称之为外激素的物质进行信息传递，而且蚂蚁在运动过程中能够感知这种物质，并以此指导自己的运动方向，因此由大量蚂蚁组成的蚁群集体性的行为便表现出一种信息正反馈现象：某一路径上走过的蚂蚁越多，则后来者选择该路径的概率就越大。基于自然界中蚁群寻找食物时的最优路径选择问题，可以构造人工蚁群，来解决最优化问题。在人工蚁群中，我们把具有简单功能的工作单元作为蚂蚁。二者的相似之处表现在，两者都是优先选择信息素浓度较大的路径。较短路径的信息素浓度高，所以能够逐渐被所有蚂蚁选择，也就是产生了最终的优化结果。两者的区别表现在人工蚁群具有一定的记忆能力，能够记住已经访问过的节点而不重复访问。同时，人工蚁群在选择下一条路径的时候是按一定算法规律有意识的寻找最短路径，并不是盲目的。蚂蚁选择下一个目标，向下一个目标的运动是通过一个随机原则来实现的，也就是运用当前所在节点存储的信息，计算出下一步可到达节点的概率，比较并按照这个概率实现一步移动，反复几个过程之后，越来越接近最优解。蚂蚁在寻找路径的过程中，或者找到一个解后，会评价这个解或解的一部分的优化程度，并把这个解的评价信息保存在相关的信息素中。信息素的更新方式有两种，一是挥发，也就是所有路径上的信息素以一定的比率进行减少，这是模拟了自然蚁群的信息素随时间挥发的过程；二是增强，在评价值较好的路径上增加信息素。这种优化过程的本质在于蚁群算法的三个独特机制：选择机制、更新机制和协调机制。所谓选择机制是指信息素残留越多的路径，被蚂蚁选择的概率越大；更新机制表示的是路径上的信息素会随着蚂蚁经过次数的增加而增长，而与此同时也会随时间的以一定的速率有一部分挥发；协调机制是指蚂蚁之间事实上是通过这种信息素的分泌来实现彼此之间的通信，共同工作的。蚁群算法通过候选解组成群体来寻求最优解的进化过程，它包含两个基本的阶段38：适应阶段和协作阶段。在适应阶段，各个候选解根据积累的信息不断调整自身结构；在协作阶段，候选解之间通过信息交流，以期望产生性能更好的解。蚁群算法正是充分利用了选择、更新和协调的优化机制，即通过个体之间的信息交流与相互协作最终找到最优解，使它具有很强的发现较优解的能力。2.1.2蚁群算法描述为了说明蚂蚁系统模型，首先引入旅行商问题39。旅行商问题就是指定几个或n个城市之间的距离，要求确定一条经过各城市当且仅当一次的最短路线。为模拟实际蚂蚁的行为，首先引入如下记号：m蚁群中蚂蚁数量；bi(t)t时刻位于城市i的蚂蚁的个数，m=；dij两城市之间的距离；ij边(i,j)的能见度，反应由城市i转移到城市j的启发程度，这个数值在蚂蚁系统的运行中不改变；ij边(i,j)上的信息素轨迹强度；ij蚂蚁k在边(i,j)上留下的的单位长度轨迹信息素量；蚂蚁k的转移概率，j是尚未访问的城市。每只蚂蚁都是具有如下特征的简单主体：（1）在从城市i到城市j的运动过程中或是在完成一次循环后，蚂蚁在边(i,j)上释放一种物质，称为信息素轨迹；（2）蚂蚁概率的选择下一个将要访问的城市，这个概率是两城市间距离和连接两城市的路径上存有轨迹量的函数；（3）为了满足问题的约束条件，在完成一次循环以前，不允许蚂蚁选择已经访问过的城市。初始时刻，各条路径上的信息素量相等，设ij(0)=C（C为常数）。蚂蚁k (k=1,2,3,m)在运动过程中根据各条路径上的信息素量决定转移方向。蚂蚁系统所使用的状态转移规则被称为随机比例规则，它给出了位于城市i的蚂蚁k选择移动到城市j的概率。在t时刻，蚂蚁k在城市i选择城市j的转移概率 (t) 为：(t)= (2.1)其中allowedk=0,1,n-1表示蚂蚁k下一步允许选择的城市。与之对应的是禁忌表tabuk，表中记录了蚂蚁k已经走过的城市，蚂蚁k在本次循环当中将不再访问tabu表中的城市。ij为能见度因素，和为两个参数，分别反映了蚂蚁在运动过程中所累计的信息以及启发信息在蚂蚁选择路径中的相对重要性。当本次循环结束以后，禁忌表中的数据将被用来计算该蚂蚁所建立的城市访问方案（即蚂蚁所经过的路径长度）。之后，禁忌表被清空，该蚂蚁出发时又可以自由的进行选择。经过n个时刻，蚂蚁完成一次循环，各路径上信息素量根据下式调整ij(n+1)=ij(t)+ij(t,t+1) (2.2)ij(t,t+1)= (2.3)其中，表示第k只蚂蚁在时刻(t,t+1)留在路径(i,j)上的信息素量，信息素的值是根据蚂蚁表现的优劣程度而决定的。蚂蚁经过的路径长度越短，信息素相应的释放的就越多；ij(t,t+1)表示本次循环中路径(i,j)的信息素量的增量；(1-)表示的是信息素轨迹的衰减系数，通常情况下，设置系数1，目的是为了避免路径上轨迹量的无限累加。在蚁群系统中，只有获得全局最优解的蚂蚁才允许释放信息素，这样做的目的是为了使搜索的过程更具有指导性。也就是说，蚂蚁的搜索将主要集中在当前循环位置所找出的最好路径的区域内。全局更新在所有蚂蚁都完成它们的路径后执行，应用下式对所建立的路径进行更新：(r,s)(1-)(r,s)+ (r,s) (2.4)如果(r,s)全局最优路径 否则 (r,s)= (2.5)其中为到目前为止找出的全局最优路径。目前常用的信息素量更新模型有以下几种：（1） 蚁密模型： 其他第k只蚂蚁经过边(i,j) = (2.6)式中，Q为常量；（2） 蚁量模型：其他第k只蚂蚁经过边(i,j)= (2.7)式中，表示第k只蚂蚁在边(i,j)边上的目标函数值（3） 蚁周模型：第k只蚂蚁经过边(i,j)其他= (2.8)式中，表示第k只蚂蚁在整个路径中的目标函数值。以上几种方法的区别主要在于，蚁密模型和蚁量模型的信息素更新都是利用的局部信息，而蚁周模型得信息素更新利用的是全局的信息，即整体信息。这种信息素更新规则会使得最优解的路径上的信息量逐渐增多，与其他路径上的信息量产生对比，加强信息的正反馈功能，提高收敛速度。当问题规模比较大时，由于的存在，使那些从未被搜索到的信息量会减小到接近于0，降低了算法的全局搜索能力，而且过大时，当解的信息量增大时，那些搜索过的解被选择的可能性过大，也会影响到算法的全局搜索能力。通过减小虽然可以提高算法的全局搜索能力，但又会使算法的收敛速度降低为了防止蚁群算法加速收敛和早熟停滞现象之间的矛盾，研究学者提出了自适应蚁群算法的概念，可以在加速收敛和防止早熟、停滞现象之间取得较好的平衡，自适应的调整路径选择概率的确定策略和信息量更新策略。其中，我们可以自适应的调整值，即信息量挥发系数使蚁群算法可以更有效的提高蚁群算法的寻优能力。2.2仿真方法介绍仿真40是利用计算机来运行仿真模型，模拟时间系统的运行状态及其随时间变化的过程，并通过对仿真运行过程的观察和仿真结果的统计，得到系统的仿真输出参数以及基本特性，以此来评价和推断实际系统的真实参数和真实性能。仿真的理论基础是相似性原理，基本思想是利用物理或数学的模型类比、模拟现实对象，通过模型来分析、研究以及将核对。系统、模型和仿真三者有着密切的关系，系统是研究的对象，模型是系统的抽象，仿真是通过对模型的实验以达到研究系统的目的，这三个元素构成了计算机仿真的三个基本要素。系统仿真技术是建立在计算机技术、系统工程、控制工程和模糊相似理论的基础上，通过将计算机作为载体，对系统或活动的过程进行实验并得到模拟结果，从而为人们对系统或活动的研究和决策提供有力的支持。具体来说41，系统仿真是一种求得一个系统问题最优解的计算机技术，尤其是当出现一些不容易建立合适的物理或数学模型的系统时，可以通过建立仿真模型顺利的对系统中的问题进行解决、分析、预测和评价。另外，仿真是是一种“人工”实验，它和实际的系统研究差别在于，仿真实验不是完全根据实际情况和环境进行仿真，而是人为的提出了一些假设条件，作为实际系统模拟出的系统模型以及相应的“人造”环境下进行的。仿真的作用表现在，通过系统仿真，可以评价系统中我们需要关注的环节的性能，估计系统各个部分之间的相互影响关系以及对整体系统运作的影响，在真实系统实施之前就可以通过仿真模拟来比较各种设计方案，从中获得最佳方案。仿真的整个过程也是一个实验的过程，还是系统的收集和累积我们所关注的信息的过程。通过系统仿真，也可以把一个复杂的系统分解成若干个子系统，更有利于分析系统中的子环节。最后，通过系统仿真得到的结果和数据可以引导产生新的认识和决策方案，在系统运行的过程及结果中，也能暴露出原系统中的隐藏问题，以便及时发现解决。随着系统工程与网络技术的迅速发展，系统仿真技术已经在社会经济、环境生态和军事航天等各个领域发挥了重要作用25。仿真系统主要有以下几种类型：（1）离散系统：当所有能引起系统状态发生变化的事件都是离散事件时，该系统称为离散系统；（2）连续系统：当所有能引起系统状态发生变化的事件都是连续事件时，该系统称为连续系统；（3）混合型系统：若这些事件部分为离散部分为连续，则称为混合型系统。具体来说，有两种情况：离散事件导致连续状态变量发生离散变化；连续状态变量达到阈值时，会产生一个离散事件。（4）蒙特卡洛(Monte Carlo)模拟系统：指用随机变量解决一些系统问题的模拟机制。在这样的系统里面，时间对系统的进程及结果没有关键性的作用。大多数管理系统可视为动态离散随机的排队系统。仿真系统中有几个主要的常用术语，也是仿真系统中经常用到的元素：（1）系统的状态：在某个指定时刻，系统中所有系统变量值的集合；（2）事件：导致系统状态发生变化的过程；（3）实体：系统中与研究目的有关的人、物、设备、设施等组成系统的各元素；（4）模拟时钟：模拟系统中表示时间的变量。模拟时钟是在模拟系统中用来记时的工具。2.1.1 港口泊位仿真介绍港口泊位服务系统的仿真设计是指根据港口的实际工作流程，通过仿真的方法对港口进行试验，分析相关影响因素发生的变化的不同情况下，港口泊位系统整体工作效率的不同表现，据此得到最为经济有效的，能够提高泊位服务系统能力的方法42。利用计算机仿真对港口工作流程进行模拟，是根据不同的港口条件(码头锚地规模、泊位数量、港口吞吐量、货物装卸能力等)，模拟港口的运行状况，根据得到的相关港口各环节的数据，为港口建设发展及改进提供相关决策依据44。泊位系统是一个随机服务系统，来港船舶、装卸需求、装卸效率等关键性因素都有不同程度的不均衡性和不确定性。船舶到港由于天气、风浪等原因很容易造成船舶到港时间的不确定，工作的过程当中也会由于天气原因、政策及管理等原因，导致船舶接受服务的时间的不确定。泊位系统是一个离散事件系统。船舶到达港口、进入锚地等待泊位、离开锚地、靠近泊位、开始作业、作业结束、离开泊位等事件均发生在时间的离散时刻。泊位系统在本文的研究当中，看作是一个动态离散随机的排队系统。 港口泊位仿真系统的设计应当遵循以下几个基本原则45：一是系统模型的建立应当符合港口实际情况。只有建立符合实际情况的系统模型，才能用得到的结果正确的指导实际港口的工作。所以在设计港口服务的仿真模型设计时，必须使系统的服务流程、各随机变量的概率分布、船舶的在港活动等设定尽可能的与实际情况保持一致，以保证模型能够反映港口实际运营情况45。二是系统中的假设条件以及参数应有一定的灵活性。例如，港口码头泊位的类型、物理条件、靠泊能力、岸桥的装卸时间、到港船舶的类型分布、船舶到达时间、船舶物理条件、作业类型等参数都是经常变化的，在模型当中必须能够方便地进行修改和调整。2.1.2 ProModel仿真软件介绍ProModel(Production Modeler)是由美国ProModel公司开发出来用于构造多种生产、服务和系统模型的计算机仿真工具46，作为当前流行的一种仿真工具，是在美国和欧洲使用最广的系统仿真软件之一。使用ProModel能够精确地建立一个经营过程及其资源配置的随机性、不确定性和相互依赖性的模型，具有为设计者提供连续或离散事件的、动态的和随机的分析功能，目前在商业、计算机科学、交通运输等多种领域都得到了很好的应用。ProModel在计划和决策支持方面具有非常强大的功能，它可以让我们通过调整站点的数量、速度、输入方式、输出方式，来测试各种设计方案或工艺过程是否可行，对整体系统在各种可能状况下的情况进行评估。当需要设计一个全新的系统或者现有系统进行改进时，我们不需要在花费大量的金钱和时间实施一个我们并不知道是否可行的方案，通过实际运行再从失败中学习经验教训，对方案再进行改造。我们可以先采用ProModel模型来测试一个计划的可行性：通过模拟一个实际的位置或者一个抽象的过程，我们可以通过模拟结果对之进行精确的预测，根据结果反映出的各环节的数据，改进系统的运作，挑选出最优方法来指导操作。ProModel提供了一个人机交互的系统，使用图形用户界面，只需要用键盘、鼠标，根据实际情况选择所需要的工作组件，设定相应操作过程，基本上不需要任何程序，就可以完成一个简单的仿真系统。在系统中，我们可以通过设定参数、变量、选取规则等，关注系统中各个环节的表现情况，测试各种流程的可行性及表现优劣情况。ProModel提供的各种统计结果、统计图等统计资料，可以直观的提供给我们测试结果，以便更直观全面的了解整个系统的运作情况。ProModel的基本仿真元素由两个部分组成：结构部件及运算元素。其中，在结构部件方面，ProModel主要提供四种结构部件47：（1）实体：实体是系统的处理对象，代表实际当中需要被处理的事物。实体可以是输入系统的等待处理的事物，也可以是在系统的处理过程中产生的。实体有不同的属性，在系统中按照一个或多个操作流程接受处理，随着在系统当中的移动，状态发生变化，最终处理完毕后，离开系统。（2）站点：站点是系统中的工作区域，代表实体需要被处理的位置，在系统中是固定的。站点在系统中分为两种，一种是实体在这里进行一个活动或作业，需要花费一段时间；一种是实体在这里等待，直到一些条件满足，触发下一个处理过程，例如，等待资源空闲、等待其他实体到达，等待下一个站点可用。站点中设定了可以处理实体的数量、处理时间，可以在站点中设定选择被处理实体的规则。模型可以对站点的利用率、空闲时间等数据进行统计。在Promodel中，站点分为单个单容量站点、多个单容量站点及多个多容量站点。（3）资源：资源是指为实体服务的人员、设备、空间等，当实体到达工作区域后，将资源分配给实体，实体占有该资源，使用后释放该资源。资源与实体的区别是，实体可以进入系统，经过一系列操作流程后，最终离开系统。而资源则一直在系统当中，等待被使用。在模型中，也可以对资源的占有率等数据进行统计，从而得出资源的充足程度等影响系统工作效率的因素。（4）路径：路径是指实体和资源在系统中的移动路线。在模型当中，使用两点来确定一条路线，这条路线是两点之间的直线最短距离。ProModel的运算元素定义了系统中不同元素之间的交互方式，同时，运算元素还支持结构化编程，可以在任何过程当中调用子程序。主要的运算元素有以下几种：（1）流程：流程是指实体在各站点之间的移动顺序。定义了实体在当前站点完成了相应的处理过程之后，去往下一个的站点位置。若有多个可能的站点，则有相应的选取站点规则。（2）实体操作：是指实体在某个站点中，需要进行的处理过程。我们主要关注的是处理时间。（3）实体到达：实体到达定义了实体进入到系统的时间间隔、每次进入系统的个数等。（4）停顿维修时间：模型中可以对相应的资源、站点等设定停顿维修时间。第三章 泊位调度算法设计3.1基本数学符号S 船舶集合，每条船记为Sj (j=1,2,3,S)；B 泊位集合，每个泊位记为Bi (i=1,2,3,B)；C 岸桥集合，每个岸桥记为Ck(k=1,2,3,C)；Taj 船j的到港时间；Hj 船j的载货量；Dj 船j的吃水深度；Lj 船j的长度；Wi 泊位i的水深；Pi 泊位i的长度；Tsj 船j到达泊位，开始接受服务的时间；Tkj 岸桥k为船j卸货的服务时间；MaxCj 船j可接受的最大岸桥数；Xij 船舶j在泊位i上接受服务，Xij =1，否则Xij =0；Ykj岸桥k在为船舶j卸货，Ykj=1，否则Ykj=0。3.2 数学模型3.2.1问题描述在本调度模型当中，我们将泊位视为一个离散的静态的泊位系统，即船舶停泊时，只能停在一个泊位当中，不能跨越多个泊位，而岸桥可以移动到相邻岸桥上帮助卸货。在系统开始的时间，所有需要分配泊位的船舶到港时间都已经确定，都将考虑到下一个分配的时间段当中。某段时间内有j条船到达锚地，确定每条船的船长、吃水深度、装载量以及最大可以接受的岸桥数。根据船舶停泊的物理限制及需要的岸桥数分配泊位。检查泊位是否空闲，若不空闲，则在锚地等待。当泊位空闲时，船j行驶至泊地i，分配岸桥开始卸货服务。每个泊地上配备有固定的岸桥，岸桥只能为停泊在该泊位上的船舶卸货。当服务完成后，船舶离开港口。3.2.2目标函数本模型的目标是船舶在港时间最短。每条船的总服务时间等于它等待泊位的时间，（Tsj-Taj）即到达泊位的时刻Ts减去它的到港的时刻Ta，加上船舶在泊位上等待岸桥的时间（Tkjs-Tsj），加上为船舶卸货的岸桥k的卸货时间Tk，本文的最优化目标可写成 minTkjs-Taj+Tkj)XijYkj (3.1)3.2.3 假设约束条件 泊位岸桥调度时必须满足以下假设约束条件 (3.2)01 (3.3)Taj-1TaTaj+1 (3.4)TsjTaj (3.5)TkjsTsj (3.6)(Wi-Dj)Xij0 (3.7)(Pi-Lj) Xij0 (3.8)01 (3.9) MaxCj (3.10)Yjk-1+Yjk+1-Yjk=-1,0,1 (3.11)其中，式(3.2) 表示每条船必须被服务一次且仅能被服务一次；式(3.3)表示每个泊位一次只能停靠一条船；式(3.4)表示船舶不会同时到港；式(3.5)表示船必须到达锚地等待后才能被服务；式(3.6)表示船必须在到达泊位等待后才能接受卸货服务；式(3.7)表示在泊位i停泊的船j吃水深度小于泊位i的水深；式(3.8)表示在泊位i停泊的船j长度小于泊位j的泊位长度；式(3.9)表示岸桥为一条船舶卸货完成之后才能为下一条船舶服务；式(3.10)表示为船j分配的岸桥数不得超过其能接受的最大岸桥数；式(3.11)表示为船舶分配的多个岸桥必须是相邻的，Y k-1、Y k、Y k+1是三个相邻的泊位，假如Y k-1和Y k+1在为船j卸货，而Y k没有在为船j卸货，则Yjk-1+Yjk+1-Yjk=2，不符合假设条件要求。此外，还有以下几条假设条件：(1)船舶的卸货时间等于为船舶卸货的岸桥的服务时间；船舶仅能接受这个泊位上的岸桥的卸货服务；(2)船舶卸货时间与船舶类型相对应，是根据船舶的装载量预先确定的。船舶卸货需要的岸桥数与其装卸量的相对应关系如下：当船舶装卸量300箱时，为其安排1台岸桥服务；当船舶装卸量为301500箱时，为其安排2台岸桥服务，当船舶装卸量为501700箱时，为其安排3台岸桥服务。岸桥的卸货速度规定为35箱/小时。3.2.4算法的设计与实现整个泊位调度的过程与TSP问题类似，但是相较TSP问题要复杂一些，其特殊性在于以下几点：1) 在泊位调度问题中，我们将船舶的载货量Hj看做TSP问题中城市之间的距离，把船和泊位共同作为需要遍历的城市。城市之间距离的具体表示方法为：如果两个城市都是船舶，则距离用两个船的载货量之和表示；如果两个城市都是泊位，则距离用所有船舶的载重量之和表示，以减少连续选择两个泊位的概率；如果两个城市中一个是船舶一个是泊位，则距离就用这条船舶的载重量表示；2) 每只蚂蚁的出发点都必须是泊位；3) 在最终的结果中，为了区别泊位与船舶，在给每个城市编号的时候，采取以下规则：船舶从0开始编号，依次递增；泊位的编号则从最后一个船舶的号码开始顺次加1，也就是说，编号比所有船舶编号都大的城市就是泊位。两个泊位之间的编号的船舶，停在前面的泊位上，停泊的顺序与寻径的顺序相同；4) 由于泊位的物理条件的限制，蚂蚁在寻径的过程中，要搜索符合这个泊位限制的船舶，并且要考虑这个泊位上可用的岸桥数量，不符合条件的泊位将不会出现在最优路径中；5) 与TSP问题不同的是，泊位岸桥调度的目标是所有船舶的总等待时间最优化，因此要考虑一个循环的总距离最小。算法中基本的参数设定如下：1、蚂蚁数量：设m是蚂蚁的数量，通过综合考虑算法的全局搜索能力和收敛速度，有研究表明48，蚂蚁数量的选择宜选取m=n/2之间（其中n为问题的规模，即共有多少条船舶需要停泊）。每当一个泊位空闲下来，蚂蚁将开始选择下一个节点，即需要停泊的船舶。2、状态转移概率：在搜索过程中，蚂蚁根据下一个可供选择的船舶的信息量及路径的启发信息来计算下一步的转移概率。(t)表示在t时刻蚂蚁k在i点出发选择j船舶的选择概率：(t)= (3.12) 其中代表信息素浓度的权重，即路径(i,j)上残留信息量的相对重要性。代表可选结点信息的权重，即蚂蚁在运动中的启发期望值的相对重要性。allowedk代表蚂蚁下一步允许访问的城市。根据相关的研究8，选取1.5左右，选取0.55之间，蚁群算法均能获得较好的搜索结果。3、信息素更新规则：在常用的三种信息素更新模型中，根据之前的分析，蚁周模型的效果最好，因此我们采取蚁周模型来更新信息素。信息素更新公式如下：ij(t+n)=(1-)ij(t)+ij(t) (3.13)其中，为信息素残留系数，是一个常数，值的选取直接影响到算法的收敛速度及是否能得到全局最优解。为提高蚁群算法的全局搜索能力，提高其搜索速度，可以自适应的改变的值。根据近年来的研究结果，以及本问题的特殊性，我们选取的初始值为0.85，(1-)ij(t)表示蚂蚁走完全程之后所有留下的信息素的挥发，ij(t)表示信息素的修改。第k只蚂蚁经过(i,j)这条路径否则ij(t)= (3.14)其中，Q为信息素强度，表示第k只蚂蚁在整个路径中的目标函数值，即船舶等待时间。当算法求得的最优值在N次循环内没有明显改进时，减为若0.95(t-1) min否则(t)= (3.15)其中min为的最小值，可以防止过小降低算法的收敛速度。具体的蚁群算法步骤如下：Step 1 初始化蚁群，时间计数器t=0，迭代次数IT_COUNT=0，ij(t)=C，ij(t)=0，合理的设置各项参数。同时设定好问题中的具体数据，包括船舶的物理条件、泊位的物理条件、船舶的载货量及最大可接受岸桥数等，根据船舶载货量计算两城市之间距离；Step 2 初始化可行结点集合，建立一个禁忌表，将k只蚂蚁的起始位置放入其各自的tabu表中，设置链表的索引s=1；Step 3 对于第k蚂蚁，从起始点Bk出发，根据状态转移规律选择移动到船舶j，这里有几种可能性：若泊位Bk符合船舶的停泊要求，则将位置(k,j)放入tabu表中，算法继续进行；若船舶无法停泊在此泊位，则选择下一个泊位，即Bk+1，重新进行step 3。重复此过程直到链表满，即所有城市都被访问过。Step 4 应用信息素更新规则。根据各条路径计算船舶的等待时间，选出局部最优路径，与目前找