毕业论文-动态需求下跨集装箱码头集卡调度问题研究.doc

上海海事大学本科生毕业设计（论文） - 1 - 学号: 200710222035 上海海事大学 SHANGHAI MARITIME UNIVERSITY 本本科科生生毕毕业业设设计计（论论文文 ） UNDERGRADUATE GURADUATION DESIGN (DISSERTATION) 动态需求下跨集装箱码头集卡调度问题研究动态需求下跨集装箱码头集卡调度问题研究 学 院: 物流工程学院 专 业: 物流工程 班 级: 工物 071 班 姓 名: 指导老师： 完成日期: 2011 年 6 月 上海海事大学本科生毕业设计（论文） - 2 - 摘摘 要要 随着国际集装箱运输业的迅猛发展，现代港口集装箱码头向大型化、信息化、自动化和 智能化方向发展。同时，港口所面临的经营与竞争压力越来越大，降低码头的装卸成本，提 高集装箱的装卸效率，是各个港口码头关注的重要领域。特别是当装卸工艺基本确定后，先 进装卸设备的配置不均衡性是港口集成化运营面临的主要难题。 针对现有集装箱跨码头集卡调度研究不足和港口跨码头作业现状，本文提出了基于集约 化管理的跨码头集卡动态调度问题。考虑跨码头集卡实际调度过程中的各种影响因素，采用 多目标规划的方法提出了跨码头集卡调度问题的模型。以需求量、调运成本、有效工时以及 司机经验等级等作为决策模型的主要考虑方面，在 Aimms 平台上编写合理的算法，并实现 跨码头集卡调度的决策系统。通过决策结果分析及模型求解效率分析，证明其鲁棒性良好。 说明本研究建立的决策模型在求解跨码头集卡调度问题时具有有效性与实用性。 关键词：关键词：跨集装箱码头，集卡调度，多目标规划，决策模型 Abstract With the rapid development of the international container transportation business, modern container terminals has developed into a large-scale, information technology, automation and intelligent direction. Meanwhile, because of the increasing competition pressure, how to lower handling costs and improve the handling efficiency in the terminals should be attached great importance. The imbalanced allocation of the advanced handling equipment is the main problem in the port integrated operation especially when the handling technology is determined. As for the inadequate study for the truck scheduling problem of the existing cross-container terminal and the cross-operating status of ports, this paper will propose a cross-terminal truck dynamic scheduling problem based on the Intensive management. Considering various influencing factors of the actual cross-terminal truck scheduling process, this paper will build a cross-terminal truck scheduling model by the multi-objective programming approach. Make demand, transporting costs, the effective working hours and the driver experience level, etc., as major considerations in terms of decision-making model, to write rational algorithm in Aimms platform, and to achieve cross-terminal truck scheduling decision-making system. Through the analysis of the results by decision and the efficiency of model solution, it can demonstrate its good robustness. It is illustrated 上海海事大学本科生毕业设计（论文） - 3 - that decision model established in this study is effective and practical in solving cross-terminal truck scheduling problems. Key words: Cross-container terminal, Truck scheduling, Multi-objective integer programming, Decision-making model 上海海事大学本科生毕业设计（论文） - 4 - 目目 录录 第一章 绪论 .- 2 - 1.1 选题背景 .- 2 - 1.2 跨码头集卡调度问题研究意义 .- 2 - 1.3 国内外集装箱码头集卡调度问题的研究现状 .- 2 - 1.4 本文主要工作 .- 2 - 第二章 跨码头集卡调度问题描述与分析 .- 2 - 2.1 引言 .- 2 - 2.2 跨码头集卡调度问题描述 .- 2 - 第三章 集卡跨码头调度模型构建 .- 2 - 3.1 符号定义 .- 2 - 3.2 模型约束条件构建 .- 2 - 3.3 模型的目标函数构建 .- 2 - 3.4 模型归纳 .- 2 - 第四章 模型求解及算例分析 .- 2 - 4.1 模型求解 .- 2 - 4.2 算例分析 .- 2 - 4.3 求解效率分析 .- 2 - 第五章 总结与展望 .- 2 - 5.1 本文结论 .- 2 - 5.2 研究展望 .- 2 - 参考文献 .- 2 - 致 谢 .- 2 - 附 录 .- 2 - 上海海事大学本科生毕业设计（论文） - 1 - 第一章第一章 绪论绪论 1.11.1 选题背景选题背景 随着全球经济一体化趋势的发展，世界经济及产业结构发生了重大变化，许多生产经营 活动和资源配置并不局限于某个国家或地区，而是在更广阔的在全球范围内开展。在这种经 济一体化格局的推动下，以国际集装箱运输为代表的现代运输方式也随之得到了良好的发展 契机，新一轮的国际航运中心和区域性集装箱枢纽港的竞争日趋激烈1。 现代集装箱运输自上个世纪 50 年代诞生以来，以其标准化、容量大、操作便捷、船舶 周转快、货损货差少、包装费用省、适合多式联运等优势，承担了国际海上货物运输的重要 职责2。在过去十年中，世界集装箱贸易量稳定保持 10%的年均涨幅均3。2006 年，英国航 运分析机构 MDS 曾做出预测，到 2011 年世界海运集装箱量有望实现 42%的涨幅，集装箱 货运量的绝对增长值将大幅攀升。虽然 2008 年末全球金融危机爆发，给世界航运业的发展 带来了重创，航运市场一度低迷，但自 2010 年 6 月份以来，全球经济出现回暖态势，各国 的航运业重新繁忙了起来。专家学者普遍认为，经济的放缓只是暂时的，集装箱海运业务的 优势使其在现在甚至于未来的国际运输业务中都将承担不可替代的角色。 在世界经济稳定发展的大环境下，随着我国改革开放的深入和社会主义市场经济的不断 完善，我国国民经济和对外贸易量一直呈现良好的增长势头。自 20 世纪 80 年代以来，中国 集装箱运输的增长速度始终以超过世界平均增幅(6%-8%)的决速增长率持续发展4。到 2005 年，我国的集装箱吞吐量取得突破性进展，超越美国位居世界首位，自此，我国成为全球海 上运输的重要枢纽。同年，我国有 10 个港口跻身世界亿吨大港行列，其中香港、上海、深 圳的集装箱吞吐量分别居世界第一、第三、第四位5。我国的集装箱运输发展在世界平台上 占有举足轻重的地位。 在激烈的区域性航运竞争中，我国的现代集装箱港口建设也随之加大了步伐，取得了很 大的成绩。但是集装箱船舶大型化发展趋势及集装箱运输量的增长，使不少集装箱港口仍处 于满负荷甚至超负荷运营的状态。要想解决这个问题，一方面必须加快加大集装箱码头的建 设。但集装箱码头的建设投资大周期长，因此另一方面必须努力提高集装箱港口的运作效率 以扩大其生产能力6。 集装箱码头的作业资源可分为岸边资源、场内资源以及连接两者的水平运输机械三类， 其中岸边资源是指泊位资源和岸桥，场内资源指堆场机械和堆场空间资源，而水平运输机械 主要包括跨运车、自动导向车和集卡。集装箱码头服务水平的提高主要以缩短船舶在港时间 上海海事大学本科生毕业设计（论文） - 2 - 为目标，同时码头还需要考虑各资源的利用率及成本，因此优化各种资源的利用对码头竞争 力的提高十分重要。 1.21.2 跨码头集卡调度问题研究意义跨码头集卡调度问题研究意义 随着集装箱船舶大型化以及集装箱运输的蓬勃发展，港口所面临的经营与竞争压力越来 越大，降低码头的装卸成本，提高货物的装卸效率，是各个港口码头所要解决的首要问题。 同时，港口管理者也逐渐认识到在装卸工艺基本确定后，装卸设备的合理配置对提高装卸效 率、降低运行成本起到非常重要的作用。港口企业是以装卸作业为主，装卸成本是企业的主 要生产成本。而在装卸成本中机械设备所占的比重将近装卸总成本的一半。然而国内出现港 口装卸机械拥有量大、利用率低的现象，这又无形的降低了企业的经济效益。因此，研究集 装箱港口跨码头装卸设备的合理分配，在保证完成各码头吞吐任务的前提下，尽可能地降低 装卸设备的利用不均衡性，对于充分发挥已有集装箱港口的生产潜力，提高设备的利用率， 降低装卸成本，提高港口企业的经济效益，适应市场竞争的要求，具有重要的理论价值7。 集装箱卡车（简称集卡）运输是集装箱码头作业系统中的重要环节，衔接前沿岸桥和后 方龙门吊的工作。目前国内很多港务集团下港口都设有多个码头，各自采用内集卡作为水平 运输资源。港口大部分集卡调度系统普遍采用某码头单管一定数量的集卡的传统调度规则。 传统集卡分配模式是根据本码头的实际操作业务量，对每个码头配备 5060 辆集卡, 配备 的集卡就始终为该码头服务直至泊位工作终止。而集装箱码头的装卸任务量在不同时段往往 有较大的差别，集卡的空闲程度也不同，此种调度规则下集卡在作业量较少时会产生空置的 情况。这种模式便于管理集卡但不利于进一步提高集装箱码头机械设备的利用率，难以适应 多泊位现代化集装箱码头生产管理的发展需求。因此采用集约化方式对集卡进行统一的跨码 头调度是目前研究的热点。 集卡是集装箱码头中灵活、数量大、工况复杂的机械设备，它的运作效率直接影响了整 个集装箱港口的运作效率，要想完成堆场机械的高效运行必须合理解决堆场集卡调度问题。 因此，本研究通过建立跨码头集卡的调度模型和开发求解算法来提高码头集卡的运作效率， 进而扩大集装箱港口的生产能力。这项研究具有极其重要的价值和现实意义。 1.31.3 国内外集装箱码头集卡调度问题的研究现状国内外集装箱码头集卡调度问题的研究现状 集装箱港口是集装箱运输中极其重要的枢纽。集装箱港口的运作效率直接决定了集装箱 运输的成本。为了提高集装箱港口的管理和运作水平，国内外许多学者都在集装箱港口运作 上海海事大学本科生毕业设计（论文） - 3 - 优化方面做了大量的工作。集卡调度是集装箱码头智能化调度的核心问题之一，集卡运输作 为港口内唯一交通运输方式，其运作效率将直接影响堆场作业的效率，进而影响到港口整体 作业的运作效率。因此，对于港内集卡运输方面的研究成为了近期研究的热点之一。国内外 许多学者为解决此类问题做了很多尝试，也取得了许多可喜的研究成果。但是这些研究大多 以当地集装箱港口的实际情况为依托，而国内外港口的实际情况却存在较大的差别，由各自 实际情况建立的模型、设计的算法和得出的结论都有所区别。 1.3.1 国外研究现状 集装箱码头的水平运输设备除了集卡之外还有跨运车与自动化码头所采用的 AGV(自动 导向车)，考虑到 AGV 的高昂的前期投资，一般只用于国外劳动力费用高的港口。国际上关 于港口水平运输机械的研究多集中于自动化或半自动化港口中使用的 AGV（自动导向车） 。 Gobal 和 Kasilingam (1992)9给出了一个基于 AGVs 空闲时间和集装箱码头其他装卸设 备等待时间的 AGVs 数量估算仿真模型，求解在满足操作水平条件下的最小 AGVs 需求数量。 Chen et al.(1997)10研究了自动化集装箱港口中的 AGVs 调度问题。文章采用贪婪算法求 出了 AGVs 调度的最优解同时给出了求解多台岸桥情况下的一种启发式算法。 Kim k.H 和 Bae J.W(1999)11根据多船、多岸桥同时作业的情况建立了多目标规划模型。 该文献进一步研究了装卸同时作业的情况，建立了整数规划模型(MVSL)，并证明了 MVSL 是 Np-hard 问题，设计了一种启发式算法对模型进行求解，使得即使问题规模很大也能有办 法解决。 Chin-I Liu，Hossein Jula，Katarina Vukadinovic，Petros Ioannou(2004)12介绍 AGV 在 不同结构集装箱堆场运输，应用多属性决策方法评价码头实施情况，计算每个码头使用 AGV 的最优数。 Hans-Otto Gunther，Martin Grunow，Matthias Lehmann13主要研究自动化集装箱码头 AGV 小车的两种调度策略：on-line 调度与 Off-line 调度算法，研究港口装卸操作并加以仿 真。 Bose 等(2000)14研究多船同时操作，用遗传算法使岸桥的总耽搁时间最短讨论集卡调 度优化问题。 Krishnamurt 等15对同时确定所有拖车路径的问题进行了研究。在这个问题的研究中， 一个大问题被分解为若干个子问题进行研究。在得到子问题的解决方案后，再进行有机的组 合形成一个总的解决方案。 上海海事大学本科生毕业设计（论文） - 4 - Maxwell 和 Muckstadt16构建了一种数学模型来解决拖车的规模确定问题，在这个模型 中，把任务序列时窗化，把岸桥、堆场等固定设施抽象为节点，节点的流量即为任务输入集 装箱与任务输出集装箱的差值。拖车空载行驶路径的长短直接影响到作业总时间，模型的目 标是使拖车空载的行驶路径最短。 Mantel and Landeweerd17提供了一种两层排队网络模型来确定自动化码头执行任务时需 要的 AGV 数量。在第一层，所有 AGV 被看成等价的服务台，运输任务作为顾客；第二层 AGV 被视为顾客，而整个堆场被视为服务时间一定的服务台。通过在不同 AGV 数量下计算 模型的等待时间，可以确定合理的 AGV 数。 1.3.2 国内研究现状 我国的港口多属于非自动化港口，出于劳动力费用和操控灵活性等方面的考虑，国内港 口多采用人力控制的拖车作为水平运输工具。因此国内的研究则偏向于集卡作为水平运输机 械的港口。 王超，陈磊等18针对集卡调度问题，充分考虑了现在科技发展全面应用 GPS 定位系统 的前提，给出了一个智能化集卡实时调度方案。 计明军,靳志宏19对同时装卸集装箱作业的情况进行研究，考虑了集装箱卡车的运输时 间和岸桥的作业时间，建立基于时间最少的优化模型。利用进化计算的特点，设计求解此优 化模型的进化算法，进行了数值仿真试验，在合理时间内获得了最优数值结果。此模型和方 法为码头集卡线路优化问题提供了决策支持。 尚晶，陶德馨20提出了在数字化技术环境下的集装箱码头集卡实时调度规则，并建立了 这两种调度模式的动态仿真模型。经过仿真实验分析，比较这两种度模式对码头生产能力的 影响，结果表明提出的调度策略是合理可行的，具有较强的可操作性。 李浩渊，汪定伟21分析了动态集卡配置对集装箱码头装卸作业的影响，构建了一个集装 箱码头整体作业系统的仿真模型。运用仿真模型与优化算法相结合的基于仿真的优化方法 (SBO)对集装箱码头动态集卡配置问题进行了求解，并将基于 MPI 消息传递标准的并行集群 计算方法引入该求解过程，很好的解决了基于仿真的优化方法中存在的计算代价过大的问题。 计明军，刘丰硕等22在待装集装箱船舶与待卸集装箱船舶同时作业情况下，研究集卡的 运输路径，建立集卡行驶路径最短的优化模型，并对优化模型进行数值试验，在合理时间内 获得了最优结果。在此基础上以岸桥等待时间最短估算作业需要配备的最佳集卡数量。 严政，陶德馨23从探索集装箱堆场机械设备调度的规则入手，提出了基于动态优化组合 上海海事大学本科生毕业设计（论文） - 5 - 的港区内集装箱集卡(简称集卡)的调度规则。应用作业调度信息系统和无线局域网络实现集 卡作业状态的实时监控和动态优化的调度功能，并用离散事件动态仿真的方法进行了模拟， 验证了该方法的有效性。 陈方鼎8研究了采用“大作业面”工艺时集装箱码头集卡的调度问题。根据实际情况将 集卡调度同岸桥作业相结合，建立了协调岸桥的集卡调度模型。采用了现代优化算法中的群 体智能算法，并结合蚁群算法与粒子群算法，形成混合群体智能算法进行求解。通过一个模 拟现实集装箱码头同时服务多艘船舶的案例，得到优于“作业线”装卸工艺的结果，这些结 果表明所提出的模型与算法对解决集装箱码头集卡调度问题具有一定的现实意义。 近年来，计算机建模和仿真技术越来越多地应用于集装箱码头的规划和管理中。计算机 仿真作为一种测试与验证平台，仅能对给定的设计结果进行评价，无法提供进一步的辅助决 策功能。 1.3.3 当前研究存在的问题 （1）国外文献的研究对象主要为 AGV。目前大多数文献对港内拖车调度问题的研究都 集中在自动导引车(AGV)上，AGV 的行驶路线相对固定，能够及时反馈位置信息以及能准 确执行调度指令，这使得一些调度策略能完整执行。而目前国内港口基本没有使用 AGV， 主要采用人工集卡，在这种情况下，由于人工因素的制约，一些调度策略就不能被很好执行。 （2）建立的模型与实际仍有差距。在现有的研究文献中，对于港口运输问题，为了简 化问题或多或少做了一些假设，诸如岸桥等待时间为零、岸桥装卸操作时间为常数、集卡在 泊位到堆场之间的行驶时间是固定的、忽略交通网络堵塞因素等等。但是，在实际中，这些 因素对问题结果的影响并不小，所以普遍存在的问题使得现有的研究结果很难投入到实际应 用中去。 （3）缺乏对全场调度的研究。目前对拖车运输研究所建立的模型，大多是针对一个岸 桥作业的情形。虽然有国外少数文献考虑了多岸桥组合模型的求解，但考虑的因素做了很大 的简化假设，同时由于国外港口与我国港口的特征差别，所建立的模型和提出的算法结果在 我国港口的实际应用效果较差。全场调度问题由于其规模大，很难找到一个高效的算法得到 问题的最优解7。 1.41.4 本文主要工作本文主要工作 上海海事大学本科生毕业设计（论文） - 6 - 考虑到集卡在码头作业中的要求的复杂性，以及集卡所具有的灵活、数量大等特点，集 卡调度问题就成为集装箱码头资源调度的一个复杂的关键性的问题。集卡调度对于码头的来 说既有短期现实意义又有长远的意义，短期的意义是指集卡在满足码头作业要求的时候能够 以较短的路径完成任务，节省油耗从而降低码头成本，长远的意义是指能够减少集卡的规模 但又同时保证了岸桥的需要。 针对现有集装箱跨码头集卡调度研究不足和港口跨码头作业现状，本文对集卡调度过程 进行深入分析和问题描述，采用多目标规划的方法提出了跨码头集卡调度问题的模型和求解 算法，解决复杂的调度问题，并证明模型及算法的有效性。 主要研究内容如下： 1. 对集装箱码头作业的流程进行深入的理解，进一步分析集卡调度问题在码头作业中 的重要意义及其发展趋势。 2. 分析研究跨码头集卡调度的具体过程，通过比较传统集卡调度模式，对跨码头集卡 调度的问题进行描述及深入分析。 3. 从港口整体系统的观点出发，考虑跨码头集卡实际调度过程中的各种影响因素，提 出实用的跨码头集卡调度多目标整数规划模型，分析与总结跨码头集卡调度的基本原则，并 将其转化为模型的约束条件及目标函数。 4. 对跨码头集卡调度的过程进行总结，理解集卡调度决策模型，并编写合理的算法， 在 Aimms 平台上开发并实现跨码头集卡调度的决策系统。 5. 针对系统基本原则，对算例的决策结果进行分析，并进行模型求解效率分析，证明 其鲁棒性良好。说明本研究建立的决策模型在求解跨码头集卡调度问题时是有效的。 上海海事大学本科生毕业设计（论文） - 7 - 第二章第二章 跨码头集卡调度问题描述与分析跨码头集卡调度问题描述与分析 2.12.1 引言引言 根据集装箱码头的装卸工艺，码头的作业资源一般可分为三类:岸边资源、水平运输资 源和堆场资源8。 岸边资源，包括泊位和岸边机械，由于目前集装箱码头岸边机械一般为岸壁式集装箱装 卸桥(Ship-to-shore crane)，所以岸边资源通常指泊位与岸桥。在集装箱吞吐量不大、到港船 舶不密集时，一般只需按照船舶的到港顺序为其配置合理泊位，而随着集装箱吞吐量的增加、 到港船舶航次增多，为了达到既快速完成装卸，又充分利用泊位资源的目的，泊位资源的配 置就显得相当重要。岸桥在装卸工艺中属“龙头”装卸设备，它是负责按照装卸船顺序将集 装箱从船上卸到岸边（进口）或者把集装箱从岸边装到船上（出口） ，岸桥的型号及主要技 术参数，很大程度上限制了码头泊位能够接纳的最大集装箱船型，而且同泊位资源一样，岸 桥资源也属于稀缺资源，成本非常高，因此岸桥的配置也成为码头装卸能力的决定因素。岸 桥是分布在泊位的岸线上的，所以在进行泊位配置时通常会涉及到岸桥配置问题。 水平运输资源是指运行于岸边机械和堆场机械之间，转移任务的运输机械。在自动化码 头指的是自动导向车承担着实现集装箱位置(AGV)，箱码头一般指的是集装箱卡车，而跨运 车也能承担水平运输任务。非自动化集装水平运输资源配置不合理将导致岸桥等待，空车行 驶距离增大，资源投资过多等不利于码头生产效率和服务水平的效果，因此如何更合理的配 置水平运输资源也是集装箱码头资源调度的一个重要问题。 堆场资源包括堆场空间资源与堆场机械资源。堆场空间资源的配置涉及到如何根据堆场 分类的标准和堆垛规则合理地为进出口集装箱安排堆存箱位。合理的箱位安排不仅能减少堆 场机械的翻箱率，减少集卡和岸桥等待时间，提高码头作业效率，而且还能提高码头堆场利 用率，降低生产成本。堆场机械资源是指在堆场用于集装箱装卸、搬运和堆码的专用机械。 常用的堆场机械有轮胎式龙门起重机(RTG)和轨道式龙门起重机(RMG)，可统称为场桥。场 桥负责在不同箱区或者同一箱区不同倍位之间移动，将集装箱由水平运输机械上吊起堆放到 某个箱位或者从某一箱位提取一个集装箱卸到水平运输机械上。 上海海事大学本科生毕业设计（论文） - 8 - 岸岸边边 资资源源 堆堆场场 资资源源 水水平平运运 输输资资源源 集集装装箱箱船船 图 2.1 集装箱码头资源示意图 集装箱码头装卸工艺流程中，岸边资源负责船舶的停靠和集装箱的在船舶上的装卸，水 平运输资源把从岸桥上卸下的集装箱运往堆场，或者由堆场运送集装箱到岸边交予岸桥装船， 堆场资源则分配给每个集装箱一个箱位并将集卡运来的集装箱装卸到指定箱位，或者从堆场 提取集装箱到水平运输机械上。可见，码头装卸作业过程中，三种资源必须相互配合相互协 调来完成集装箱的装卸任务，所以，集装箱码头作业资源的调度问题往往涉及到多种资源的 相互协调问题。 由于国内劳动力成本相对较低，集装箱码头基本上都是非自动化的，即码头水平运输方 式采用集卡运输，码头专用集装箱卡车具有灵活、数量大、工况复杂等特点，因此要想完成 堆场设备的合理运行，必须首先解决集卡作业资源的调度问题。 2.22.2 跨码头集卡调度问题描述跨码头集卡调度问题描述 如果装卸设备配备数量太多，必然会增大港口的投资。因利用率低，空闲时间过长所带 来的浪费也会降低港口的经济效益。反之，装卸设备配置不足，将导致船舶在港停泊时间过 长，排队现象严重，损害船运公司及货主的利益，由此也会影响港口的信誉，削弱其在港口 运输市场中的竞争力。所以，码头装卸设备的配置应兼顾港口与船运公司的双方利益，使其 达到“既满足需要，又不造成浪费”的最佳投资水平7。 在对港口装卸设备配置的研究中所采用的成本分析方法、技术经济分析方法或数学规划 方法，大部分是静态的。由于港口装卸设备配置决策涉及港口各个码头的设备资源状况和效 率，而这些资源和效率都是动态的，所以静态模型难以反映真实情况7。 目前，对于码头集卡资源的配置基本上用的还是传统的模式：一个码头配置固定数量的 集卡，配备的集卡就始终为该码头服务直至泊位工作终止。这样就没有从港口整体最优考虑， 上海海事大学本科生毕业设计（论文） - 9 - 往往导致不能充分的挖掘港口的生产能力。 因此，采用集约化方式对集卡进行统一的跨码头调度有利于进一步提高集装箱码头机械 设备的利用率，同时也符合多泊位现代化集装箱码头生产管理的发展需求。 码头A 码头B 码头C 码头D 总调度中心 图 2.2 集约管理港口集卡 跨码头集卡动态调度是根据某时刻码头申请的集卡需求动态地调度集卡。设立一个集卡 总调度中心集约化管理港口所有的集卡, 使各个码头共享所有的集卡，如图 2 所示。各码头 可根据当日码头作业计划向总调度中心提前预定一定数量的集卡，当某码头集卡无法满足码 头作业要求时可提出申请额外的集卡，而当码头有空闲集卡即可申请退订。总调度中心可根 据申请合理地就近从其他码头调度空置的集卡，各码头其余空置集卡则调回总调度中心。灵 活地满足各码头对集卡的不同需求，从而在保证码头作业效率的基础上大幅度减少集卡数量 并提高资源的利用率。 上海海事大学本科生毕业设计（论文） - 10 - 申请退订 申请需求 申请退订 申请需求 申请退订 提 前 预 订 提 前 预 订 提前 预订 提 前 预 订 图 2.3 业务概述 跨码头集卡调度的主要决策内容是：对于任一正常作业状态的集卡，是否将其调运至其 他码头或总调度中心，从而满足租用方（码头）的申请及退订要求。 集卡资源的分配必须遵循一定的规则，主要有以下几点： （1）按需分配原则。 需求量是各码头根据其实际作业情况向总调度中心申请的集卡数量。当码头业务较繁忙 而集卡无法满足码头作业需求时，需要向总调度中心额外申请的需要集卡。为充分利用集卡 资源，总调度中心分配给该码头的集卡数量应不大于该码头的申请量，并尽量满足码头的申 请需求。 （2）调回原则。 调回原则指的是对于某码头申请退订的集卡，必须调离该码头，即就近调度至需要的码 头，或者调度回总调度中心。 （3）就近调度原则。 集卡跨码头调度需考虑码头与码头之间的调运成本，该成本和码头之间的距离有关。例 如码头 A 申请退订集卡而码头 C 申请需求额外的集卡的情况。若将集卡从码头 A 直接调运 至码头 C 的距离要大于集卡从码头 A 先调运至总调度中心再从总调度中心调运至码头 C 的 距离，此时则选择后一种调运方案。 上海海事大学本科生毕业设计（论文） - 11 - 码 头 A 码 头 C 总 调 度 中 心 图 2.4 就近调度原则 （4）工时平均原则 集卡的有效工时指的是集卡调入总调度中心的时间减去上一次调出总调度中心的时间的 差。为尽量均衡各集卡之间的作业强度，优先调度有效工时少的集卡至其他码头作业。若将 码头退订的空置集卡调回总调度中心，优先调度有效工时相对较多的集卡回总调度中心。如 图 2.5 所示，若从码头 A 调回 1 辆集卡回总调度中心，应优先调回有效工时为 7 的集卡 T08，而非有效工时为 4 的集卡 T05；而若从总调度中心调出 1 辆集卡至码头 B，则应优先 调出有效工时为 4 的集卡 T26，而非有效工时为 7 的集卡 T22。 退 订 4工工时时 总调度中心 码头A 7工工时时 7工工时时 4工工时时 调 出 码头B T05 T26 T22 T08 图 2.5 工时平均原则 （5）等级需求。 对于难度较高的装卸作业任务，某些码头可以对集卡司机的经验等级提出要求。例如在 上海海事大学本科生毕业设计（论文） - 12 - 处理危险品货物的情况下，可申请经验较为丰富的司机操作作业。 为满足以上业务需求，进行有效的集卡调度，达到为各码头合理分配集的目的，建立跨 码头集卡调度的决策模型见第三章。 上海海事大学本科生毕业设计（论文） - 13 - 第三章第三章 集卡跨码头调度模型构建集卡跨码头调度模型构建 3.13.1 符号定义符号定义 （1）维度（实体）的表示符号 t，表示第 t 辆待调度的集卡。 i/j，表示第 i/j 个码头，模型中将总调度中心设置为一个虚拟码头。 l，表示集卡对应的司机经验等级，从高到低依次可分为甲、乙、丙、丁四个等级。 （2）已知参数的表示符号 ，binary，用于描述第 t 辆集卡是否处于第 j 个码头。1 表示第 t 辆集卡当前时刻处于 tj W 第 j 个码头，0 则相反。 ，用于描述第 j 个码头的集卡需求量。由各码头根据当前作业情况提出申请。 j N ，用于描述码头 j 的特殊等级需求。表示码头 j 对司机等级为 l 的集卡的需求量。它 jl M 与装卸货物的特征有关。 ，binary，表示码头 j 是否有特殊等级需求。1 表示码头 j 有水平等级 l 的需求，0 jl CM 则相反。 ，用于描述码头 i 申请的司机水平等级为 l 的集卡退订数量。 il S ，用于描述集卡从第 i 个码头调度到第 j 个码头的调运成本。它和码头 i 的码头 j 之 ij D 间的距离有关。 ，binary，表示第 t 辆集卡对应的司机经验等级。1 表示集卡 t 对应的司机经验等级 tl E 为等级 l，0 则相反。 ，用于描述集卡 t 的有效工时。 t H ，binary，1 表示码头 i 是总调度中心，0 则相反。_ i IfCenter ，表示码头 j 分配集卡资源的优先系数。描述码头对于需要集卡调度的重要程度。 j a （3）决策变量的表示符号 ，模型的决策变量，binary，用于计算是否将集卡 t 调运至码头 j。 tj X 3.23.2 模型约束条件构建模型约束条件构建 模型的约束可分为绝对约束和目标约束。绝对约束是指必须严格满足的约束条件，如线 性规划中的约束条件都是绝对约束。绝对约束是硬约束，对它的满足与否，决定了解的可行 上海海事大学本科生毕业设计（论文） - 14 - 性。目标约束是目标规划特有的概念，是一种软约束，目标约束中的决策值和目标值之间的 差异用偏差变量表示。 根据跨码头集卡调度遵循的分配原则，本文模型的约束有如下几个： 3.2.1 按需分配限制 根据各码头向总调度中心提出的申请，可获得当前时刻码头集卡的空闲状态。当码头业 务较繁忙而集卡无法满足码头作业需求时，就反馈所另需的集卡数量至总调度中心，即可得 实时集卡需求量。在尽量满足各码头需求的前提下，总调度中心安排实际调度出的集卡数量 应不超过统计的需求量，以免造成资源浪费以及增加调度成本。如下图 3.1，码头 A 向总调 度中心申请需求 3 辆集卡，分配给该码头的集卡数应不超过 3 辆。 码头A 图 3.1 按需分配原则 模型中该约束方程表示如下： .（3.1） tjj t XNj 不等式的左边，为关于 t，j 的二维 01 矩阵，对 t 求和后得到调度至码头 j 的集卡数 tj X 量。不等式的右边是实时统计的码头 j 的集卡需求量。为满足资源需求限制，使得左边小于 等于右边。 3.2.2 调回约束 当码头的作业任务所需的集卡数量小于原先预定的集卡数量时，就会造成部分集卡处于 上海海事大学本科生毕业设计（论文） - 15 - 空置的状态，空置集卡的数量即可为该码头申请的集卡退订量。对于某码头申请退订的集卡， 必须调离该码头。因此，实际调出的 l 等级集卡应等于申请的退订量。 如下图 3.2，码头 A 申请退订的集卡 T07，必须调离该码头，即就近调度至码头 B，或 者调度回总调度中心。 退 订 码头A 码头B 总调度中心 T07 图 3.2 调回原则 模型中该约束方程表示如下： .（3.2）(1_)(1_) tjtiitlili jt XWIfCenterESIfCenteri 等式的左边，二维 01 矩阵、和相乘可得关于 t，j，i，l 的四维 01 矩阵，其中 tj X ti W tl E 1 表示从码头 i 调出且对应司机等级为 l 的集卡被调度至了码头 j，0 则表示该集卡 t 未被调 度至了码头 j。对 j，t 求和，可得到从码头 i 调出且对应司机等级为 l 的集卡数量。 等式的右边，变量表示码头 i 申请的司机等级为 l 的集卡退订数量。等式两边乘以 il S ，表示码头 i 为总调度中心时，该约束不起作用。令左边等于右边，对集卡(1_) i IfCenter 调回量进行约束。 3.2.3 等级需求约束。 在某些特殊情况下，各码头需要根据业务的情况申请一定数量的特定等级的集卡。例如 在处理危险品货物的情况下，需要经验等级为甲级的司机操作作业。在集卡调度时应尽量满 足码头对集卡司机经验等级的要求，同时实际调出的该等级的集卡应不超过需求量。 上海海事大学本科生毕业设计（论文） - 16 - 丙 乙 甲 甲 甲 码头C 码头D 图 3.3 等级需求原则 如上图所示，码头 C 申请需求 1 辆甲等级的集卡，分配给该码头的甲等级集卡应不超 过 1 辆；码头 D 申请需求 1 辆乙等级的集卡，若将 1 辆丙等级的集卡分配给该码头，则就 不符合需求。 模型中该约束方程表示如下： .（3.3） tjtljl t XEMj 不等式的左边，二维 01 矩阵和二维 01 矩阵相乘可得到关于 t，j，l 的三维 01 矩 tj X tl E 阵，其中 1 表示对应司机等级为 l 的集卡 t 被调度至了码头 j，0 则表示该集卡 t 未被调度至 了码头 j。对 t 求和，可得到调度至码头 j 且对应司机等级为 l 的集卡数量。 不等式的右边，变量表示码头 j 对司机等级为 l 的集卡的需求数量。令左边右边， jl M 对调度至各码头且为各特定等级的集卡数进行约束。 3.2.4 唯一性约束 该约束保证一辆空置集卡只能分配给一个码头。集卡 t 指派给码头 i 后，就不能再将其