（计算机应用技术专业论文）港口泊位分配与装卸桥调度系统的建模与优化.pdf

摘要 集装箱港1 ：3 在国际物流和国民经济中具有很重要的战略性地位，是国际物流中不可 或缺的重要节点。在过去的四十年中，集装箱作为重要的个体装载方式在国际海运中起 着毋庸置疑的重要性作用。随着集装箱货物运输量的不断增长，集装箱港1 3 之间的竞争 越来越激烈。如果没有有效地利用信息技术和优化方法，那么集装箱港口的运营将是难 以想象的。 衡量一个集装箱港口的重要指标是船舶的在港时间( 集装箱终端为靠岸船舶装卸所 花费的平均时间) ，从船舶的角度看是要最小化船舶停靠的费用。另一个密切相关的衡 量指标是港口装卸桥的使用效率，装卸桥在一定时间内的吞吐量。即装卸桥装卸的集装 箱总数装卸桥操作的小时数。对于集装箱港口来说这是一个利润衡量指标，应该最大化 此指标。衡量集装箱港口很大程度上基于船舶的平均在港时间和装卸桥的利用效率。本 文研究的问题就是要提高这些指标。 正是在上述背景下，本文综合运用运筹学、优化理论与方法、和计算机仿真等学科 理论和方法，在专业人士对集装箱港口的理论和实践研究基础上，对港口泊位分配，装 卸桥调度问题进行了系统的分析和研究。 本文做了以下几方面的工作： 1 介绍了课题的选题意义、国内外研究现状。分析了集装箱港口的基本运作流程。 2 描述了泊位分配问题的非线性模型，以最小化船舶的在港时间为目标，并考虑 了船舶处理的优先权条件约束问题。 3 。对装卸桥调度模型进行了改进，考虑了装卸桥的装卸能力约束，不同的装卸桥 处理集装箱的能力不同，并以最小化船舶的等待时间为目标进行优化。 4 介绍了两种智能混合优化策略g a s a 和g a t s ，针对不同模型，分别对模型进 行了有效的求解，并通过算例仿真结果与传统遗传算法所得结果进行了比较。 关键词：泊位调度装卸桥调度遗传算法混合优化策略 a b s t r a c t c o n t a i n e rt e r m i n a lp l a y sa l li m p o r t a n ts t r a t e g i cr o l ei ni n t e r n a t i o n a ll o g i s t i c sa n dn a t i o n a l e c o n o m i e s i t sa ni m p o r t a n tn o d ei ni n t e r n a t i o n a ll c l g i s t i e s d u r i n gt h el a s tf o u rd e c a d e st h e c o n t a i n e ra s 锄e s s e n t i a lp a r to fau n i t l o a d - c o n c e p th a sa c h i e v e du n d o u b t e di m p o r t a n c ei n i n t e r n a t i o n a ls e af r e i g h tt r a n s p o r t a t i o n 、矾me v e ri n c r e a s i n gc o n t a i n e r i z a t i o n ，t h en u m b e ro f s e a p o r tc o n t a i n e rt e r m i n a l sa n dc o m p e t i t i o na m o n gt h e mh a v eb e c o m eq u i t er e m a r k a b l e o p e r a t i o i l sa r en o w a d a y su n t h i n k a b l ew i t h o u te f f e c t i v ea n de f f i c i e n tu s eo fi n f o r m a t i o n t e c h n o l o g ya sw e l la so p t i m i z a t i o nm e t h o d s ， n 圮m o s ti m p o r t a n tp e r f o r m a n c em e a s u r et oas h i p p i n gl i n ei nr a t i n gat e r m i n a li st h e v e s s e lt u r n a r o u n dt i m e ( t h ea v e r a g et i m et h et e r m i n a lt a k e st ou n l o a da n dl o a dad o c k e d v e s s e l ) f r o mac u s t o m e r sp e r s p e c t i v e ，t h i sm e a s u r ei s ac o s tm e a s u r et h a ts h o u l db e m i n i m i z e d a n o t h e rc l o s e l yr e l a t e dm e a s u r et h a ts h i p p i n gl i n e su s ei nc h o o s i n gat e r m i n a li s t h ea v e r a g eq u a ye r a n er a t e ，t h eq u a yc r a n e s t h r o u g h p u td u r i n ga p e r i o d , ( t o t a ln u m b e ro f c o n t a i n e r su n l o a d e do rl o a d e d ) ( t o t a ln u m b e ro fh o u r st h eq u a yc l - a r l eo p e r a t e d ) f o ra s h i p p i n gl i n e ，t h i si sap r o f i tm e a s u r et h a ts h o u l db em a x i m i z e d s h i p p i n gl i n e sj u d g e c o n t a i n e rt e r m i n a l sl a r g e l yb a s e do nv e s s e lm m a r o u n dt i m ea n dq u a yc r a n er a t e a l lt h e d e c i s i o np r o b l e m sw es t u d i e dd u r i n gt h i sp a p e rc o n t r i b u t e dt oi m p r o v i n gt h e s em e a s u r e s i nt h ea b o v ec o n t e x t , t h i st h e s i su t i l i z e sm a n yk i n d so fd i s c i f ，l i n et h e o r ya n dm e t h o d , s u c ha so p e r a t i o nr e s e a r c h , o p t i m i z a t i o nt h e o r ya n dm e t h o d , c o m p u t e rs i m u l m i o na n ds oo n f o l l o w i n gt h et h e o r ya n dp r a c t i c a le x p e r i e n c eo fs p e c i a l i s t s ，w er e s e a r c ht h eb e r t ha l l o c a t i o n a n dq u a yc r a n es c h e d u l i n gp r o b l e m t l l i st h e s i sa c h i e v e st h ef o l l o w i n gr e s u l t s ： 1 i n t r o d u c i n gt h es i g n i f i c a n c eo ft h i st o p i c ，t h ed o m e s t i ca n df o r e i g nr e s e a r c h p r e s e n ts i t u a t i o n e x p l a i n i n gt h eo p e r a t i o np r o c e s so f t h e c o n t a i n e rt e r m i n a l s 2 d e s c r i b i n g an o n l i n e a rm o d e lf o rt h eb e r t ha l l o c a t i o np r o b l e mt om i n i m i z et h e t u r n a r o u n dt i m eo fc o n t a i n e r s h i p sa n dc o n s i d e r i n gt h ec o n s t r a i n tw i t hs e r v i c e p r i o r i t y - ，+。，m 。 3 - i m p r o v i n gt h eq u a yc 湖e 专c 岛d u l i n gm o d e lw i t ht h e + 。 e o n s t r a i n to fq u a yc r a n e s w h i c hd i f f e r e n ti nt h ea b i l i t yo f h a n d l i n gc o n t a i n e r s o p t i m i z i n gt h e 7 p r o b l e mb y m i n i m i z et h et o t a lw a i t i n gt i m ec a u s e db y q u a yc r a n e s 4 i n t r o d u c i n gt w oh y b r i do p t i m i z a t i o nm a t e # e sg a s aa n dg a t sa n ds o l v i n g t w om o d e l sb yt h e mr e s p e c t i v e l y w ed e v e l o pp r o c e d u r e sf o re a c he x a m p l ea n d c o m p a r et h es i m u l a t i o nr e s u l t st ot h er e s u l t so b t a i n e db yt h et r a d i t i o n a lg a k e yw o r d s ：b e r t hs c h e d u l i n g , q u a yc r a n es c h e d u l i n g ，g e n e t i ca l g o r i t h m , h y b r i d o p t i m i z a t i o ns t r a t e g y 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取 得的研究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他 人已经发表或撰写过的研究成果，也不包含为获得墨生墨墨盘堂 或 其他教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研 究所做的任何贡献均已在论文中作了明确的说明并表示了谢意。 学位论文作者签名：每彳 签字日期： 2 d 。7 年 f 月2 0 日 学位论文版权使用授权书 本学位论文作者完全了解 墨洼墨墨盘堂有关保留、使用学位论文 的规定。特授权叁盗堡兰盘釜 可以将学位论文的全部或部分内容编入 有关数据库进行检索，并采用影印、缩印或扫描等复制手段保存、汇编， 以供查阅和借阅。同意学校向国家有关部门或机构送交论文的复本和电子 文件。 ( 保密的学位论文在解密后适用本授权说明) 学位论文作者辐辱干 导师牦知俊晒 签字日期：如叼年f 月日签字日期： 1 每a1 q 第一章绪论 第一章绪论 1 1 选题的研究背景、目的和意义 集装箱港口在国际物流和国民经济中具有不可替代的战略性地位，是国际物流中不 可或缺的重要节点。随着经济全球化进程加快，这种重要性日趋突出。集装箱港口物流 的显著特点就是空间资源有限，可配置资源有限。为了最大限度发挥港口的枢纽作用， 世界各集装箱港口委托专业研究机构针对自身特点对其集装箱物流运作管理模式进行 优化。 随着经济全球化进程的加快及其对整个世界的经济与产业结构产生重大影响，越来 越多的生产经营活动和资源配置在全球范围内进行。在此大趋势下，以国际集装箱运输 为代表的现代运输方式推动了新一轮国际航运中心和区域性集装箱枢纽港的竞争。而世 界经济的持续稳定发展和国际贸易量的高速增长，又为国际集装箱运输提供了充足的货 源。 我国的港口表面呈现一派繁荣景象，国家商务部对外贸易形式报告指出：2 0 0 5 年， 中国对外贸易延续了2 0 0 2 年以来快速增长的态势，全年进出口总额达1 4 2 2 1 2 亿美元， 进出口额的世界排名达到第3 位。据有关方面预测，2 0 1 0 年世界港口集装箱吞吐量可能 达到3 9 1 亿至4 6 5 亿标箱，至2 0 1 5 年将上升至5 亿至6 亿标箱。这表明2 1 世纪以集装箱运 输为标志的国际物流将持续稳定发展。天津港集装箱吞吐量预计，2 0 1 0 年为7 0 0 万标箱， 2 0 1 5 年为1 0 0 0 万标箱。这无疑为港口业的发展注入了一针强心剂。同时给天津港集装箱 码头的泊位、堆场、机动设备和人员造成了不小的压力。但是，从竞争力上看，中国内 地港口还离国际枢纽港有相当大的差距。目前的港口业，深圳港集装箱运量已经超越韩 国釜山港，居世界第4 位。上海港也由去年世界排名第4 位跃居为第3 位。在世界集装箱 运量前5 名中，中国的香港、上海、深圳三地稳居其中。但是，深圳与上海两大港口的 世界排名同时升位，并不能掩饰中国港口目前面临的问题。在国际航运里，国际货物转 口占有很重要的地位，这恰恰是中国港1 ：3 发展所短缺的。上海、深圳两大港口中转量仍 然不足，目前盐田港货物中转量仅占总货量的2 左右，香港却高达4 0 0 , 4 ，中国内地出口 到欧美等地的货物中7 0 要通过韩国釜山港中转。因此可以说，中国是一个港口大国， 但并不是一个港口强国。下面以天津港为例，来说明我国港口目前所存在的问题。 天津港集装箱码头始建于7 0 年代末期，1 9 8 0 年底在三港池建成我国内地第一座集 装箱专用泊位。1 9 8 5 年以后，先后建成四港池集装箱泊位和东突堤南侧的集装箱码头。 为适应船舶大型化需要，又先后将原2 7 号、2 8 号、2 9 号泊位改造为可靠泊第六代集装 箱船的专用泊位，大幅度提高了泊位等级。结合港口货类结构的调整，一港池西侧盐杂 通用泊位也于去年改造为第一、二代内贸集装箱泊位，j 者强了天津港口集装箱接卸能力。 根据天津港统计资料显示，天津港北疆港区现有生产用仓库面积1 9 1 5 2 万平米，堆 场面积2 2 6 1 9 0 万平米，其中集装箱堆场面积5 1 1 9 5 万平米，堆存能力为4 1 6 7 万t e u ( t w e n t y f o o te q u i v a l e n tu n i t 标准箱，系集装箱运量统计单位，以长2 0 英尺的集装箱为 第一章绪论 标准) ：天津港保税区面积5 平方公里，主要从事国际贸易、出口加工和保税仓储：除 此之外，在港区周围也形成大量的后方堆场，根据天津口岸管理委员会的资料统计，港 外现有仓储库场3 9 7 家，总面积2 5 0 0 万平米，其中集装箱仓储库场3 9 家，面积2 2 0 万 平米，主要坐落在塘沽、东丽、津南、大港以及天津经济技术开发区内，基本围绕京山、 北环、李港三条铁路和津塘、杨北、津北、津沽、东海五条公路分布。 从规划的角度看，目前在以下方面还存在一些问题： 一码头布局上的问题 1 港口现有各类泊位交杂程度较重。特别是北疆港区，散货、杂货、集装箱、客运 泊位交杂分布。港内道路交通条件较差，港区后方中心区域建立了保税区，分割了港区 道路，不利于集装箱疏运，影响泊位效率的发挥；同时后方集装箱堆场也呈交叉分布， 造成了统一规划、管理上的困难。 2 缺乏现代物流理念及相应的整体规划。根据现代港口物流对空间的要求，集装箱 码头必须具有长顺岸、大纵深的基本条件，从而使依托港口发展现代集装箱综合物流成 为可能。目前形成的北疆老港区，很难适应集装箱现代物流的发展要求。因此要加强北 港池区域土地开发的管理，实现土地资源的有序开发，否则无法满足现代物流集中划分 功能区的要求，必将贻误天津港集装箱物流发展的长远大计。 二泊位能力上的问题 目前天津港集装箱泊位的能力跟不上集装箱运量快速增长的需要。从1 9 9 5 年到2 0 0 5 年天津港集装箱吞吐量年均增长1 5 5 。随着津京地区经济的迅速增长，我国加入w t o 及西部大开发战略的实施，天津港集装箱吞吐量必将取得突破性进展。2 0 0 6 年天津港集 装箱吞吐量完成5 9 5 万t e u ，同比增长2 4 ，2 0 0 7 年预计吞吐量为7 0 0 万t e u ，2 0 1 0 年突破1 0 0 0 万t e u 。但是目前天津港集装箱专用泊位仅为7 个，核定年通过能力1 0 0 万t e u ，泊位实际利用率达6 0 0 。而且集装箱船大型化的趋势，对港口泊位水深和 作业条件要求越来越高。且受规模经济影响，环球主要干线航线上的集装箱船已向第五、 第六代及其以上发展，其载重量已达5 6 万吨以上，吃水深达1 3 1 5 米，并且载重 8 0 0 0 t e u 的集装箱船已在建造中。对于超巴拿马型集装箱船要求港口装卸桥的外伸臂不 低于4 8 米。因此仅仅通过码头改造已很难满足船舶大型化的发展要求，必须加快北港 池区域深水集装箱专用泊位的建设，从而确保天津港集装箱运量的持续增长和港口物流 产业的顺利起步。 j ，“，一 一三作业机械、仓库和聚场不足j 虽然这些年来天津市加强了港1 3 建设，大幅度地增加了投资，引进国外先进的港口 装卸和货场运输设备，增加了对仓库和堆场修建的投入，但是，仍然不能满足物流业务 增长的需要。因此，使得集疏运系统不配套，使得船舶停时加长，制约了客货吞吐量的 增长和港口经济效益的提高。 四运输网络上的问题 1 港口多式联运不发达，运输网络系统不完善。这方面的规划工作过去较为薄弱。 天津港腹地广阔，包括华北、西北的广大地区，通过新欧亚大陆桥港口腹地进一步延伸 第一章绪论 至蒙古、西亚及欧洲各地。从运输方式分析，超过5 0 0 公里运输距离时，铁路运输具有 明显优势：但是且前由于缺乏专业化的铁路换装设备，港区到天津铁路枢纽能力紧张以 及国铁自身存在观念，设备不足问题，导致铁路集装箱运输优势没有充分发挥出来，在 很大程度上也制约了天津港口集装箱物流产业的发展。同时，目前港口在运输网络系统 化建设上，缺乏统一规划，各种运输方式自行运作、自成系统，没有形成相互贯融的系 统化、网络化体系。 2 缺乏具备较强组织协调能力和服务规模较大的物流经营主体。除中远、中外运、 中储已开展现代物流业务以外，港务局所属仓储企业及港1 3 内外众多仓储企业规模较 小，功能单一，基本处于零散布局和分散状态，缺乏系统化的物流服务功能。 五港口信息化建设滞后，物流经营能力低，无法使港口物流效率最大化 从物流业应用的信息系统现状来看，尚未建立广泛的信息服务系统，虽已建立港口 e d i ( e l e c t r o n i cd a t a i n t e r c h a n g e 电子数据交换) ，但与开展航运交易、商品交易、信息 发布、金融结算、数据传输和文件传送等社会化服务要求还相距甚远，信息系统支持规 模小、效率低，而且服务项目有限、单项营运，不能支持现代物流企业所需要的网络设 计和货物购、运、调、存、管、加工和配送全过程的服务。巨大的信息资源没有得到有 效的开发利用。整个天津口岸信息服务系统的建设，有待在统一规划之下，协调配合、 整体推进。无论物流管理模式还是相应的物流软件都远未形成物流系统化、标准化、专 业化、共同化、现代化。 本课题研究目的就是：针对天津港集装箱港口的特点，依托运筹学、系统理论和控 制理论基础，利用先进的信息技术和现代智能优化技术，开展集装箱港口集装箱物流运 作的建模与优化研究，在对港口实际运作进行详尽和缜密分析的基础上，提出符合实际 的集装箱港口的船舶泊位调度系统和装卸桥调度系统的优化模型，并用智能优化方法进 行仿真。 泊位的分配，即在船舶到达之前为其分配靠港泊位。中国港口目前仍呈现出吞吐能 力不足的状况，实际总吞吐量却已经远远超过了港口码头的总设计吞吐能力。目前港口 码头泊位少，特别是深水泊位更少。虽然沿海港口码头泊位继续向大型化、专业化方向 发展，我国港口码头仍将会逐步进入超负荷状态。因此，集装箱港口泊位的合理分配和 利用对集装箱港口的运作效率起着至关重要的作用，它是制约港口物流系统进行有效运 作的瓶颈。 ， 。rt 装卸桥调度也是港口遥营的二个重心，船货吞吐蓬和港i ；3 运作效率常常是由怎样施 行装和卸来决定的。港口的装卸速度和集装箱的装箱顺序，是影响船舶在港时间 ( t u r n a r o u n d t i m e ) 以及船舶的运输效率的关键因素。目前在我国，许多大的集装箱港 口，经常发生船舶压港现象，这一方面是由目前我国港口的容量和设备跟不上物流发展 的需要，还有一个重要的原因就是港口的资源没有得到科学合理的使用，降低了港口的 服务能力。而港口中的装卸运输活动是频繁发生的。讨装卸搬运的管理，主要是对装卸 运输方式、装卸搬运机械设备的选择和合理配置与使用，以及装卸搬运合理化，尽可能 减少装卸搬运次数，可以节约物流费用，获得较好的经济效益。 在港口，任何物流管理系统包括装卸桥的运行常受到港口大小，高货物转载量和有 第一章绪论 限的物理设备的限制。因此众多港口将重心放在有效的装卸桥调度上，包括新加坡港口， 香港港口和澳洲港口。装卸桥位于海，陆分界处，并且由于操作空间和装卸桥结构的限 制，装卸桥只能在有限的区域移动。一种典型的装卸桥操作模式如下：船上要卸的集装 箱通常在甲板上以一定次序分成无优先权的工作包，或移到卡车上运输到堆场存储。相 反的操作，货物从场外卡车装到船上。在这种情形下，装卸桥和卡车通过固定的通道或 路线会出现拥塞，产生瓶颈。 泊位和码头的装卸与运输设备是影响装卸速度的关键因素。例如，集装箱船舶的泊 位分配问题，是码头运作的一个关键问题，涉及到船舶的航线类型、航行距离、船舶的 类型、可停港时间长短、中转集装箱的转移距离和集装箱中货物递交给收货人的时间限 制等因素，集装箱船舶的泊位分配与码头装卸和运输车辆的编组与调度之间还相互影 响。因此，如何对这样的问题进行建模就是一个复杂的问题。 所以，我们要加强对港口泊位分配和集装箱装卸桥的分配调度的研究。这对于优化 集装箱港口的资源配置，合理安排资源，降低运营成本，拓宽其业务范围，提高港口的 服务水平和竞争能力，都具有非常重要的意义。这将有利于集装箱物流系统在以下几方 面的改进： 1 ) 有利于缩短船舶在港停留时间。港口泊位分配和装卸桥调度的合理化可以减少 货物通过港口时不必要的时间浪费，使整个港口作业能更有序地进行。 2 ) 有利于降低港口装卸成本。当选择最佳的装卸桥调度方式，将会使货物在港内 流动中的多余能耗减少到最低，由此减少装卸成本中的动力消耗。 3 ) 有利于港口作业流程的合理布置。港口泊位分配方式和装卸桥调度方式的选择 直接影响到港口作业流程，进而影响到港口营运设施的布置。港口作业流程的合理布置 将减少港口建设的投资，提高港口土地的利用。 1 2 国内外研究现状及面临的问题 1 2 。1 集装箱港口集装箱物流运作流程 集装箱港口集装箱物流运作分为内运( i n b o u n d ) 和外运( o u t b o u n d ) 两部分。内 运过程运作如图1 1 所示：集装箱船舶在未到达集装箱港口前，先通知港口其期望靠港 时间，港口预先为船舶分配泊位( b e r t h ) ，调配港岸装卸桥( q u a yc r a n e ) 、内港卡车 ( i n t e r n a lt r u c k ) 、堆场装卸桥( y a r dc r a n e ) 准备服务。货船靠港后港岸装卸桥直接把 集装箱卸载到等待的内港卡车上，通过内港卡车把集装箱送到港口的货场。集装箱在货 场只是临时性存储，用户的港外卡车通过验放闸口的审核按时进入外港口，到达港口堆 场完成装车，最后集装箱运出港口。集装箱的外运过程与此相似只是顺序相反。 第一章绪论 图1 t 集装箱港口集装箱物流运作流程示意图 1 2 2 当前集装箱港口优化问题的研究现状 由于港口物流在国民经济中的重要地位，以及集装箱港口的特点( 货物量大而且增 加很快；可用的土地和资源有限) ，使得国外学者们对集装箱港口物流优化问题产生了 的研究兴趣。他们针对国外的不同港口采用不同的方法，对于不同的资源以多种目标为 导向，进行了各种尝试，并取得了可喜的成果。 ( 1 ) 国外计算机模拟技术在港口码头系统上的应用现状 在国外，计算机模拟技术在港口码头系统上的应用得到越来越多的重视，应用也越 来越普遍。例如，香港的c h i n al i g h t & p o w e r 公司，曾委托s a n d w e l li n c 利用模拟模型 研究增加何种的设备或者设施，以及以什么样的方式增加这些设备或设施，才能以最经 济的方式适应港口吞吐能力增长的要求【l 】；荷兰的t e b o d i nb v c o n s u l t a n t s & e n g i n e e r s 曾为印度某港口利用数值模拟模型研究港口的设计和卸船机的模型【2 】；计算机模拟器 e t o o l 用来评估在整个集装箱运输链中发挥作用的一些新设想和新概念，已用于对跨运 车堆码输送、自装输送机械与有轨龙门起重机配合、利用具有堆码和输送能力与跨运车 类似的新型机械作业的三种作业方案进行比较、评估【3 】；由德国i n s t i t u eo fs h i p p i n g e c o n o m i c sa n dl o g i s t i c s 开发的集装箱装卸系统模拟器s c u s y ，已经成功的应用于研究 集装箱的不同堆码方式对整体布局的影响、批较采用不同设备组合的堆场作业方式、分 析不同设备的适用对码头营运的影响等 4 f 以色列的学者开发出席乎研究多个港q 同时 营运的相互影响以及与劳动力有关问题的模拟模型。 目前，在发达国家从事港口码头系统模拟模型开发的人员和公司很多。如上面提到 的加拿大的s a n d w e l li n c ，香港的c h i n al i g h t & p o w e r 公司，荷兰的t e b o d i nb v c o n s u l t a n t s & e n g i n e e r s ，德国i n s t i t u eo f s h i p p i n g e c o n o m i c sa n d l o g i s t i c s 夕b ，还有美国的 j o r d a n w o o d m a n d o b s o n 公司、意大利的s i s t e m ia t e l e m a t i c a 公司等。近年来，对模拟模 型开发的需求在增加；模拟模型开发的要求在提高，应用动画模拟模型呈发展趋势；应 用于港口码头营运管理方面的模拟模型所占的比例越来越大f 5 。 第一章绪论 从国外公开发表的文献来看，计算机模拟技术在集装箱港口中的应用大致可以分为 以下几类： 一用排队理论和遗传算法对船舶的到港情况进行模拟分析，从而为港口的投资提 供决策依据，并讨论泊位动态分配对港d - i - 作效率影响 6 7 8 。 二对到港船舶的装卸箱过程进行模拟，研究了港岸集装箱装卸桥调度问题，同时 通过模拟还可以帮助制定堆场计划以减少翻箱率 9 1 0 。 三对集装箱的卸箱进场和出口装船进行模拟，对堆场内的交通情况进行分析，讨 论了港口交通工具配备问题以及自动化小车的应用问题 1 1 1 2 1 3 。 四对集装箱在堆场内的堆放情况进行模拟，分析了对于进口箱和出口箱的处理策 略问题，主要讨论了集装箱在堆场内的堆放策略以提高堆场利用率的问题 1 4 儿1 5 1 6 。 五对整个集装箱港口进行模拟分析，讨论了在新的作业方法或者管理模式下集装 箱港1 ：3 通过能力的问题；为集装箱港口的一些计划的制定提供决策支持；对集装箱在港 1 ：3 内部的运输过程进行合理物流规划；对港口的作业流程的优化以及港1 ：3 设备的合理计 划；模拟对新港1 3 的管理方法分析等 1 7 1 8 1 9 2 0 。 ( 2 ) 国内计算机模拟技术在港口码头系统上的应用现状 d 我国集装箱运输起步于2 0 世纪5 0 年代的铁路运输，国内集装箱运输始于1 9 7 2 年， 国际集装箱运输始于1 9 7 3 年，上海港、天津港是中国大陆创办集装箱运输最早的港口 2 1 。 港口码头系统计算机模拟技术早就被引进介绍到国内。从公开发表的文献来看，国 内交通部第一航务工程勘察设计院开发过煤炭码头装卸系统和散粮码头的计算机模拟 模型，武汉交通科技大学开发过集装箱码头装卸系统的模拟模型；天津大学开发过油码 头的计算机模拟模型；交通部水运科学研究所开发过用于研究堆场容量的散货码头计算 机模拟模型；交通部第三航务工程设计院与上海海运学院联合开发了马迹山矿石中转码 头的计算机模拟模型；上海海运学院做过一个应用于港口生产调度的动画模拟案例 5 。 国内对于港口调度以及信息化的研究起步比较晚，并且主要侧重于信息化平台构 建，而对于港区工作流程实施部分少有涉及，而这部分的性能优劣才是决定集装箱港口 决策支持系统的成败的核心。 ( 3 ) 对泊位分配和装卸桥调度问题的研究情况 ，泊位分配调度问题首先涉及泊位的分配，即在船舶到达之前为其分配靠港泊位。依 据所要满足的特定目标和约束不同，前人的研究大多把泊位分配归为多种不同的组合优 化问题。l a ia n ds h i h 2 2 研究了离散的泊位分配问题，并给出了分配问题的几个简单规 则：b r o w ne ta 1 1 2 3 1 为船舶的泊位段分配建立了整数规划模型；l i m 2 4 将泊位看作连续 的，而不是离散的段的集合，并讨论了假设在船舶都获得最佳的泊位情况下，如何最小 化船舶总长度，他还证明此问题属于约束二维包装问题，并且给出了图论的描述，因此 泊位分配问题是n p 难题。遗传算法 8 】 2 5 】 2 6 】和混和整数规划【7 】等多种启发式算法用 于此问题的求解。 第一章绪论 港岸装卸桥的调度问题是为靠港船舶分配若干港岸装卸桥完成装卸任务，包括把装 卸桥分配给不同船舶或者把装卸桥分配给船舶的不同部分，对此部分的优化没有绝对的 目标，一般目的是减少全部船舶的延迟同时保证港岸装卸桥使用的经济性，如：h a 曲a i l i a ，k a i s a re i 2 8 利用混和整数规划，以最小化船舶在港时间为目标来减少无效移动； d u b r o v s k y0 和l e v i t i ng 2 9 应用遗传算法外加安全约束来搜索优化的装卸流程： p c t e r k o f s k y 和d a g a n z o 3 0 3 1 研究了在静态情形下以最小化总体船舶的延迟时间为目 标的装卸桥调度问题，并提出了用各种精确的启发式算法来解决装卸桥调度问题； d a g a n z o 3 2 还研究了装卸桥调度策略对港口吞吐量和船舶延迟的影响。 1 2 3 目前国内外研究所存在的问题 港口码头系统作为一类较大的服务系统，具有多个随机因素，如船舶和货物集疏运 工具到港时间的随机性；船舶作业和码头操作受风、浪、雾、雨、等随机变化的影响； 泊位、装卸和堆取设备、堆场及职员的情况随时间变化；船舶和货源组成情况以及用户 的服务要求不断变化等；整个系统效率的发挥依赖于各子系统之间的相互协调，单个子 系统效率的高或者低，都影响整个系统效率的发挥。 众多学者一般都是针对港口集装箱泊位分配与集装箱装卸桥调度进行了建模优化 的研究，他们所作的工作是有一定意义的，但由于船舶靠港时间的不确定性和集装箱装 卸桥设备的动态性，这些大多针对静态环境假设的优化仿真模型难以实时反映港口运作 的特点，因此效果并不是很理想。由于港口系统的复杂性，仅考虑问题一个方面，其工 作也是不完善的。例如，对泊位分配的研究，有的只考虑最小化船舶在港时间，有的只 考虑将船舶服务时间最小化，或最小化船舶延迟费用等，不能综合考虑多方面的因素进 行研究。另外，在用遗传算法进行优化时，权值的选择随机性经验性较大，无法反映港 口集装箱物流系统的真实性。同时，目前的大多数研究存在着一些问题，一些研究注重 实际问题的形式化描述和讨论，没有深入地进行定量方面的研究，而另一些研究则注重 一般性问题的数学模型探讨，而对问题的研究背景、动机和实际意义没有描述，甚至没 有实际应用背景，从而存在着理论研究与实际背景脱节的现象。最后，以前大多研究中， 泊位调度和装卸桥调度彼此是独立研究的，近年来有少量研究从泊位调度和装卸桥调度 结合的角度来分析问题，但系统、深入的研究不多。 1 3 本文的主要研究工作和创新之处 课题的研究内容是港口泊位分配与装卸桥调度系统的建模与优化，利用最优化，运 筹学与控制理论对各环节的因素进行优化配置，并以计算机仿真为工具，理论和仿真相 结合的方法对提出的理论和方法进行分析和验证。在课题中主要完成了以下工作： ( 1 ) 分析了天津集装箱港口的发展现状和港口泊位分配和装卸桥调度对集装箱港 第一章绪论 口运营的影响。 ( 2 ) 描述了集装箱港口泊位分配的数学模型，并对装卸桥调度问题建立了改进的 数学模型。 ( 3 ) 介绍了混合优化策略g a s a 和g a t s 的思想和特点，并将此智能优化算法分别应 用于港口泊位分配和装卸桥调度模型的求解中。 ( 4 ) 用具体的算例说明了两种优化算法的有效性。 本文的创新之处如下： ( 1 ) 本课题将混合优化策略g a s a 应用于集装箱港口泊位分配调度模型的求解 中，并与遗传算法所得结果进行了比较，实现了全局快速优化。 ( 2 ) 改进了集装箱港口装卸桥调度的数学模型，在模型中考虑了不同装卸桥装卸 能力的约束，使模型更符合天津港口运行的实际情况。 ( 3 ) 将混合优化策略g a t s 应用于集装箱港口装卸桥调度模型的求解中，避免了 迂回搜索，并与遗传算法所得结果进行了比较。 无论从模型和方法上，以上几点都是新的，目前还未见到类似文献报道。 1 4 本文结构 第一章，阐述了课题的研究背景、目的和意义。 第二章，阐述了优化算法的含义，并具体介绍了遗传算法，模拟退火，禁忌搜索三 种智能优化方法。 第三章，讲述了集装箱港口泊位分配问题，首先给出了泊位分配的数学模型，根据 模型给出了混合优化策略g a s a ，并分别用传统的遗传算法g a 和混合优化策略对模型进行 了求解，通过实例证明混合优化策略g a s a 能实现快速全局优化。 第四章，讲述了集装箱港口装卸桥调度问题，首先改进了装卸桥调度问题的数学模 型，根据模型给出混合优化策略g a t s ，并分别用传统的遗传算法g a 和混合优化策略对模 型进行了求解，通过实例证明混合优化策略g a t s 能实现快速全局优化和避免陷入局部极 小解。 第五章，总结本文的成果及不足，指出今后的研究方向。 第二章智能优化算简介 2 1 引言 第二章智能优化算法简介 所谓优化算法，其实就是一种搜索过程或规则，它是基于某种思想和机制，通过一 定的途径或规则来得到满足用户要求的问题的解 3 3 。智能优化算法要解决的一般是最 优化问题。最优化问题可以分为两类：( 1 ) 求解一个函数中，使得函数值最小的自变 量取值的函数优化问题；( 2 ) 在一个解空间里面，寻找最优解，使目标函数值最小的 组合优化问题。典型的组合优化问题有：旅行商问题( t r a v e l i n gs a l e s m a np r o b l e m ， t s p ) ，加工调度问题( s c h e d u l i n gp r o b l e m ) ，o 一1 背包问题( k n a p s a c kp r o b l e m ) ， 以及装箱问题( b i np a c k i n gp r o b l e m ) 等。 就优化机制与行为而分，目前工程中常用的优化算法主要可分为：经典算法、构造 型算法、改进型算法、基于系统动态演化的算法和混合型算法等。 ( 1 ) 经典算法。包括线性规划、动态规划、整数规划和分枝定界等运筹学中的传 统算法，其算法计算复杂性一般很大，只适用于求解小规模问题，在工程中往往不实用。 ( 2 ) 构造型算法。用构造的方法快速建立问题的解，通常算法的优化质量差，难 以满足工程需要。譬如，调度问题中的典型算法有j o h n s o n 法、p a l m e r 法、g u p t a 法、 c d s ( c a m p l e u d u d e k s m i t h ) 法、d a u n e n b r i n g 的快速接近法等。 ( 3 ) 改进型算法，或称邻域搜索算法。从任一解出发，通过对其邻域的不断搜索 和当前解的替换来实现优化。根据搜索行为，它又可以分为局部搜索法和指导性搜索法。 a ) 局部搜索法。以局部优化策略在当前解的邻域中贪婪搜索，如只接受优于当前 解的状态作为下一个当前解的爬山法；接受当前解邻域中最好的解作为下一个当前解的 最陡下降法等。 b ) 指导性搜索法。利用一些指导规则来指导整个解空间中优良解的探索，如模拟退 火、遗传算法和禁忌搜索等。 ( 4 ) 基于系统动态演化的方法。将优化过程转化为系统动态的演化过程，基于系 统动态的演化来实现优化，如神经网络和混沌搜索等。， ( 5 ) + 混合型算法。峙宣上述各棘算法丛结构蘑操作生相掘命而彦生的各类算法。 、 ；_ “ 、 一般而言，局部搜索就是基于贪婪思想利用邻域函数进行搜索，若找到一个比现有 值更优的解就弃前者而取后者。但是，它一般只可以得到“局部极小解”，我们以一只 兔子登山作比喻，就是说，可能这只兔子登“登泰山而小天下”，但是却没有找到珠穆 朗玛峰。而模拟退火，遗传算法，禁忌搜索，神经网络等从不同的角度和策略实现了改 进，取得较好的“全局最小解”。 第二章智能优化算简介 2 2 遗传算法 遗传算法( g e n e t i ca l g o r i t h m ，g a ) 这个概念是由h o l l a n d 教授在2 0 世纪7 0 年 代初期首先提出并使其发展起来的。 “物竞天择，适者生存”，是进化论的基本思想。遗传算法就是模拟自然界想做的 事。遗传算法可以很好地用于优化问题，若把它看作对自然过程高度理想化的模拟，更 能显出它本身的优雅虽然生存竞争是残酷的。遗传算法以一种群体中的所有个体为 对象，并利用随机化技术指导对一个被编码的参数空间进行高效搜索。其中，选择、交 叉和变异构成了遗传算法的遗传操作；参数编码、初始群体的设定、适应度函数的设计、 遗传操作设计、控制参数设定五个要素组成了遗传算法的核心内容。作为一种新的全局 优化搜索算法，遗传算法以其简单通用、健壮性强、适于并行处理以及高效、实用等显 著特点，在各个领域得到了广泛应用，取得了良好效果，并逐渐成为重要的智能算法之 遗传算法的流程如图2 1 所示： 图2 1 标准遗传算法的流程图 第二章智能优化算简介 遗传算法的伪码： p r o c e d u r eg e n e t i ca l g o r i t h m b e g i n i n i t i a l i z eag r o u pa n de v a l u a t et h ef i t n e s sv a l u e ： w h il en o tc o n v e r g e n t b e g i n s e l e c t ： i fr a n d o m o ，1 ( p ct h e n c r 0 s s o v e r ： i fr a n d o m ( 0 ，1 ) ( p mt h e n m u t a t i o n ： e n d ： e n d ： 上述程序中有五个重要的环节： ( 1 ) ( 2 ) ( 3 ) ( 4 ) ( 5 ) ( 1 ) 编码和初始群体的生成：g a 在进行搜索之前先将解空间的解数据表示成遗传 空间的基因型串结构数据，这些串结构数据的不同组合便构成了不同的点。然后随机产 生n 个初始串结构数据，每个串结构数据称为一个个体，n 个个体构成了一个群体。g a 以这n 个串结构数据作为初始点开始迭代。比如，旅行商问题中，可以把商人走过的路 径进行编码，也可以对整个图矩阵进行编码。编码方式依赖于问题怎样描述比较好解决。 初始群体也应该选取适当，如果选取的过小则交叉优势不明显，算法性能很差，群体选 取太大则计算量太大。 ( 2 ) 检查算法收敛准则是否满足，控制算法是否结束。可以采用判断与最优解的 适配度或者定一个迭代次数来达到。 ( 3 ) 适应性值评估检测和选择：适应性函数表明个体或解的优劣性，在程序的开 始也应该评价适应性，以便和以后的做比较。不同的问题，适应性函数的定义方式也不 同。根据适应性的好坏，进行选择。选择的目的是为了从当前群体中选出优良的个体， 使它们有机会作为父代为下一代繁殖子孙。遗传算法通过选择过程体现这一思想，进行 选择的原则是适应性强的个体为下一代贡献一个