A 港口集装箱码头岸桥与场桥配套仿真研.doc

大连海事大学毕 业 论 文二一三年六月A港口集装箱码头岸桥与场桥配套仿真研究专业班级：物流管理三班姓 名：吴岳指导教师：郑红星交通运输管理学院摘 要摘 要集装箱码头是一个离散，随机的作业系统，具体可以表述为：利用码头的各种装卸设备、运输设备等硬件资源及相关信息资源，并对集装箱船舶靠泊作业、岸桥装卸作业、集卡水平运输作业、场桥堆码作业等环节的控制以实现对到港船舶进出口作业的系统。2012年全球港口发展报告指出，受全球经济环境持续恶化的影响，国际贸易量、海运量增速下调，全球主要集装箱港口呈现出一派萧条的景象，2012年港口货物吞吐量增速不足5%。对于任何一个集装箱码头而言，其首要考虑的问题是面对随机到来的装卸任务，如何合理的配置装卸设备,给出最佳的设备调度方案。以便于提高码头整体的作业能力，达到客户最大满意度，同时降低码头生产运营成本。针对集装箱码头设备配套的相关研究不胜枚举，泊位和岸桥都是码头的稀有资源，其配置是否合理直接影响船舶在港时间，场桥作为堆场最主要的装卸设备已成为诸多码头堆场瓶颈资源，其效率低下直接决定了内外集卡的等待时间，影响客户满意度。考虑到短期内集装箱码头挂靠船舶的装卸量可以通过船东发给港方的预配图获悉，同时泊位与岸桥配置与作业计划短期内固定。本文主要研究的是针对特定泊位与岸桥分配计划下，以所有集卡等待与场桥大车移动成本之和最小为目标建立场桥配置及调度的集成模型，以便于得出A港口某营运时段内的岸桥与场桥配套比和各箱区内各台场桥的具体调度方案。设计了求解集成模型的改进遗传算法(带基因修复技术)，针对A港口实际作业情况选择实验算例并利用Matlab编译改进的遗传算法求解算例。最后利用Flexsim仿真软件进行优化结果的分析验证，并以设备利用率等为评价指标对提出的配套及调度方法与A港口现有方法进行比较。关键词：集装箱码头; 设备配套; 场桥调度; 改进遗传算法; Flexsim仿真分析IABSTRACTABSTRACT Container port is a discrete and random operation system which can be described as below, make full use of the facilities and the information technology in order to control the whole import or export operation system including vessel berthing system, the Q/C discharge/load system and horizontal transport operations and so on. “Global port development report of 2012”points out the increasing pace of global trade and seaborne trade volume is decreasing with the constant deterioration of the global economy ,the container volume growth is only less than 5% and all the container harbors are in depression now and the nightmare will last long judging from the current status of global trade. For every container port, the most important urgent problem is how to improve the efficiency and productivity when faced with uncertain work order, which will come true only when the terminal facilities are well arranged both in the quantities and the schedule, as a result, the ports can satisfy customers and save operation cost at the same time.Its true there are plenty of facility matching research, berth and quay crane are rare resources for every port and have a direct effect on the window time of each vessel, and as the most import facility in the yard, yard crane is actually the key resource in the yard and it determines the waiting time of not only the inner truck but also the outside truck, which is a good indicator showing the service of the port.Considering the shipping liners or the shipping agents will send the preplan to port 48 hours before the ETA, which berth and quay crane to be used is fixed in a short period, so hereunder the research is based on assigned order and the quay cranes and berth are fixed, we build a model to find the best scheduling and quantity for the fixed work, we are targeted at the total cost of waiting time of trucks and the moving cost of yard cranes, thus we created the improved GA for such model and got the best quantity and assignment for the fixed work order for the example port A, then we made the Verification with the simulation software Flexsim and got proved by some indicators like utilization rate of the key resources Key words: container port; facility matching ; yard crane assigning; improved GA; Flexsim simulation researchII目 录目 录第1章 绪论11.1 研究背景及意义11.1.1 研究背景11.1.2：研究意义11.2国内外对岸桥与场桥配置与调度研究现状21.2.1 码头整体资源配置的研究现状21.2.2 泊位与岸桥集成调度研究现状31.2.3 场桥配置及调度研究现状31.3 本论文的主要内容及组织结构31.3.1本文主要内容31.3.2 文章组织结构41.4 本章小结5第2章 集装箱码头及业务流程概述62.1 集装箱码头简介62.1.1 集装箱码头定义及功能62.1.2 集装箱码头工作流程62.2 集装箱码头主要设备分析及介绍72.3 岸桥、场桥设备配套及调度研究92.4 本章小结9第3章 集装箱码头岸桥与场桥配套问题103.1 问题的描述103.2 模型假设113.3 场桥配置与调度集成模型建立123.4 本章小结14第4章 改进遗传算法设计154.1 遗传算法概述154.2 针对模型设计改进遗传算法174.2.1 染色体编码方式174.2.2 初始种群的生成174.2.3 适值函数与选择机制174.2.4 交叉操作184.2.5 变异操作与终止规则184.2.6 基因修复技术184.3 本章小结19第5章 实验分析205.1 实验案例205.2 实验结果分析225.3 本章小结23第6章 仿真分析246.1仿真系统主要参数与统计分布246.2仿真结果的分析与比较266.3本章小结26第7章 总结与展望277.1全文总结277.2研究展望27参考文献：28致 谢29附录：IIVA 港口集装箱码头岸桥与场桥配套仿真研究A港口集装箱码头岸桥与场桥配套仿真研究第1章 绪论1.1 研究背景及意义1.1.1 研究背景国际贸易中约87%是通过海运方式完成运输的，集装箱运输自从1957年一经面世便受到世界青睐，现代集装箱化运输更是取得了飞速发展，集装箱化运输已经成为现代交通工具不可缺的组成部分，其高货运质量、高运输效率及便于多式联运的特征，为全球经济与贸易的发展做出了卓越贡献。集装箱化运输是以多个运输环节组成的完整体系来进行的，而集装箱港口是集运体系的枢纽，集装箱需要在港口进行换装，集散，保管及临时堆存。集装箱港口在现代物流业的发展中有举足轻重的贡献，一些发达国家甚至将其看成是体现本国物流竞争力的重要标志之一。经济危机爆发前海运市场蓬勃发展，港口产业随之高速发展，最高集装箱吞吐量年增速已达到32.9%，而2012年全球港口发展报告指出自2010年起全球集装箱吞吐量增幅以近50%的速度收缩，2011年同比增幅仅为3.96%，2012年港口货物吞吐量增速不足5%；同时马士基航运北亚区首席执行官施敏夫预计2013年全球海运集装箱的需求增长在4%-5%，而运力增长约8%；马士基公司还会继续通过减速航行、拆船、闲置运力等方式积极调整运力。这些都表明集装箱码头需要更好的满足客户需求，最大限度地缩短船舶在港时间，提高装卸效率，为客户提供增值服务，进而保持现有及增加潜在的船东挂靠本港，这需要港口码头合理高效的利用空间资源及各类设备资源。集装箱码头在初期发展时期，想要通过完善泊位资源、扩大码头生产作业设备等手段来提高码头通过能力，这种规模扩张的手段为港口增速带来的发展空间会随着港口吞吐量的不断提高、港口内外部环境日益复杂而慢慢缩小，逐渐呈现规模不经济，会因为码头运行成本的大幅增加给码头带来很多负面影响，如何有效利用码头各种有限资源，适应集装箱运输机船舶大型化发展趋势，提供船舶在港最快时间服务以及如何处理码头生产调度中诸多的不确定问题，高效服务，是目前研究者面临的一大难题。 1.1.2：研究意义2012年全球集装箱港口吞吐量排名前二十名我国占有八席，我国集装箱码头生产作业能力确实是在不断提高，但不容忽视的是目前来看我国大部分集装箱码头的生产自动化程度比较低，堆场堆存计划、集卡配置、岸桥与场桥配套等调度问题还有单纯依靠人工经验来完成的情景，而且生产设备配套问题存在针对性差的弊端，这种生产管理难免会对集装箱码头作业系统的高效性、稳定性、及时性和可靠性带来不利影响。很明显的就是这种作业量变化中产生的设备闲置问题，码头生产作业中泊位是稀缺资源，岸桥购置成本最高，场桥其次正如“木桶理论”，如何解决这两种稀缺资源的配套优化问题就成为了重中之重，故而设备配套问题的分析具有重要的现实意义和理论意义。现实意义a：当今萎靡的外部环境加之日趋激烈的港口竞争对港口服务提出了严峻的考验，优化集装箱码头生产作业方式、设备配套，生产调度模式可以有效缩短船舶在港停泊时间、提升服务质量，争取当今及潜在船东航线挂靠本港。b：集装箱码头作为集运网络中的枢纽，其装卸作业及时性、运行安全性、生产服务可靠性将直接影响整个集运网络的运作效率，宏观来看会影响航运企业及各贸易主体及整个网络上每个环节的运作成本，因此唯有通过集装箱码头作业系统的高效作业，才能保证整个网络健康发展。c：集装箱码头是一个随机性很强的作业系统，受多种因素影响，调度问题也随之存在复杂性，有效率的作业资源调度与配置不仅能够有效缩短船舶在港停泊时间，同时也能减少码头生产作业成本。理论意义集装箱码头系统内各环节相互影响、相关制约，码头生产作业流程具有时间和空间上的双重复杂性。为了实现集码系统内整体生产最优，处理优化目标函数与约束条件间相关关系，有效求解针对问题所建立的相关模型，一直以来都是集装箱码头生产调度问题研究的难点和重点，本文所指岸桥与场桥设备配套优化，是指通过对己有研究的分析，系统地归纳解决特定的集装箱码头岸桥数固定，也就是分配到堆场任务一定的情况下，算出对应与此岸桥数量的场桥数量并算出详细的场桥调度方案，建立针对随机任务码头岸桥调度及场桥配备的数学模型并设计相应的算法求解，然后利用Flexsim仿真软件对配套优化结果进行分析验证。因此上述问题的研究有很重要的理论意义。1.2国内外对岸桥与场桥配置与调度研究现状1.2.1 码头整体资源配置的研究现状Ebru K. Bish将船舶装卸，岸桥调度及集卡分配描述为一个转运问题，提出启发式算法，以到港船舶最长在港时间最小化为求解对象。杨静蕾建立起一个包含泊位、岸桥、场桥及集卡等资源在内的排队模型，通过实际算例求解出设备最佳配比。李浩渊运用面向对象的系统仿真建模方法，构建了集装箱码头整体物流作业系统的仿真模型。将优化算法和仿真模型相结合，进行了设备配套探究。计明军等人通过集卡码头内作业运行路径分析建立模型求解出最佳的集卡配置数量。徐远琴等人分析了集卡，岸桥场桥联合调度，建立了以等待岸桥，场桥作业时间及运输时间最短的优化模型。1.2.2 泊位与岸桥集成调度研究现状随着研究的深入，泊位与岸桥调度的研究从静态泊位调度发展成动态泊位调度，从离散发展到了和连续调度。这些研究大多是建立在一个长时间序列里以最小化船舶在港时间为目标。由于泊位作为船舶靠离无力空间需要岸桥进行装卸作业，研究者一般将泊位与岸桥同时考虑调度问题。Yang等人设计了一种基于进化算法的方法，来求解泊位与岸桥集成调度问题。Zhou等人研究了随机环境下的泊位与岸桥调度模型，最小化船舶在港等待时间。Lee等在考虑岸桥效率的基础上，采用遗传算法研究了离散泊位的调度问题。1.2.3 场桥配置及调度研究现状关于场桥的优化调度与配置，目前大多采用的是固定时间窗口的研究，以最小化任务量为目标。Richard Linn研究了以倒箱率最少为目标的场桥配置问题。Kap Hwan Kim等人以场桥作业路径最短为目标建立优化调度模型，并运用分支定界法进行求解。Kozan等人利用遗传算法模型模拟了堆场装卸设备的分配问题。Kap Hwan Kim以最小化场桥提箱总时间作为目标建立了混合整数模型，Linn等人构建了一种基于整数规划的场桥动态调度模型和启发式算法。曾庆成等研究了场桥调度优化问题，建立了混合整数规划模型，利用随机贪婪适应性搜索方法对遗传算法进行改进。Zhang等将场桥调度和堆场空间分配作为一体构建场桥动态调度模型，设计出整数规划与动态规划结合的场桥调度方案，并利用仿真对结果进行了验证。1.3 本论文的主要内容及组织结构1.3.1本文主要内容（1）介绍集装箱码头及业务流程，介绍港口关键的装卸设备及其重要性。（2）针对随机装卸任务量的固定泊位，固定岸桥数量进行场桥配置及调度的模型的建立。（3）针对A港口集装箱码头具体情况选取算例，实验得出岸桥与场桥配套比；各箱区各场桥详细调度方案。（4）利用Flexsim仿真软件对优化的结果进行仿真分析验证，并与A港口现行的运作方式对比。1.3.2 文章组织结构第1章 介绍文章研究背景及意义，国内外相关课题研究现状，阐述了集装箱码头关键设备配套及调度优化的重要性。第2章 介绍集装箱码头及业务流程，解释岸桥场桥稀有资源的装卸工艺，引出建立模型必要性。第3章 提出集装箱码头装卸设备配套问题，并针对特定装卸任务建立场桥数量配置及详细调配方案的模型。第4章 针对所设计模型改进遗传算法设计。第5章 针对A港口实际情况选取算例并对结果进行分析。第6章 采用Flexsim仿真软件对A港口模型计算出结果进行仿真分析。发现采用模型计算出结果设备利用率比A港口目前设备利用率高，成本低，即可对模型设备配套优化结果进行仿真验证。第7章 总结与展望本文研究思路见图1.1国内外文献阅读 明确研究问题确定决策变量分析影响因素改进遗传算法建立设备配套模型算例实验模型求解场桥调度方案场桥配置数量仿真验证结果分析图1.1 本文研究思路1.4 本章小结第一章绪论主要阐述了当今萧条经济环境下优化港口生产调度对码头，港口，供应链涉及主体甚至全球贸易都有重要影响，解释了场桥配置及调度方案优化对短期内降低码头成本，提高服务质量的理由，并对全文奠定了行文思路。第2章 集装箱码头及业务流程概述2.1 集装箱码头简介2.1.1 集装箱码头定义及功能集装箱码头是指包括港池、锚地、进港航道、泊位等水域以及货运站、堆场、码头前沿、办公生活区域等陆域范围的能够容纳完整的集装箱装卸操作过程的具有明确界限的场所。码头资源包括泊位、岸桥、场桥、堆场、控制室、大门等，涉及到装船，卸船，集港，疏港，堆存转运等功能，是水路联运的枢纽，是多式联运转换运输方式的缓冲，也是货物的交接点。图2.1为集装箱码头平面布局图。图2.1 集装箱码头平面布局图2.1.2 集装箱码头工作流程集装箱码头作为动态，高效运营系统，主要可以分为进口工作流程与出口工作流程。1进口工作流程（1）卸船作业。在船舶靠港48小时前，调度部门从船公司或者船代处取得船舶进口舱单、船舶积载图、船期计划等进口信息，制定集装箱船舶靠泊计划和卸船顺序单等，具体应包括时间信息、泊位信息、堆场信息和交接信息等内容。然后进行靠泊作业。靠泊时候由港调部门提前安排好引水、拖轮等工作。完成靠泊后码头调度组织按照卸船，并在卸船完成后做好记录，发给船公司或船代装船结果。 (2) 堆场作业。包括收箱、移箱、翻箱、倒箱装卸和提箱计划等。收箱时，集装箱先由内集卡运送到堆场，按照提前制定的堆场作业计划，利用场桥将集装箱卸到指定的箱位。 (3) 出场作业。收货人依据从船公司或船代换来的提货单和海关的放行证明来办理集装箱的提箱手续。在集装箱的设备交接单上签字，交接完毕后收货人凭借出场证明在闸口处通过检验后，完成出场作业。进口工作流程图可以简化为图2.2船舶配载图等进口信息车队来港提箱靠泊计划堆场作业核实签字卸船计划 闸口检验 图2.2集装箱码头进口工作流程2出口作业流程出口作业流程可以看做进口相反的方向，分为进场作业，堆场作业，装船作业三方面。首先码头调度人员按照船公司提供的预配船图和出口舱单，充分考虑到码头现有设备运作情况，堆场堆存情况编制装船作业计划，集港计划，堆场堆存计划等，在规定入港时间入港集装箱暂存在堆场中，转船前要核对到场集装箱的海关放行信息及船公司提供的订舱信息，然后编制船舶预配载图，并据此编制转船顺序单，转船完毕后做好核查工作然后编制出口单船小结和转船清单。2.2 集装箱码头主要设备分析及介绍 国内外如此多的研究都将码头设备研究的重点放在岸桥与场桥的研究上，足可以看出这两种购置成本最高的港口资源的重要性，实际中岸桥与场桥配置调度不合理也是大多数集装箱码头的高效工作的瓶颈所在， 因此在此我们对两种设备做简要介绍。 1.岸桥岸桥全称岸壁集装箱装卸桥，大多数集码使用岸桥进行集装箱装卸船作业。岸桥主要是由带行走机构的门架，臂架及承担臂架机构的拉杆等构件组成。通过带行走机构的门架，岸桥可以沿着和码头岸线平行的轨道移动，从而进行换位、换舱和换泊位的作业，但是因为电缆线长度和电缆坑的限制，在移动时活动范围也受到一定程度的影响。臂架主要是用来承受配有集装箱专用吊具的岸桥小车的重量的，小车自带升降机构，可沿臂架轨道前后移动吊运集装箱。臂架包括陆侧臂架、海侧臂架和门中臂架三个部分。海侧臂架通常是可变幅式的，为的是在岸桥移动时，可以将海侧臂架仰起，确保船舶或航道的安全，岸桥图片可见图2.3图2.3 集装箱码头岸桥2场桥集装箱龙门起重机简称场桥，是集装箱码头堆场进行装卸、搬运、堆码作业的主要机械，通常由起升机构、小车行走机构和大车行走机构等三部分组成。按照行走方式的差别，又可分为轮胎式龙门起重机(RTG)和轨道式龙门起重机(RMG)。轮胎式场桥机动灵活，能够进行转场作业，通用性好，技术成熟，但也有环保条件差，噪音较大等缺点。轨道式场桥一般比轮胎式场桥大，具有堆垛层数多，装卸效率高，稳定性好，可靠方便，结构简单，污染性小等优点，但因为自身特点，作业范围受轨道限制，机动性差，对地基条件要求较高，设备投资成本也较高。目前在我国，大多数的集装箱码头堆场选择使用的机械还是轮胎式场桥，本文的主要也选用轮胎式场桥作为研究对象。如图2.4所示图2.4 场桥2.3 岸桥、场桥设备配套及调度研究 岸桥作为直接装卸船舶设备其效率直接决定船舶在港停泊时间，但是岸桥的作业效率同时与堆场装卸效率息息相关，原因在于内集卡作为岸桥与堆场的衔接，同时堆场中关键装卸设备场桥的效率还直接影响进出场区外集卡的等待时间，总而言之，岸桥与场桥配套优化调度对于集码来说是非常重要的，本文认为考虑到短期内泊位与岸桥使用数量在船舶靠泊48小时的靠泊计划中已经固定，所说的岸桥场桥设备配套优化调度是在短期任务量，泊位、岸桥开放数固定的情况下，如何在场区配置和岸桥数量配套的场桥数量，并根据装卸任务设置高效的场桥详细调度规则，如此既可以缩短码头内集卡等待场桥作业的时间，从而缩短船舶在港时间，提高集装箱码头集装箱吞吐量同时还可以缩短外集卡的提箱和集箱作业时间，从而缩短外集卡在码头内的时间，减小了港口大门作业的负担，同时能保证集疏运系统的高效。具体简单工艺流程图如下图2.4集装箱船大门集装箱堆场外集卡场桥场桥内集卡岸桥图2.5岸桥场桥装卸工艺流程图2.4 本章小结本章首先简单介绍了集装箱码头定义功能及进出口流程，介绍了岸桥场桥及其工艺流程，并进行了设备配套调度的剖析，解释了在短期内对于拥有固定泊位岸桥的码头作业情况下，分配到各个场区的任务量一定时场桥优化调度所起的关键作用。9A 港口集装箱码头岸桥与场桥配套仿真研究第3章 集装箱码头岸桥与场桥配套问题本文中集装箱码头装卸机械的优化配置指的是在岸桥数量和作业计划已定的情况下，如何调配适当数量的场桥相配合，以使集装箱船舶高效、顺畅地完成装卸任务。之所以如此认为，是因为码头实际短期生产作业中，港方会在船到港前48小时收到船公司或者船代发来的卸船图及预配船图，清楚装卸箱量安排泊位计划，由于泊位作为船舶物理停泊空间，而真正装卸船舶的是岸桥，泊位计划固定也可以看做是岸桥使用数量已知，相比之下，短期内场桥配置包括数量和调度规则的改善能更好的提高服务效率，降低成本。3.1 问题的描述通常情况下，码头有多条船同时靠泊，场桥在堆场作业时有可能要装卸来自不同船舶的集装箱，甚至还要为集疏运作业的外部集卡提供服务。然而为了提高集装箱船舶的作业效率，避免不同船舶的作业干涉，码头公司一般会开辟出相对独立的堆存区域，场桥也只装卸相对固定的区域内的集装箱，并且通过对集疏运作业的时间预约控制来防止外部集卡对船舶装卸作业的干扰。大部分学者均不将外卡列入研究之中，但本文将研究混合堆存模式下岸桥-场桥的配置及调度问题，故必须将外集卡加入到研究中。并且为了防止堆场内各箱区作业量不均衡，本文不会将场桥固定给某个岸桥且内集卡也是不固定于场桥或岸桥。如此一来在各箱区内的场桥只管完成计划期内的装卸任务列表，不管是为哪个岸桥服务，便于充分利用较少的场桥资源来如期完成任务。目前我国集装箱码头大都采用分堆模式堆存，但也有少部分港口为提高空间利用率选用了混堆模式。此模式下场内箱区中场桥既要执行装船过程又有卸船作业，当然若是同一条船的话，岸桥也是有装有卸，也可称为同步装卸作业。这种装卸作业方式下各个箱区内某个箱位对应的箱子类型可能是进口箱、出口箱、重箱、空箱，待提箱其中的一个(均设为20尺箱)，故场桥要服务的集卡包括：重载内卡、重载外卡、空载内卡，空载外卡，而且集卡作业时间和要求也不同，如图3.1所示（场桥与贝位均按照从左往右的方向编号）。考虑到内集卡的服务时间直接影响船期，而外集卡的服务时间影响场外客户满意度。因此在岸桥数量和作业计划已定的情况下，堆场内各混堆箱区场桥的配置与调度问题具有很高的研究价值。堆场各箱区内场桥配置与调度问题可视为首先，如何将各箱区内配置合理的场桥能力；其次将各箱区内所有任务在各场桥间分配；最后确定各箱区内的各场桥装卸任务的序列。以往大部分学者都将配置与调度分开研究，即在已知场桥配置的前提下确定场桥的调度方案或者在已知场桥作业规则的前提下测算场桥的合理配置数量。本文研究的理念是在一段时间内堆场内须作业的各箱区内的任务量已知，且每个任务的箱位确定，但对应的集卡到达作业位置的时间不同的前提下，如何确定各箱区内场桥的合理台数与配入箱区后的各场桥装卸任务次序，使得所有集卡等待与场桥大车移动成本之和最小的同时保证超过等待上限的集卡尽量的少。图 3.1 混堆集装堆场布局与作业示意图3.2 模型假设考虑到以下两点：一，堆场内的任务会随着时间的推移而产生或多或少的变化，即并非一个稳定任务系统。二，集卡前来接送箱的时间具有动态性，但是提前较短一段时间的集卡到达时间是可以通过预约或统计分析准确获知的。可是若计划期提前时间太长肯能会导致与实际不符，进而使得所求得的计划完全无效。综合考虑以上两点，本文将计划期长度设为2小时，即每2个小时对堆场内进行一次配置与优化，以便尽可能地达到实时优化的目的。(1) 各个箱区内的各个任务的箱位与装卸耗时已知(2) 计划期内各个任务对应的集卡到达时刻已知(3) 只有当任务对应集卡到达指定作业位置后场桥才能实施装卸(4) 各个箱区内的相邻场桥之间不可以相互跨越且须留有安全作业距离(5) 外卡等待时间超过上限后优先级高于未超等待上限的内卡。内卡等待时间超过上限优先级最高，且必须被服务(6) 考虑到单个箱区空间有限，各箱区最多配置3台场桥3.3 场桥配置与调度集成模型建立参数说明：M为码头堆场可用的场桥数；N为计划期内箱区b内的任务集合；n为N中包含的任务总数；Y表示计划期内箱区b内配予的场桥数；K为箱区b内场桥m装卸的任务总数；X表示箱区b内场桥m第i个装卸的任务的编号；r为箱区b内场桥m第i次装卸的任务对应集卡到达作业位置的时刻；h为箱区b内场桥m完成第i次装卸的任务所需时间；t为箱区b内场桥m完成其第i次装卸的任务的时刻；W为0-1变量且当箱区b内场桥m第i次装卸的任务对应集卡是内卡时取0,否则取1；为箱区b内场桥m的大车从一个任务移到其紧后任务处需要的时间；B为泊位、岸桥已分配且作业计划已定后给堆场内形成的待作业任务箱区总数；B为箱区b内场桥m第i次装卸的任务所在贝位；B表示一箱区内总的贝位数；为箱区b内场桥m在某时刻t所处的贝位，；b表示相邻场桥间留有的安全作业贝位数；t用于定义系统的初始时刻，视为0；C为场桥大车移动单位时间需要的成本；C为箱区b内场桥m第i次装卸的任务对应集卡等待单位时间的成本，且变量具体取值为Cimb=0, Wimb=1且等待时长30minutec1, Wimb=1且等待时长30minute c2, Wimb=0; i=1,2,3KmbT为内集卡等待时间的上限值；T为外集卡等待时间的上限值；V为场桥大车的移走速度；I为单个贝位的长度。上述参数中Y、X 、K是模型的决策变量。目标函数：MinC0*b=1Bm=1Ybi=1Kmbd(i-1)imb+b=1Bm=1Ybi=1KmbCimb*(timb-himb-rimb-30*Wimb)约束条件：timbhimb+rimb (1)timb=himb+maxrimb，t(i-1)mb+d(i-1)imb (2)d(i-1)imb=Bimb-B(i-1)mbV0*l0 (3)XimbXjmb,iji,j=1,2Kmb (4)XimbXjm+1b,iji=1,2Km;j=1,2K(m+1)b (5)m=1YbKmb=nb (6)Pm-1btPmbt-bsafe (7)Pmbt1，B0 (8)timb-himb-rimbT1，Wimb=1T2，Wimb=0 (9)b=1BYbM (10)C,C0,C1,C2,l0,B0,V0,bsafe,T1,T20 (11)Cimb0,c1,c2 , Wimb0,1 (12)XimbNb , Kmb1,2,3nb-1, 0Yb3 (13)以上式中：b=1,2,3B；m=1,2Y；i=1,2K上述模型中，目标式的左半部分为堆场内所有作业场桥的大车移动成本，右半部分为所有的内/外集卡等待成本。约束(1)保证任一个任务的完成时刻不早于该任务的集卡到达时刻与装卸时间之和；约束(2)为某任务完成时刻、集卡到达时刻、装卸时长等之间的等式约束；约束(3)为任一场桥从某装卸任务移动到其下一个装卸任务所需时间的等式约束；约束(4)、(5)、(6)共同保证了一个任务只能由一台场桥装卸且只能被装卸一次；约束(7)保证各个箱区内相邻的场桥之间不会穿越且留有安全作业距离；约束(8)保证在计划期内的任意时刻各场桥均不会跑出所在箱区；约束(9)保证各任务对应内/外集卡的等待时间不能超过其上限；约束(10)保证配置到各个作业箱区内的场桥总数不超过码头可用上限；约束(11)、(12)为参量的取值约束；约束(13)为决策变量的取值约束。3.4 本章小结本章首先阐明岸桥场桥设备配套问题，认为短期内码头装卸任务，岸桥数固定，建立模型来配置场桥数量与调度规则来达到所有集卡等待时间及场桥移动成本最小。第4章 改进遗传算法设计4.1 遗传算法概述遗传算法是1975年美国Michigan大学J. H. Holland教授在从事机器学习时发现学习不仅可以通过单个生物体的适应来完成，还可以通过一个种群的进化适应来加以实现。Kenneth De Jong 将这种算法用于解决优化问题。Holland 研究遗传算法是从设计和实现一种能应付变化的、不确定环境的鲁棒性好的自适应系统开始。他认为这类系统的自适应是从其所处环境中随时得到反馈的函数关系，因而形成我们今天称之为简单遗传算法的再生计划(Reproductive Plan)。这种简单的遗传算法只是一类具有固定种群(Population)规模、个体用固定长度的基因链的一个抽象模型。依据适应度(Fitness)随机地选择双亲并通过交叉(Crossover)和变异(Mutation)算子获得新的种群。遗传算法的特点是其算法中不包含待解决问题的具体形态。它是从改变基因的配置来实现问题的整体优化的，因而属于自下而上的优化方法。类似于生物的进化过程，遗传算法处理的是变量集合的编码而非变量本身。它对结构对象进行直接操作，不存在求导和函数连续性的限定，具有内在隐并行性和较强的全局寻优能力。采用概率优化寻找方法，能自动获取搜索空间。自己能够调整搜索的方向，不需要一些人为确定的规则。遗传算法的这些特点已被人们广泛地应用于组合优化、机器学习、信号理、自适应控制和人工生命等领域。它是现代有关智能计算中的关键技术之一。遗传算法作为进化算法中的一员，是用于解决最优化问题的搜索算法。该算法的实现方式通常为计算机模拟。遗传算法借鉴了达尔文适者生存、优胜劣汰、物竞天择的自然选择和遗传机理，深受大自然从低级、简单向高级、复杂转变规律的启发，从人类漫长却绝妙的非凡进化过程汲取精华，可见遗传算法是以自然界生物进化理论为基础慢慢发展起来的，其中生物进化过程如图2所示。相关概念在生物遗传理念中映射如表1所示。图4.1 生物进化过程表4.1 GA的概念与生物遗传理念的映射关系生物遗传相关概念GA中的功能适者生存目标值越大的解越容易被保留个体解染色体字符串；行/列向量；多维数组基因解的每个分量适应性适应度值函数群体选定的一系列解集合种群按照适应度函数选择后的解集交叉按交叉规则产生新的解变异某些基因变化在使用遗传算法时，个体就代表优化问题的解，表现为一个变量的序列，称之为染色体或基因链。染色体的表达方式多为字符串或者数字串，但是也有根据特殊问题凸显的特点来设置与问题对应的染色体表达方式，即是该算法的编码过程。首先，随机产生一定数量的个体，某些特殊情况下为了提高初始种群的质量，也可以对此随机产生过程加入人为的干涉。各代的每一独立地个体都要被评价，评价的结果通过预设的适应度函数计算得到对应个体的适应度值来表现。然后按照适值大小，对种群中的个体进行排序，高于初始种群低适应值的个体排在前面。 其次，下一代个体产生、组成新的种群，这一过程通过一系列的选择操作、交叉操作和变异操作来完成的。选择，是根据新产生个体的适应值，但又不完全以适应值高低作为选择准则来进行的操作。如果单纯依赖适应值高低、选择适应值较高的个体进行下一步操作，有可能使算法以较快的速度收敛到局部最优解，却无法得到全局最优解，这种现象称之为早熟。因此为避免该不良现象的产生，遗传算法选择操作依据以下原则:适应值越高，被选择的机会越高，而适应值越低，被选择的机会也就越低。交叉，是对被选择的新个体进行配对交叉的操作过程。一般遗传算法都会设置一个交叉概率。通过交叉操作，每两个“父代”个体会产生两个新个体，而不进行交叉操作的个体则保持原样。进行交叉操作的两个个体染色体在随机产生的交叉点进行基因的相互交换，产生的两个新个体的染色体，第一个个体交叉点之前的基因是遗第一父个体的，交叉点之后遗传另一父个体，另一个个体的染色体构成则恰好相反。变异，是通过基因突变产生新的“子”个体的操作过程。遗传算法需预设一个固定的变异概率。新个体的染色体根据预设的变异概率进行随机的变异，一般就是改变染色体一个位点对应的一个基因，将其从1变到0，或者从0变到1。最后，经过以上一系列的选择、交叉和变异之后，产生不同于初始种群的新一代个体，并不断地循环此过程和操作，进而一代一代地向提高群体适应度的方向进展，优良的个体总是有更大机会被选择去进一步产生新一代，而适应值较低的个体则慢慢地会被淘汰掉。这一过程不断被重复，直到满足终止条件。一般遗传算法的终止条件有以下几种：预设定进化次数上限；计算的资源耗费限制;己获得最优值达到某标准;适应值已经饱和；人为干预和组合法等多种方式。4.2 针对模型设计改进遗传算法4.2.1 染色体编码方式鉴于遗传算法易于搜索到全局最优解、求解时间短、可适用范围广、全局优化性能和稳健性高等特点，本文设计了改进遗传算法(IGA)对模型求解，具体如下。本文采用实数编码，染色体的长度为（任务数+场桥数-1），基因位为0表示不同场桥间的间隔符号，染色体的基本结构示及意如图4.2所示，为10个集装箱由两场桥装卸的一个方案的染色体表示。各个基因位值表示任务编号，染色体从左往右顺序是场桥装卸顺序。图4.2 染色体编码展示4.2.2 初始种群的生成本文采用随机生成初始种群，在生成初始种群时首先要满足约束（4）、（5）、（6），以保证生成的染色体无重复的基因值。其次要保证所有染色体中的“0”不能处于基因链的首位和末位（保证两场桥均要作业）。对于后者本文将采用基因修复方法来自动修复“错误个体”(“0”处于基因链的首位和末位的个体)，具体的修复手段下文详细介绍。4.2.3 适值函数与选择机制在算法中个体的适值函数用个体的目标值函数转化而成，而且为了满足约束（7）当个体对应方案出现跨越或干扰时该类个体的适值将被明显区分，如下式：Fitness(Xi)=在算法中计算f(Xi)时引入一惩罚规则来满足约束（9），当对应的方案有集卡超过等待上限，给该个体的目标值加上一个M（一较大的正数）值作为惩罚。对于个体的选择，本文采用轮盘赌选择机制（允许相同个体）。4.2.4 交叉操作针对染色体编码特点，本文采用顺序交叉，如图4.4所示，具体步骤如下：Step 1：随机选择两个交叉点X,Y确定两父体中将被复制到子代的基因片段，并初步得到两个不完整的子代a、b。Step 2：对两个父个体从第二个交叉点Y后开始列出原基因码顺序，得到两个父个体的基因码排列。Step 3:从父体1、父体2的基因码排列中分别删掉父体2、父体1已复制到子代的基因码，分别得到排列a、b。Step 4：对a，从第二个交叉点开始按顺序将排列b的基因码从左往右填入对应的基因位并替换“”。对b做同样操作，完成后得到两个完整的子个体。在随机交叉过程中也可能会出现一些错误个体，比如任两个可行父个体顺序交叉后可能出现有“0”基因位于整个染色体的首位或尾位。因此，在算法的每一代完成所有交叉操作后，立刻调用基因修复程序把生成的新种群中错误个体修复为可行个体。4.2.5 变异操作与终止规则传统遗传算法的变异操作只有一次，而且各个基因位的值均可以在一个给定的取值范围内变异，但本文设计的染色体中除了分隔符“0”外各基因位的值不能重复。故设计了一个改进的变异算子，具体如下：初次变异，为了实现场桥间任务分配的改变，采用“倒位变异”，即在“0”两侧分别选两个基因倒换位置。紧接着二次变异，采用“换序变异”改变某场桥装卸任务的顺序，即在“0”同一侧选两个基因换位。如图4.3所示。 图4.3 连续两次变异操作当算法的迭代次数达到预先设置的进化代数时，算法终止。4.