（工商管理专业论文）上海浦东集装箱码头智能化生产控制研究.pdf

论文独创性声明 本论文是我个人在导师指导下进行的研究工作及取得的研究成果。论文中除 了特别加以标注和致谢的地方外，不包含其他人或其它机构已经发表或撰写过的 研究成果。其他同志对本研究的启发和所做的贡献均已在论文中作了明确的声明 并表示了谢意。 怍者魏讧日期叱 论文使用授权声明 本人完全了解复旦大学有关保留、使用学位论文的规定，即：学校有权保留 送交论文的复印件，允许论文被查阅和借阅：学校可以公布论文的全部或部分内 容，可以采用影印、缩印或其它复制手段保存论文。保密的论文在解密后遵守此 规定。 作者签名二函师签名：簧彤嗽华 姓名；王超学号：0 5 z o z 5 3 0 3上海浦东集装箱码头智能化生产控制研究 摘要 随着中国进出口贸易以及长江经济区的进一步发展，港口能力的提升越发显 得重要，但由于资源的稀缺性，粗放型发展道路已经无法走下去，走集约化发展 道路，通过管理创新、技术创新以及机制创新来提高码头的生产能力及服务水平 是必然选择。上海港作为世界发展的重要港口、作为中国的龙头港口，“做大做 强”也是其发展的必由之路。 本文就是根据这一指导原则，结合上海港务集团的子公司，上海浦东集装箱 码头有限公司的智能化、信息化探索经验，提出的集装箱码头生产智能化控制的 研究方案。 本文第一章先介绍港口的基本情况码头的作业流程及基本概念；然后介绍上 海港和上海浦东集装箱码头有限公司的优缺点；接着简要介绍一下集装箱信息管 理系统；最后简要的分析本文所要解决的问题及解决方法。 本文以码头的作业流程为顺序，依次分为堆场计划、装船计划和装船作业。 由于码头管理系统非常庞大，故本文就几个主要的问题进行探讨。本文第二章是 堆场计划，介绍了堆场中的翻箱问题，其解决方法用到了图论中的一些知识；此 外还将介绍p a 区域划分。第三章是装船计划，介绍了智能配载问题及其解决方 法，主要运用了线性规划的方法。第四章是装船作业，介绍了装船顺序安排问题 和集卡调度问题，前者给出了两种算法；后者建立了一个模型，并用到了图论中 经典的算法。 关键词：码头，配载，堆场，线性规划，算法，模糊逻辑推理 第l 页 姓名；王超学号：0 5 2 。2 5 3 0 3上海浦东集装箱码头智能化生产控制研究 第一章背景及解决方案分析 1 1 港口基本情况简介 回顾2 0 0 6 年，全球3 0 大集装箱港口吞吐量全线飘红，其中中国港口的表现 尤其亮眼，面对世界港口已成亚洲港口天下的格局，中国港口在未来还将大放异 彩。 据英国伦敦出版的国际集装箱化杂志报道：2 0 0 6 年世界排名前3 0 位的 集装箱港口吞吐量达到2 42 0 8 万t e u ，相当于当年世界港口集装箱吞吐总量4 4 0 0 0 万t e u 的5 5 。 上述3 0 家集装箱港口中，来自中国的港口包括香港地区的和台湾地区的港 口在内达到1 0 家。中国内地集装箱港口吞吐量2 0 0 5 年达到61 3 0 万t e u ，占当 年全球前3 0 名集装箱港口吞吐总量的2 8 2 ；2 0 0 6 年达到74 7 0 万t e u ，占当 年全球前3 0 名集装箱港口吞吐总量的3 0 9 9 6 ；而作为中国最重要港口的上海， 2 0 0 6 年达到2 1 7 1 万t e u ，约占其中的1 0 。 今年上半年，上海港继续保持良好的发展势头，集装箱和货物吞吐量持续创 历史新高，港口运作层次和经营效益稳步提升。一至五月，全港货物吞吐量 2 3 0 1 1 3 万吨，同比增长6 1 ；外贸货物1 0 3 0 2 4 万吨，同比增长2 5 6 ，其中 外贸出口5 0 7 1 7 万吨，增长3 0 7 ，外贸进口5 2 3 0 7 万吨，增长2 0 9 9 6 。集装 箱量1 0 2 9 5 万标准箱，同比增长2 5 6 。洋山深水港区集装箱量2 2 0 万标准箱， 并创造最高装卸船时量每小时6 9 0 9 3 个自然箱箱和桥吊单桃台时量9 7 个自然箱 的世界记录( 双4 0 尺吊) 。旅客吞吐量5 1 3 万人次；货运量1 5 7 8 6 万吨，增长 7 3 ；货运周转量6 0 9 0 7 亿吨公里，增长1 4 2 。 人们普遍认为，由于中国经济态势持续强劲，集装箱贸易出口量有增无减， 预计上海港集装箱吞吐量2 0 0 7 年预计将达到26 0 0 万一27 0 0 万t e u ，预计2 0 0 7 年年底将超过中国香港，2 0 0 8 年年底将超过新加坡。 第3 页 姓名：王超学号：0 5 2 0 2 5 3 0 3 上海浦东集装箱码头智能化生产控铡研究 中国港口综合竞争力指数排行榜是由中国国际海运网 ( 硼w s h i p p i n g c h i n a c 例) 和大连海事大学世界经济研究所共同调研完成，通 过对港口关键指标和具体数据分析，采取国际先进的经济学计算原理，中国港口 综合竞争力指数排行榜终于于2 0 0 6 年首次在中国问世。在该排行榜中的排名情 况如下： 十大港口总得分情况如下，上海港获得3 3 0 分，以绝对优势名列第一；深圳 港1 9 5 分列第二，青岛港1 5 0 分第三位。排名在最后三位是大连港7 9 分、连云 港5 1 分、营口港4 2 分。十大港口中的宁波港、广州港、天津港、厦门港处于中 游水平。这是十大港口的最终排名。 中国港口综合竞争力捧行耪 上海 3 3 0 深圳 1 9 5 青岛 1 5 0 宁波1 3 4 广州 1 2 5 天津 1 0 5 厦门8 8 大连7 9 连云港 5 l 营口4 2 图1 4 上海港作为中国大陆第一大港口，名副其实。在十三项指标中，上海港十一 项指标排名第一，一项排名第二，唯一劣势是上海港的区位指标。上海港一直保 持强有力的发展势头，与上海市以及长江三角洲的发展建立紧密地联系。临港工 业的互动以及国际航运中心建设的推动，都是上海港强有力的竞争优势，上海港 正在快速的向国际性港口迈进。 上海港正加快推进国际航运中心功能建设。提出了上海现代航运服务业中长 期发展战略，2 0 0 5 至2 0 1 0 年为培育期，初步形成框架，拥有各类相关产业接近 或达到香港目前水平；2 0 1 0 至2 0 2 0 年为发展期，建成产业完整、功能齐全、结 构合理的航运服务业体系，接近伦敦现代航运服务业水平，基本建成功能型国际 航运中心。上海港是国际型港口的代表。 第4 页 缴。：。，。m 姓名：王超学号：0 5 2 0 2 5 3 0 3 上海浦东集装箱码头智能他生产控制研究 码头主要作业有以下三种： i 、堆场一岸边的装卸船作业： i i 、 经闸口一堆场的集疏箱作业； i i i 、 堆场一堆场的倒箱作业： 具体细分进程及相关活动事件见下图： 褂避在 羹褂毫程 蘑进曩 蠢遥腿 翻罐进 程 一b 糖格进 程b 一 昏 爵 爵 昏 阿两司 瞥 佩 t 叁! l 整体作业流程同时发生情况见下图： 图1 2 第7 页 姓名：e 超学号：0 5 2 0 2 5 3 0 3上海浦东集装箱码头智能纯生产控制研究 图1 3 1 3 集装箱码头管理信息系统 集装箱码头管理信息系统是一个多输入多输出的非常复杂的庞大系统，涉 及到货物、堆场、机械设备、船舶等各种实体即时信息的传递、交换、处理及优 化。完全由人工操作和管理无法实现码头运行的高效性和准确性。我们在信息 技术的应用上已经完成了从业务处理和基本信息处理到管理控制阶段，在这个 阶段中存在着各个层面的管理控制，其中最基础的就是生产各环节围绕中心目 标的决策支持，这就是我们要研究的管理智能化。它的目标就是把我们在日常工 作中所积累的经验或者是我们想做但心有余而力不足的事情通过智能化系统模 型和优化模型在计算机中实现，从而达到既提高工作水平又优化目标，极大地提 高工作效率的目的。通过集装箱码头管理信息系统智能化技术的开发应用，能够 可靠、稳定地提高码头管理水平、作业效率、集装箱的通过能力、服务水平和竞 争能力，并大大提高经济效益，加快实现上海港口的现代化。 1 4 问题简要分析及解决方案提出 历史给予中国、给予上海港重大机遇，同时也给予了重大挑战。尤其目前， 在“又快又好”的经济发展道路指引下如何“做大做强”上海港是一个迫切需要 解决的问题；而上海浦东国际集装箱码头有限公司作为上海港在浦东建设的第一 个码头，解决其发展的矛盾，提高其运营的质量和水平，具有极其重要的示范意 义及i j 瞻作用。因此，我们提出这一问题也是适应大环境的需要。那么上海浦东 第8 页 姓名：王超学号：0 5 2 0 2 5 3 0 3 上海浦东集装箱码头智能化生产控制研究 国际集装箱码头有限公司的发展得利于同时也受制于上海港的整体口岸环境，因 此，我们首先来分析上海港总体环境的弊端所在。上海港的劣势除了1 1 中所 指的区位指标( 主要是因为它到目前为止，还有一半是受潮汐影响的河港) 以外， 从运营角度来分析，还有如下两个： 一是先进港后放关给码头带来的极大被动； 这给码头带来的最大不便就是造成集装箱已经进了码头但不能配船、装船， 否则万一装了上去而海关不放行，集装箱卸下来的时间及劳动成本就太大了。而 正是由于这个问题，使得在装卸进程中堆场上堆的一列集装箱中有的可以装有的 不可以装，这势必会提高翻箱量。 二是遵循服务至上，但缺乏对客户的有效控制及管理，主要表现在客户送箱、 提箱等计划性不强。 这些作业的计划性不强，导致码头无法预估下一段时问的工作量，为有效组 织生产带来负面影响。 以上两点对于码头运作，尤其是资源紧缺的码头运作带来极大不便。而上海 浦东国际集装箱码头有限公司正是属于资源紧缺的码头，而且和上海其他码头相 比也处于劣势。下表反应了外高桥地区个码头的硬件状况，其中外一期即上海浦 东国际集装箱码头有限公司是硬件条件最差的。 外一期( 浦 项目 外二期 外三期外四期外五期 集公司) 泊位数量( 个) 33244 1 2 5 0l i l o 泊位长度( m ) 9 9 0 06 6 5 ( + 1 8 7 )( + 1 9 0 ) 泊位水深( m ) 一1 2 01 3 2一1 3 2 一1 4 2 ( 一8 7 ) - 1 4 2 ( 4 5 ) 码头面宽度( m ) 4 25 05 05 4 5 + 3 05 8 + 3 0 陆域纵深( m ) 5 5 31 2 0 01 0 2 01 2 0 0 1 2 2 0 数量( 座)4 4 344 引 宽度( m ) 1 4 3 座2 0 2 座 2 0 3 座 2 0 3 座 桥1 5 1 座1 5 2 座 2 0 x 3 座 2 5 l 座2 5 1 座 总长( m ) 2 4 24 2 28 2 01 0 8 4 平面箱位( 只) 6 4 3 41 4 5 5 47 7 4 6f 6 5 2 81 9 0 8 3 陆域面积( 万m 2 ) 5 01 0 2 1 36 3 8 61 5 5 1 6 3 其中堆场( 万m 2 ) 2 l 4 92 6 5 57 6 绿化( 万m 2 ) 1 7 51 3 33 14 0 岸桥数量( 台) 】2 21 51 4 场桥数( 台) 4 28 64 8 4 8 第9 页 姓名：王超学号：0 5 2 0 2 5 3 0 3上海浦东集装箱码头智能化生产控制研究 上海浦东国际集装箱码头有限公司由于起步较早，并随着其它码头的建立。 现在已很明显在各项硬件指标上出现劣势。下面是对本码头一些劣势的定性总 结： 1 堆场狭小而且设计不合理，目前集卡是单车道； 从上面的对比图中可以看出，浦集公司的堆场面积是其它码头的二分之一甚 至三分之一，而吞吐量按泊位算基本持平。这样势必导致堆场堆放高度增加，翻 箱量提升；单车道就会导致后面的集卡必须等待前面集卡作业完成才能驶到自己 需要的位置；而由于进入车道集卡的无序性又导致轮胎吊频繁移动。其结局是既 浪费了时间又提高了成本。 2 码头前沿宽度不够，造成舱盖板等必须放在桥机下方，造成车道不足； 浦集公司( 外一) 的码头宽度比其它码头至少窄了8 米，也就是起码少了三 个车道。车道不足的后果是如果完全按照配载船图来装，就会存在先到的集卡不 一定是要装的箱子、而它绕一圈回来也不一定能够到达集卡队列中该达到的位置 的现象，造成指挥上的不便( 外一堆场本来就小，也不可能给缓冲区) ；不按照 配载船图来装就会引起船公司的不满，服务质量就会下降。 3 是某些关键设备如桥机等日渐老化，满足不了生产的需求。早期设备无 法进行双箱吊而且由于经常需要维修造成出勤率的降低。这样也影响了作业的进 度。 4 是由于码头生产任务激增，导致业务人员工作强度增大从而引起其工作 质量的下降，为整体效率的提高埋下了不利的因素； 5 是目前的信息系统在设计理念上滞后于生产形势的发展。现有的生产系 统在设计理念上是香港九十年代中后期的产物，已经无法适应上海港吞吐量剧增 而物流专业人员缺乏的局面。 为了克服上述劣势，考虑到设备的昂贵性以及资源的稀缺性，只能从挖掘自 身的潜力出发，充分利用智能化系统，从管理创新、科技创新以及机制创新上来 解决生产发展的瓶颈。 至于如何解决，我们先来继续看一下图1 1 第l o 页 姓名：王超学号：0 5 2 0 2 5 3 0 3上海浦东集装箱码头智能化生产控制研究 目口目目 斗量卡 璺章主彝辜 百豆口日 t 誊詈茎。十| i 自轮脑 丢岩蓍吾誊 口 l t 口羞 口日目日 鸯曩。 8 * 。格- 事 码头装卸效率及服务水平的提高最直接的表现是在岸边，但由于目前的桥机 作业能力远大于实际的生产效率，所以要想提高码头装卸效率及水平，充分发挥 设备能力是其主要解决思路，这就需要配载得当；而配载也要受制于堆场的堆存 状况以及场地设备的保障状况。所以堆场堆存能力是解决问题的基础。而上海浦 东国际集装箱码头有限公司最突出的问题就是堆场狭小以及布局的不合理。 因为要兼顾到装卸效率及装船准确率，有些问题我们通过与船公司协商进 行变通处理，如对于装船准确率的问题，我们同船公司协商的结果是，在一定范 围内，可以允许码头实装位置同配载位置不同，即：在保证港口相同、箱型相同、 重量在一定范围之内，在甲板上可以同层交换、甲板下同列交换。 本文所提内容，是基于以上分析及协调的结果，以作者对集装箱码头尤其是 外一期码头数年研究及实践，提出解决方案的一部分，其指导原则是：以堆场为 基础，以配载为重点，以中控为实现，以设备为保障。基于这一指导原则，本文 作者同各方力量共同努力，为外一期码头的智能化信息系统付出了很大的精力。 本文所介绍的这些方案大都已经实现，为码头的进一步发展做出了贡献。本文以 码头的作业流程为主线，分为三部分内容：堆场计划、配载计划和装船作业。由 于码头管理系统的复杂性和本文篇幅的缘故，本文只介绍几个具有代表性的问题 及其解决方案。 本文第二章是堆场计划。堆场是整个码头作业流程的基础，几乎所有从码头 进口和出口的集装箱都要在码头存放一段时间。如果存放的时候没有计划性的 话，会对后面的操作带来很大的麻烦，同时会降低整个码头的效率。堆场计划主 要包括道口进提箱、p a 区域划分和日常的翻箱操作。最小预翻箱是对已经存放 第l l 页 姓名：王超学号：0 5 2 0 2 5 3 0 3上海浦东集装箱码头智能化生产控制研究 在堆场上的集装箱进行整理，以最少的翻箱次数达到目标状态。进整理后的集装 箱能提高配载人员的配载速度和质量，提高装船的效率和质量。关于配载将会在 第三章中提到。为了更好的解决最小预翻箱问题，我们借助于图论中的一些工具 ( 本文出现的图论术语可参见 2 3 、 2 4 ) ，但由于这个系统对即时性要求很高， 故还要做一些修改，这些都会在第二章中介绍。同时，第二章还将介绍p a 区域 划分，p a 区域划分就是对从道口进来的集装箱分配几个具体的位置，本文将详 细介绍c a g 放箱策略。关于堆场计划的智能优化系统见 1 3 ， 1 8 。 本文第三章是装船计划。在某艘船的靠泊时问和需要装上该船的集装箱已定 的情况下，为该船设计一个大致的装船计划。其中最主要的问题是配载，即在需 要装船的集装箱及其在堆场上的位置已知的前提下，按照船的具体要求把堆场上 需装船的每个箱子按排一个位置，使得装船速度最快。这个问题涉及到多方面的 问题，比如船的靠泊计划和桥吊作业计划( c w p ) 等。由于涉及到一艘船的集装箱 会有成百上千，所以如果要人工来配载的话，往往会考虑的不够周全，工作人员 的工作强度也很大。在这种情况下，我们给出了一个智能配载的方案，即用电脑 来帮助配载。其中涉及到很多数学和算法问题，主要建立了一个线性规划来帮助 我们解决这个问题。参考文献 6 】和【18 】中介绍了其它智能配载系统。 本文第四章是装船作业。这是码头最关键的一个环节，所谓装船作业就是把 堆场上的集装箱装到船上去。这看似很简单的一个过程，但其中存在着很大的变 数。因为在同一时刻码头可装的箱子有很多，怎样安捧合理的装船顺序，将十分 的关键。在第二章和第三章的基础上，在装船的时候，中控会有一张配载船图， 大致决定了集装箱所要装的位置。但由于外一的特殊情况，有很多时候是要违背 这张船图的，因为现场作业时以效率优先。如果为了装一个箱子而让整个装船作 业停顿下来，这是不允许的本章前半部分介绍怎样合理的安捧装船顺序，并给 出算法( 见【1 9 】) ；后半部分涉及到集卡调度问题。在前半部分已经确定装船顺序 的前提下，怎样合理快速的调度堆场中的集卡来完成这些任务，其中要考虑到任 务与集卡的距离和照顾某些桥吊等因素。关于集卡调度的其它智能优化系统见参 考文献【2 】、【3 1 、【4 】、【5 】和【2 0 】。 第1 2 页 姓名：王超学号：0 5 2 0 2 5 3 0 3上海浦东袋装箱码头智能化生产控制研究 1 5 小结 本章首先介绍了中国及上海港口发展的机遇及挑战，然后简要介绍集装箱码 头作业流程及集装箱码头信息管理系统，最后分析上海港及上海浦东集装箱码头 有限公司的劣势所在并提出了整体的解决思路，为下文的详细阐述列出了总体纲 要。 第1 3 页 姓名：王超学号：0 5 2 0 2 5 3 0 3上海浦东集装箱码头智能化生产控制研究 第二章堆场计划 在上海港，几乎所有从码头进口和出口的集装箱都要在码头存放一段时闻。 堆放计划的合理性及其与以后各环节的有效衔接，是关系到整体码头装卸效率的 重要基础，堆场计划主要包括进出日集装箱的堆放及日常的翻箱、转栈操作。本 章先介绍比较简单的翻箱问题，再就进出口集装箱的堆存计划作一阐述。 2 1 翻箱问题描述 在集装箱码头堆场中集装箱堆放一般是以堆栈为基本单位的，每个堆栈共有 六列。堆栈中每列的最大堆放高度是由轮胎吊性能决定的。一般分两种情况： 1 每列最多可堆放4 个集装箱；2 每列最多可堆放5 个集装箱。 下面以情况l 来简要说明堆栈堆放要求，情况2 可傲类似处理。图2 1 是集 装箱堆栈的结构图，堆栈中共有2 6 个位置，其中第5 个和第2 6 个位置在翻箱过 程中作为临时翻箱位，但翻箱完成后不能堆放集装箱。同时因为翻箱过程的实际 要求限制，共需留有5 个位置作为临时翻箱位，其中包括第5 个和第2 6 位置。 这样堆栈中最多可堆放2 1 个集装箱。 第五层 第四层 第三层 第：层 第层 一耻5 26 一争4 o9 13 l72125 o 3o8l2l62024 一一卧2o71ll5l92 3 一一m l0610l41822 第一列第二列第三列第四列第五列第六列 图2 1 在集装箱堆栈中，通常是根据集装箱各种相关属性来分类堆放集装箱的。针 对客户的实际需求，主要考虑集装箱的5 个基本属性。它们分别是航次、港口、 重量等级、箱型、装船码。其中航次属性表示集装箱将要装船的航次；港口属性 表示集装箱是在哪个港口卸载；重量等级是集装箱以一个基本重量单位( 例如 5 0 0 0 千克) 进行转化后的等级；箱型属性表示集装箱属于大箱型还是小箱型； 装船码属性则表示集装箱是否通过海关报关。 第1 4 页 姓名：王超学号：0 5 2 0 2 5 3 0 3上海浦东集装籍码头智能化生产控制研究 在集装箱码头，集装箱从集装箱堆场闸口进入堆场，在闸口由闸口监控系统 分配集装箱在堆场上应该堆放在哪个堆栈中，然后托运到分配堆栈，轮胎吊依照 集装箱到达堆栈的先后顺序进行堆放。这种按照先进先堆放原则堆放的集装箱堆 栈状态，我们定义为集装箱堆栈的初始状态。当集装箱到达码头比较集中时，集 装箱堆栈的初始状态往往是无序的，不合理的为了缩短装船时间，提高码头的 生产效率，需要对无序的不合理的集装箱堆栈进行预翻箱，使集装箱堆栈状态能 够满足堆放原则。此外，预翻箱一般是由轮胎吊来完成的，由于外一期客观条件 的限制，轮胎吊不可能有很多时问来进行预翻箱作业。怎样在最短的时间内( 以 最少的翻箱步骤为衡量标准) 达到符合要求的状态显得更为紧迫和重要。最小预 翻箱问题正是为了解决这个问题提出的。最小预翻箱是对已经存放在堆场上的集 装箱进行整理，以最少的翻箱次数达到目标状态。 为了说明什么状态是符合要求的状态，有必要介绍以下集装箱堆栈的堆放原 则： 1 集装箱堆栈在堆放时要保持同一列中的集装箱尽量是同一类别的，即当我们 选择集装箱五个属性中的一个属性为堆箱依据时，要求每列中集装箱的属性类别 相同。如图2 2 所示，我们以港口属性为堆箱依据，堆栈l | i 有a ，b ，c ，d ，e ， f 等六个港口类别的集装箱。因为需要保持咧i 集装箱属于同类别，所以第 三列第二层位置上e 港口集装箱需要和第五列巾两个e 港口集装篇堆放在同咧 巾，第五列第二层位置上d 港口集装籍剐应该同第四列巾两个0 港口集装籍堆放 在同列巾，从而满足弼列中堆放的集装篇属于嗣类别的要求。 f i abedf 【 abcdef abcdf 图2 2 在无法满足同一列属于同一类别的情况下，才允许在同一列中堆放不同类别的集 装箱。如图2 3 所示，我们仍以港口属性为堆箱依据，堆栈中有a ，b ，c 三种港 口类别的集装箱。因为堆栈实际情况的限制，我们只能尽最大可能保证网一列属 于同一类别，所以图中1 7 个 港口集装箱应当把它们堆放成5 列，而剩下的一 第1 5 页 姓名：1 = 超学号：0 5 2 0 2 5 3 0 3上海浦东集装箱码头智能化生产控制研究 个b 港口集装箱和一个c 港口集装箱只能混合堆放在同一列中。 aaa aaab aaaaa aaac 图2 3 2 在实际堆放的时候，常常需要以两个或两个以上的集装箱属性为依据来进行 分类堆放，并且它们之间具有不同优先级。下面以航次和港口两个属性为依据， 并假设航次属性的优先级大于港口属性的优先级来说明分类堆箱的情况，以三个 或三个以上属性为依据分类堆放的情况可依此类推。航次属性的优先级大于港口 属性的优先级是指在同一列中首先保证集装箱航次属性相同，然后保证集装箱港 口属性相同。当无法满足上述要求的时候，那么先放弃同一列中集装箱同港口的 限制，其次再放弃同一列中集装箱同航次的限制。如下图2 4 所示，第三列第三 层位置上b 航次e 港口集装箱应该与第五列中两个b 航次e 港口集装箱堆放在同 一列中，第五列第三层位置上b 航次b 港口集装箱应该和第四列中两个b 航次b 港口集装箱堆放在一列中。在图4 中前一个字母代表航次属性，后一个字母代表 港口属性。 af i aabbebbaf aa abacbbb e af aa b cbbb eaf 图2 4 3 堆栈中的集装箱按一个或多个属性分类堆放时不能满足同一列中集装箱同类 别时混放列的堆放规则如下： ( a ) 如果一列中集装箱是由单一属性不同造成的混合，则依据如下规则堆 放。即考虑重量等级属性时，重量等级大的集装箱须堆放在重量等级小的 集装箱上面；考虑装船码属性时，不能装船的集装箱都须堆放在此列能装 第1 6 页 姓名：王超学号：0 5 2 0 2 5 3 0 3上海浦东集装箱码头智能化生产控制研究 船集装箱的下面等等。 ( b ) 如果一列中集装箱是由多种属性不同造成的混合，则需要把符合单一 属性混合个数较多的集装箱集中放在底部，然后按照规则a 堆放单一属性 混合的集装箱。 把按照以上规则堆放的集装箱堆栈状态称为集装箱堆栈的允许状态。因 此，集装箱堆栈预翻箱问题就是从集装箱堆栈初始状态出发，以尽量少的搬 箱步骤使集装箱堆栈状态达到允许状态，并且我们把这种以最少搬箱步骤达 到的集装箱堆栈允许状态称为目标状态。 2 2 翻箱问题解决方案 集装箱预翻箱问题是一个复杂的组合优化问题，求解组合优化问题就是找出 一种搜索过程或规则，它是基于某种思想和机制，通过一定的途径或规则来得到 满足用户要求的问题的解。目前，解决该类组合优化问题的常用方法有模拟退火 算法、遗传算法、禁忌搜索算法及启发式算法等。模拟退火算法、遗传算法、禁 忌搜索算法等指导性搜索方法具有较强的通用性，无需利用问题的特殊信息，然 而容易造成对已知问题信息的浪费。启发式算法对问题的依赖性较强，但对特殊 问题却能利用问题信息较快地构造解，其时间性能较为理想。针对集装箱预翻箱 问题中对实时性和优化性的要求，我们从集装箱预翻箱问题的实际情况出发，考 虑将集装箱问题分解，提出首先根据堆箱规则确定集装箱堆栈的目标状态，然后 运用改进的广度优先算法计算搬箱步骤的解决方法，设计和实现智能集装箱预翻 箱系统i t b s 。 2 2 1 翻箱问题的抽象化 为了便于描述问题，我们作如下定义： 定义2 i ：集装箱堆栈的一个堆放状态称为一个节点，不同的堆放状态对应 不同的节点。 因此，我们把集装箱堆栈的初始状态称为初始节点f 。，满足堆箱规则的集装 箱堆栈状态称为允许节点o ，集装箱堆栈的目标状态称为目标节点t ，所有的 第1 7 页 姓名：王超学号：0 5 2 0 2 5 3 0 3上海浦东集装箱码头智能化生产控制研究 允许节点组成允许节点集肘= f 。：， ，所有集装箱状态构成的节点集是 矿，并且矿，矿，m ，m c 矿 定义2 2 ：通过一次移动把堆栈中一个集装箱从一个位置搬到另一位置，使 得集装箱堆栈状态转化到另一集装箱堆栈状态的操作定义为一条边p 。所有由集 装箱堆栈状态变化产生的边组成边集e ，e = q ，) i ( 0 ，) 能使f ，转化为 k ，i f l k e n 。 定义2 3 ：尼，鳓q ，) 定义为两个顶点之间最短路径的长度，其中，y 。 集装箱堆栈预翻箱闯题归结为： 给定无向图g = ( 矿，e ) ，其中矿是所有集装箱状态构成的节点集，e 是所有 由集装箱堆栈状态变化产生而成的边集，已知初始节点，要求找出满足堆箱规 则的允许节点集m = 纯，：，) ，并确定一个允许节点o ( 即目标节点 i 。= k ，f 。m ) ，对任意ke 肘，满足如呼矗( ，t ) s 如，鲫( f ，o ) ，并给出此 条最短路径工= ( f ，i 1 ) ，( ，f 2 ) ，( f 删( 。津) ，f 。) 其中f 1 ，f 2 一，f 蚴( 。，。) 矿， f 。y ，f 。m 。 2 2 2 目标节点的确定 根据集装箱堆栈预翻箱问题的描述，我们知道首先应当找出满足堆箱规则的 允许节点集m = ，f 。：， ，然后逐个比较对应的拓馏曲o 来确定唯一的目标 节点。然而就问题的规模和复杂度而言，穷举出允许节点集肘的巨大计算量 是无法承受的。在这里我们利用集装箱堆栈预翻箱问题的特征信息来快速地构造 出目标节点。 假设以图2 2 中表示的集装箱堆栈状态为初始节点t ，图2 5 中的集装箱堆 栈状态分别为满足堆放原则的两个允许节点，：，显然 如增叻( f ，f 。1 ) 如呼矗( ，i ，2 ) ，跆，彬 ( ，i ，1 ) = 2 ，如增砌( j ，2 ) = 9 。从初始节点 与允许节点的对比中我们可以得出：当允许节点的堆放情况与初始节点的堆放情 况相近时对应的 哪咖o 较小。基于该特征，我们采取构造策略从允许节点集m 第1 8 页 姓名：王超学号：0 5 2 0 2 5 3 0 3上海浦东集装箱码头智能化生产控制研究 中确定目标节点t 。 f f 8df l bcdef l bc0ef 图2 5 我们以堆箱规则为基准统计出各类属性集装箱的总数以及需要占的列数和 可能混放的列数，然后根据初始节点的堆放情况以尽可能保持集装箱不搬动为原 则来确定一个目标节点。由于目标节点的确定是尽可能保持集装箱不搬动为原则 来确定的，这样能够在以后搬箱步骤的求解中大大降低搜索最短路径的复杂度。 初始节点大约有( 硝s ! 地一一) ! ) 种不同的排列，而目标节点确定后初始节 点不同的排列降为( 一m ) ! ss ! 舾一刀+ 所) ! ) 种不同的排列，其中行为总集 装箱个数，历为可不搬动集装箱个数，s 为集装箱堆栈位置个数。同时能使确定 的目标节点既满足堆箱规则又可使缸，鳓( t ，) 趋近真实的缸愕曲( ，屯) 。 2 2 3 搬箱步骤的求解 在确定目标节点艺之后，就可以开始搜索从出发到的最短路径 上= ( f ，i ) ，( 2 ) ，( 删( 岫) ，f ：) ，其中，f 2 ，蝌( ) y ， 矿，e 吖。最短路径求解的常用算法是广度优先算法b f s ( 这个算法可 以在任何一本算法书中找到) 。广度优先算法是盲目搜索算法的一种，它的 特点是：当发现目标节点时，已经找到了到达目标节点的一条最短路径。然 而它的缺点是要求产生和存储一棵庞大的搜索树( 树中的节点个数等于 p “1 一1 ) p 一1 ) ，6 是节点的子节点最大个数， 是目标节点的深度) 。在集 装箱堆栈搬箱步骤的搜索过程中，由于一个节点最多可能产生3 0 个子节点， 当 太大时使得算法性能非常差，以至计算机的存储空间不能容忍，计算速 度不能满足实时性要求。 第1 9 丽 姓名：王超学号：0 5 2 0 2 5 3 0 3 上海浦东集装箱码头智能化生产控制研究 为了克服用传统广度优先算法搜索翻箱步骤时间复杂度和空间复杂度 上过大的局限，我们主要对广度优先算法进行了如下改进： 1 利用由问题信息构造出的目标节点，对初始节点中与目标节点对应的部 分匹配集装箱进行锁定使之不能移动，从而减少搜索分支的大量扩展。 2 引入启发评估函数以力，g ( x ) ，| i l ( x ) 表示搜索图中节点工的深度，g ( x ) 表 示在节点工中与目标节点对应的部分匹配集装箱个数。由于在集装箱预翻 箱问题中目标节点确定后扩展子节点到深度为 胍娥战i g _ 珩+ l ( m 就胁辔珩为最大堆箱高度) 时至少能使节点中一个集装 箱堆放到与目标节点匹配的对应位置，利用这一特定信息结合启发评估 函数来确定下一候选节点。设任意节点x ，以节点x 为根节点，深度为 m 胁自g 所+ l 的广度优先扩展子树节点集为口= 岛，如，6 3 ， ，选取下一 候选节点y ，y 曰使得任意也口，( 力 厂( 6 ，) ，且当存在以使 厂( ) ，) = ，( 玩) 时，j l ( y ) j j l ( 以) 。进而再以候选节点y 为根节点进行深度为 朋缸王昆0 咖+ l 的广度优先扩展选取下一候选节点，直到候选节点中集装 箱堆放与目标节点完全匹配。 2 3 集装箱堆存计划概述 在集装箱码头各种机器设备的生产效率中，桥吊效率是最重要的。保证 桥吊的效率直接关系到集装箱码头上述两个效率目标，所有的生产过程和设 备调配都需要服务于桥吊。一般来说，一个桥吊每8 0 一1 2 0 秒可以完成一次 将箱由集卡吊到船上指定位的动作，这样来说桥机每个小时应该完成3 0 一4 5 次吊箱动作。但很多其他的因素会影响到码头的操作，而且这些因素又是相 互影响的。如：集装箱在堆场上的堆放，会直接影响到堆场上轮胎吊的工作 量，内集卡的行进距离以及桥吊的工作效率。 合理紧凑的装船序列才能够确保一个平滑的装船进程，减少等待时间。 第2 0 页 姓名：王超学号：0 5 2 0 2 5 3 0 3 上海清末集装箱码头智能化生产控制研究 圈z 6 船公司提供的船图示例 船图示例一般要符合如下要求： 1 ，超高箱，超重箱，平项箱等特殊箱在船上有特定的位置要求： 2 不同长度的箱需要放在符合长度要求的贝位里； 3 出口箱会根据其箱型，卸货港口和重量等级来分类，类别相同的箱在船上放在一起； 阁2 7 常用的两种装船方式 船的每个贝位通常会划分成许多的小分块，配载时每个分块被区分开来 考虑；对于贝位里的小分块，配载通常可以使用两种策略，一种是逐层装载： 另一种是逐歹装载：无论哪种装船策略都是需要麓够连续地将这个小分块填 满，才能继续装载它上面的分块； 第2 l 页 姓名：王超学号：0 5 2 0 2 5 3 上海浦东集装箱码头智能化生产控制研究 牛待蓑鲁篇在堆量上的分布 图2 8 出口箱在堆场上的分布 | i * 上的列 贝位的每个小分块里箱的种类不多，但同种类的箱都需要能连续的取得，所 以一种合理的摆放方法就应该像图四右面的示意，尽可能使每一列里面堆放的是 符合装船需要的同种类箱。所以将出口箱按照装船要求进行分类，并且最小分配 单元应该是列；实际装船要求构成了c a g 放箱策略的基础。 2 4 集装箱堆存解决方案一c a g 放箱策略 场地位置级别： 图2 9 第2 2 页 姓名：王超学号：0 5 2 0 2 5 3 0 3上海浦东集装箱码头智能化生产控制研究 出口箱在船舶到来前的几天内，就开始已经陆续进场，它们通常由外集卡运 到码头，到达的时刻，数量都不可控制。出口箱的到来是无序和随机的，很难事 先预测和安排，但堆箱效果要求它们是规则有序的，如何将无序随机的进箱序列 转变为规则有序的堆场放箱是c a g 需要解决的最大问题。c a g 是通过抢占的方式 来解决这个问题的： 图2 1 0c a g 放箱原理示例 例如一段时间内有某条船的a ，b ，c ( 红，兰，黄) 3 个港口的箱子要进场； 由于是随机到来的所以这三种箱子的数量和到来时闻顺序事先并不能预测和知 晓。 如图2 1 0 中最左边的图，假设首先到来的是a ，b 两港口的箱子，这时该间 位中的6 个列都是空闲的，c a g 会给先到的两个种类箱子平均的分配三个空列， 如a 港口箱( 红色) 分到1 ，2 ，3 列，b 港口箱( 蓝色) 分到4 ，5 ，6 列； 如图2 1 0 中中间的图，随着a ，b 种类后续箱的到来，它们会被c a g 逐列的 填充到它们各自的空间，就是说每当一列填充满了，下一个到来的同类型的箱子 就放在这一列的傍边； 如图2 1 0 中最右边的图，如果用完了自己的预留空列或者来得较晚，就可以 去抢占别人的列，如c 港口箱( 黄色) 来的较晚，已经没有多余的空列分给它， 所以它要抢占别人多余的空列，但一次只能抢占一列，而且要从最远端开始抢占， 目的是尽可能让同种类箱靠近，假设这时a 港口到来的量比较大已经用完了自己 的空列，b 港口箱还有4 ，5 两个空列，c 港口箱只有抢占b 港口的一个空列( 第 6 列) ；随着时问的推移，b 港口到来的箱量较少而c 港口的箱子较多，所以c 港口在用完了自己这一列后又抢占了b 港口一个空列( 第5 列) 。 图2 1 0 就是这种预分配和抢占的实际效果图，可以看到尽管我们事先并不 第2 3 页 姓名：王超学号：0 5 2 0 2 5 3 0 3上海浦东集装箱码头智能化生产控制研究 能预测出每种箱子会来多少，但是还是能将这些无序的箱子变成符合分类要求的 有规则的箱子。 图2 1 1c g a 总体设计模块图 第2 4 页 姓名：王超学号：0 5 2 0 2 5 3 0 3 上海浦东集装箱码头智能化生产控制研究 p a 当前搜索： 图2 1 2 第2 5 页 姓名：王超学号：0 5 2 0 2 5 3 上海浦东集装箱码头智能化生产控制研究 p a 钝化搜索： 图2 1 3 第2 6 页 姓名：王超学号：0 5 2 0 2 5 3 0 3上海浦东集装箱码头智能化生产控制研究 a u 搜索： 图2 1 4 第2 7 页 姓名：王超学号：0 5 2 0 2 5 3 0 3上海浦东集装籍码头智能化生产控制研究 p a 全区搜索： 图2 1 5 第镐页 姓名：王超学号：0 5 2 0 2 5 3 0 3上海浦东集装箱码头智能化生产控制研究 箱位置的搜索流程： 图2 1 6 当前已激活，钝化p a 索引搜索过程： 该搜索部分是整个搜索流程的的第一步，该部分搜索过程根据当前等待给 位的箱信息直接在已经建立并处于已激活状态的p a 索引集中查找同箱信息相匹 配并且满足必须满足的规则的p a 索引，如果找到匹配的可以很快指出合适的a u 位置；在a u 中根据优先级规则在a u 中查找较为优化的列位置。 第2 9 页 姓名：王超学号：0 5 2 0 2 5 3 0 3上海浦东集装箱码头智能化生产控制研究 使用到的规则： 1 。必须满足的规则： 规则i d规则名称 b r 旬0 2b i o c kt r a c l o rl i m i t b r 伽b l o c i w 0 r k l o a dl i m n b f - 0 1 0b i o c km 0 垤m 朗tl j m n s u 厶- f o f a j3 m l e s s 肿0 6m a x i m u ms i a c kc 0 n t a i n e rc 0 u n t s r 0 0 9s t a c kc u 丌1 e n t a 0 w a b l el e n g l h s r _ 0 1 0m i n i m u ms h u h l es i o l s s f i d l 2y a c 阳n ea v a i l a b i 咐 s f - 0 1 3 y a r dc 陷n ew 0 n i o a dl m i l s r _ 0 1 6 y a r dc 旧n es e g r e g a 6 0 n s 曲南耐6 凡“蛞 l r 枷1 s l a c k i n gh e i g h fl i m n l r 0 0 3 p e n d | n gu n a v a i l a b i er e n d l r 0 0 4i s 0 i a 制l a n er u l e l r 0 0 5v 翻d i a n e l r 0 0 7u n a v a a b i e a 陀ac h e c k l r _ 0 0 8 l a n et y p e l r 加1 0 e x i s l i n gr e s e e a r e a l r - 0 1 1 s 脚v a g ep i a n l r 0 1 2h 0 tp i c k u d l r _ 0 1 3 n 0 m i n a 例e m p t yc o n l a i n e r l r m l 4h o i dd e l e n o n l r _ 0 1 6f 毡s e n ea 陀ah o lm o v el i m i l l r - 0 1 9 m i x i n gl e v e i 0 l f t 旬2 0l a n eg 巾u n d i n gc o n 订o i l r ? ? ?e t b 辩0 a r 甜o n s u b 勘f a 7 5 ，l j 怕s 7 - o l 引 3 4 m l 钨 l r 0 2 2s s 0 0 4 p ac u r r e n tk e yl o c a t i 佃s t a c kp o s i t i o n y b s n o a w a y 胁ma c c e s s i b l ee n d 第3 0 页 姓名：王超学号：0 5 2 0 2 5 3 0 3上海浦东集装箱码头智能化生产控制研究 分配新a u 搜索过程： 当没有现成的p a 可供使用时，考虑在堆场上的所有空列中分配出一块合适 的au 对于满足了必须满足的规则的多个a u ，可以使用优先级规则来选出最为合 适的一个来作为这次搜索的a u ，并在其上建立p a 索引。 必须满足的条件： r u i e 憾r u i en a m e a r 0 0 1 s e r v i c ea r e at a c 舾rl i m i l a r 旬0 2a v a i l a b i eg m u n d i n ge q u i p m e n t s u w o 拓“2 ，u f e s b r 0 d 1a v a ；l ab f et 础rl a n e b r 0 0 2b l o c kt r a c l o rl i m n b r 硼b 1 0 c kw o r k l o a dl j m i l b f t - 0 1 0b i o c km o v e m e n ll l m n s u b 姚| 4 m l e s s r - 0 0 6m a x i m u ms l a c kc o n l a i n e rc o u n t s r 0 0 9s l a c | ( c u 丌e n l a i l o w a b i el e n g f h s r 0 1 0m n i m u ms h u 仟l es i o t s s r 旬1 2y a r dc 陷n ea v a a b i l y s r - 0 1 3、r a r dc r a n ew o 水i o a dl i m i l s 鼬1 6y a c r a n es e g r e g a t i o n s “6 - f o f a 6 m l e s l r 0 0 1 s i a c k i n gh e j g h tl i m i l l r 0 0 4 f s o f a 自e dl a r u j e l 啪0 5v b i di a n e l f 如0 7u n a v a j i a b l ea 伦ac h e c k l f 旬1 0 e x s l i n gr e s e ea 陀a l r - 0 1 1 s 虹啪g ep i a n l f 旬1 2h o