（计算机软件与理论专业论文）基于遗传算法的港口船舶调度优化问题研究.pdfVIP

上海海事大学硕士学位论文 摘要 随着经济的迅猛发展和港口经营体制的转变，港口在推动我国经济发展战略中的 作用日益明显。港口调度是港口生产管理的重要内容，其主要工作包括船舶调度、机 械调度、人员调度、堆场调度( 集装箱堆场和散杂货堆场) 、拖轮调度、引航员调度 等。港口船舶调度是其工作关键，做好港口船舶调度工作直接关系到港口能否有效利 用其资源并发挥其潜能。港口调度模型和先进调度算法的研究已经成为港口研究的一 大热点。 本文在泊位调度模型基础上，增加船舶装载货类、装载货物吨位以及泊位机械配 置等港口调度实际中的重要因素，把一般的静态船舶作业时间变为动态船舶作业时 间；通过对单纯船舶在港时间加权的方式，引入了更为符合港口调度实际的大船优先 策略，把船舶在港时间由简单加和改进为加权和，建立了基于动态船舶作业时间和船 舶加权在港时间的船舶调度模型。 针对所提出的模型，利用基于整数编码的遗传算法实现船舶调度优化，并设计了 新的基于滑动窗口的两点交叉算子，在一定程度上提高了遗传算法的执行效率，得到 了较为满意的船舶调度模型近似最优解，并在演示程序中实现了最终调度结果的可视 化，提高了实验结论的可靠性。 关键字：船舶调度、动态作业时间、加权在港时问、遗传算法、滑动窗口 上海海事大学硕士学位论文 a b s t r a c t w i t ht h er a p i dd e v e l o p m e n to ft h ee c o n o m ya n dc h a n g eo fp o r tm a n a g e m e n t s y s t e m 。t h ep o r tp l a y sa ni n c r e a s i n gi m p o r t a n tr o l ei nt h es t r a t e g yo fp r o m o t i n gt h e e c o n o m i cd e v e l o p m e n t p o r ts c h e d u l i n gi sa ni m p o r t a n tp a r to fp o r tp r o d u c t i o n m a n a g e m e n t i t sm a i nt a s k si n c l u d es h i p p i n gs c h e d u l i n g ，m a c h i n es c h e d u l i n g ， h u m a ns c h e d u l i n g ，p i l ef i e l ds c h e d u l i n g ( c o n t a i n e rp i l ef i e l da n dc o m el o o s e g r o c e d e sp i l ef i e l d ) ，t u g b o a ts c h e d u l i n g ，p i l o ts c h e d u l i n g ，e t c p o r ts h i p p i n g s c h e d u l i n gi sak e yw o r ko fi t s h i p p i n gs c h e d u l i n gi sd i r e c t l yr e l a t i v et ow h e t h e rt h e p o r tc a nm a k eu s eo ft h er e s o u r c ea n di t sp o t e n t i a le f f e c t i v e l y t h es t u d yo fp o r t s c h e d u l i n gm o d e la n da d v a n c e ds c h e d u l i n ga l g o r i t h mh a sa l r e a d yb e c o m eag r e a t f o c u so fp o r ts t u d y ， o nt h eb a s i so fb e r t hs c h e d u l i n gm o d e l ，c o n s i d e r i n gk i n d sa n dt o n n a g e so f c a r g oa n dm a c h i n ed e p l o y m e n t ，c h a n g i n gn o r m a ls h i p p i n gj o bt i m ei n t od y n a m i c s h i p p i n gj o bt i m e ，w e i g h t i n gs h i p p i n gt i m ea n da p p l y i n gt h es t r a t e g yo fb i gs h i p p i n g f i r s t ，t h i sp a p e rp r o p o s e dad y n a m i cs h i p p i n gj o bt i m ea n ds h i p p i n gw e i g h t e dt i m e i np o r tb a s e ds h i p p i n gs c h e d u l i n gm o d e l a i m i n g a tt h e p r o p o s e dm o d e l ，t h i sp a p e rr e a l i z e ds h i p p i n gs c h e d u l i n g o p t i m i z a t i o nb ya p p l y i n gt h eg e n e t i ca l g o r i t h mb a s e do ni n t e g e rc o d e ，a n d d e s i g n e dak i n do fn e wc r o s so p e r a t o ro nt h eb a s i so fs l i p p i n gt w op o i n t si nt h e w i n d o w s ，w h i c hi m p r o v e de x e c u t i o ne f f i c i e n c yo fg e n e t i c a l g o d t h m ，g o t a p p r o x i m a t eo p t i m a ls o l u t i o n ，r e a l i z e dt h ef i n a ls c h e d u l i n gr e s u l tv i s u a l l ya n d i m p r o v e dt h ed e p e n d a b i l i t yo ft h ee x p e r i m e n tr e s u l t s w a n gz h o n g - h u a ( c o m p u t e rs o f t w a r e & t h e o r y ) d i r e c t e db yp f g a om a o - t i n g k e y w o r d s ：s h i p p i n gs c h e d u l i n g ，d y n a m i cj o b1 3 m e 。w e i g h t e dt i m ei np o r t ， g e n e t i ca l g o r i t h m ，s l i p p i n gw i n d o w 论文独创性声明 本论文是我个人在导师指导下进行的研究工作及取得的研究成果。 论文中除了特别加以标注和致谢的地方外，不包含其他人或其他机构已 经发表或撰写过的研究成果。其他同志对本研究的启发和所做的贡献均 已在论文中作了明确的声明并表示了谢意。 作者签名： 谶坦i ! i 论文使用授权声明 本人同意上海海事大学有关保留、使用学位论文的规定，即：学校 有权保留送交论文复印件，允许论文被查阅和借阅；学校可以上网公布 论文的全部或部分内容，也可以采用影印、缩印或者其他复印手段保留 论文。保密的论文在解密后遵守此规定。 作者签名：导师签名 弘- j 期：垃夕群 上海海事大学硕士学位论文 第1 章绪论 1 1 港口调度研究的对象、目的及意义 2 0 0 6 年，全球3 0 大集装箱港口吞吐量全面大幅上升，其中中国港口的表现 尤其亮眼，面对世界港口己成亚洲港口天下的格局，中国港口在未来还将大有作 为。据国际集装箱化杂志2 0 0 7 年3 月份的报道：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 。 人们普遍认为，由于中国经济态势持续强劲，集装箱贸易出口量有增无减， 预计2 0 0 7 年全球港口集装箱吞吐量将继续大增，尤其是中国上海洋山深水港区、 青岛港、天津港、宁波港和广州港，增长幅度将大于往年。在全球集装箱港口排 名表中，从2 0 0 5 年第1 3 位提升到2 0 0 6 年第1 1 位的青岛港、从2 0 0 5 年第1 5 位 提升到2 0 0 6 年第1 3 位的宁波港、从2 0 0 5 年第1 8 位提升到2 0 0 6 年第1 5 位的广 州港等中国集装箱港口2 0 0 7 年和2 0 0 8 年集装箱吞吐量将有大幅度增长，预计中 国港口2 0 1 0 年集装箱吞吐量在全球排名表前3 0 位集装箱港口吞吐总量中的份额 将扩大到4 0 l “。 由以上数据可见，港口在我国国民经济和交通运输业的发展中正在发挥着越 来越重要的作用。我国大型港口在城市经济发展和腹地区域经济发展中的地位和 作用也越来越突出，已经基本上形成了以上海港和宁波港为中心的长三角区域港 口群，以深圳港和广州港为中心的珠三角区域港口群，以及以天津港和大连港为 中心的环渤海区域港口群。中国港口在带动腹地经济资源开发利用的同时，三大 区域港口内部以及与其它沿海港口之间的竞争正在进一步加剧。从国际国内经济 发展形式看，随着我国经济结构的调整、西部大开发战略的实施和加入w t o ， 我国的海运量预计将以每年8 一l o 的速度递增，港口在整个国民经济中的重 要战略地位将得到进一步的提升。 随着世界贸易的增长和航运技术的发展，运输船舶呈现大型化的发展趋势， 特别是在大宗货物的运输上，越来越多采用大型船舶，随着我国加入w t o ，港 口市场不断开放，航运市场竞争会更加激烈。对很多大型港口来说，随着深水航 上海海事大学硕士学位论文 道、码头扩建和改造，面对到港船舶的大型化和数量的不断增加，港口调度是否 有效合理、是否能保证进出港船舶的安全，直接影响到港口的竞争力、经济效益 和社会效益n 8 堋。 、 1 1 1 研究对象 港口，自古就是沿海城市经济发展最重要的依托，而泊位和作业机械则是港 口最宝贵的资源。泊位和作业机械等港口资源利用是否充分有效不仅直接影响到 整个港口的发展，而且会影响到整个城市乃至整个区域经济的发展进程。资源总 是有限的，特别是在中国经济快速发展的过程中，各类资源都出现相对短缺的情 况下，有效地管理调度有限的泊位和机械满足日益增长的码头装卸和运输需要， 对港口生产的顺利进行就显得尤为重要。 本文以港口拥有的泊位及相应泊位上配置的机械为主要研究对象，并在建立 的数学模型中考虑了停靠港口进行装卸作业的船舶特点及其到港信息。由于操作 人员和作业机械一般按照一定的比例配备，一旦确定机械的调度方案就容易对入 力资源进行安排，因此本文建立的船舶调度参考模型未对港口作业人员进行考 虑，而是仅以码头稀缺资源，即泊位以及相应泊位上配置的装卸机械，为主要研 究对象。 1 1 。2 研究目的 港口调度研究是为了进一步优化港口调度过程，促进港口资源的优化利用， 提高港口作业效率和资源利用率。本文全面分析了港口调度涉及的多个方面之间 的关系，在深入分析的基础上将港口调度分解为五个部分，着重选择其中最重要 的泊位调度为切入点开始研究，并适当考虑机械调度等资源配置参数，结合港口 到达船舶的有关特性( 如船舶装载货物吨位、船舶所装货类的装卸效率) 及其到 港的随机性特征，对码头优化调度理论进行了较为深入的研究。 7 在泊位调度模型的基础上，本文尽可能多地考虑实际调度情况，构建了一个 船舶调度参考模型，并以本模型的运算结果作为码头船舶调度的参考方案。之所 以称其为参考模型，在于该模型也尚未对港口实际情况全部考虑，因此也不可避 免地仍带有“理想化”的特征，与前有模型所不同的是该模型考虑了更多码头实 际条件，更为贴近港口的实际情况，因而对港口调度也具有更大的参考意义。此 外，本文对建立的参考模型用m a u a b 进行了仿真实现，利用遗传算法求出了本 参考模型的近似最优值，在某种程度上达到了可指导实际调度生产的目的。 2 上海海事大学硕士学位论文 1 1 3 研究意义 生产调度部是港口最为核心的部门，在港口调度具体作业中，港口船舶调度 需要考虑到泊位的适应性、堆场的容量、拖轮和引航员的调度、机械和人员的调 度、船舶到港时问、货物特性( 如时效性货物优先、军事物资优先) 等诸多因素。 因为需要考虑的因素太多，船舶调度与机械使用的随机性比较大，人的主观因素 对船舶调度的影响很大。目前，国内大多数港口还是根据调度员的经验判断来安 排船舶调度作业，没有进行科学的调度决策过程，缺乏合理的调度管理依据，对 港口调度安排的权威性形成了冲击，导致了资源浪费，生产能力不能得到充分的 释放，给生产带来了不利。因而，港口装卸的经营成本比较高，港口资源的利用 率较低，最终导致了港口竞争力不强1 4 j 。 因此，经济、合理地管理和使用港口泊位、堆场及机械等港口稀缺资源，有 利于充分发挥港口的生产潜力，提高资源利用率，降低装卸成本，对提高企业经 营效率和经济效益，适应市场竞争的要求，具有非常重要的意义 1 。2 港口调度的研究及应用现状 目前，国内大型港口集团的调度一般分为两级，一级调度是集团总部的生产 调度部，集团总调通过每天的调度会议对当天2 4 小时的船舶作业做出调度计划， 然后各港务公司二级调度部门则根据集团总调的调度计划制定出本公司当天的 昼夜作业计划及工班作业计划。无论是一级调度还是二级调度，调度部门都是港 口生产的指挥中心，调度室承担了港口每旬每日乃至每班的船舶计划、火车计划、 堆场计划等工作，并协调货主、机械、劳务等部门的作业组织p ”。 港口调度问题主要包括船舶调度、机械调度、人员调度、堆场调度( 集装箱 堆场和散杂货堆场) 、拖轮调度、引航员调度等p s i 。目前，除了集装箱堆场的调 度和管理已经存在比较成熟的软件产品外，国内绝大部分港口的港口调度工作基 本上还停留于依靠调度人员经验进行管理的水平，调度管理水平比较落后，对人 的依赖性太强，对先进调度思想和软件存在较大需求。 随着我国经济水平的迅猛发展，港口在推动我国经济发展战略中的作用日益 明显。特别是随着计算机技术，尤其是数据库技术的发展和不断成熟，企业资源 计划( e r p ) 的推广，使得各港口企业成功实施计算机科学管理和调度有了理论上、 技术上的保证。近年来，青岛港、天津港、大连港以及广州港等国内大型港口在 实施港口信息化的过程中，都先后与相关单位合作，对港口调度问题开展了一系 上海海事大学硕士学位论文 列研究，取得了比较显著的研究和应用成果。 以下是国内部分重要港口的调度指挥系统应用现状 s - 3 a l ： 1 2 1 青岛港 随着港口生产的不断发展，青岛港通过资源整合、优化管理流程，以信息化 实现了对港口业务流程的改造。通过2 0 0 3 年实旌的集成可视化港口生产指挥 系统项目，青岛港运用现代先进信息技术，创新港口管理手段，在国内港口率 先实现了生产调度、引航调度，拖轮调度的“三调合一”，实现了信息资源共享 利用，建立起具有港口生产组织、船舶引航、拖轮调度、作业监控等业务管理功 能和数字化、图形化、可视化的集成信息应用系统为一体的集团生产调度指挥中 心，已经达到世界一流国际大港的先进管理水平，为生产组织调度、船舶引航等 方面的管理提供了及时有效的技术手段，为集团的生产管理和船舶引航装上了 “千里眼”和“顺风耳”。 1 ，2 2 天津港 天津港( 集团) 调度指挥中心总投资约3 0 0 0 万元，于2 0 0 5 年1 2 月2 6 日建 成并投入使用。该中心将船舶调度，拖轮和引航调度以及港内交通指挥等功能整 合，实现了港口现代化管理水平的飞跃。该调度指挥中心内主要分为中央控制区、 视频会议区和办公区。 天津港调度指挥中心是以天津港生产调度系统为基础，运用现场视频监控系 统、船舶交通管理系统( v t s ) 、船舶自动识别系统( a i s ) 、全球定位系统( g p s ) 、 货场图形化管理系统、智能交通系统( 玎 s ) 、视频会议系统等现代化手段，对航 道、泊位、库场、道路进行信息识别和视频监控，达到优化港口资源配置、实现 港口生产集中指挥的目的，从而保证港口生产安全、科学、高效、有序进行。 该调度指挥中心的天津港生产调度系统采用客户服务器模式，数据集中管 理，保证数据充分共享。现场视频监控系统能够直观、便捷、翔实地反映港口生 产的视频信号，充分利用港口资源实现调度指挥的监控管理。船舶交通管理系统 实现对进出港船舶船名、船号、吨位等静态信息进行识别；实现对进出港船舶航 向、航速、位置及相对方位等动态信息进行识别。船舶自动识别系统能够准确定 位船舶位置和掌握航行情况，结合船舶交通管理系统，全面实现对港口海域船舶 全方位、多层次、及时准确的图形化管理和监控。全球定位系统在天津港目前主 要应用于港作拖轮的监控，用图形化手段，高精度、全天候、高效率地掌握拖轮 4 上海海事大学硕士学位论文 位置和航行情况，提高港作拖轮作业效率。另外，货场图形化管理系统、智能交 通系统、视频会议系统等也充分体现了该中心的先进性、安全性、可靠性等多种 功能。 1 2 3 大连港 为了适应港口生产形势的需要，保证各专业化公司的生产作业、安全质量以 及突发事件进行全面、有效的管控，大连港集团于2 0 0 5 年启动了可视化管理系 统工程。2 0 0 6 年年底，该工程生产调度指挥中心建设已全面动工。 根据大连港生产管理实际，2 0 0 5 年1 0 月，大连港集团开始编制可视化管理 系统工程可行性研究报告并立项。按照大连港集团信息化小组会议安排及各单位 的可视化需求，大连港集团各单位和部门及试点单位共同进行了研讨，并通过广 泛的调研，由项目实旌单位大连港通信公司、大连港隆科技有限公司分别对可视 化管理系统的软硬件建设进行了设计。 可视化管理系统内部软件由大连港隆科技自主研发，集成了现场监控的 c c t v 画面系统、弓l 航和拖轮的船舶识别系统a i s 、g p s 信号系统、海事局的船舶 交通管理系统、自动调度控制台系统、屏幕墙显示系统和视频会议系统。系统充 分考虑到目前的现状及未来业务扩展的需求，采用开放式体系结构设计，以大连 港集团企业网络作为信息传输通道，以大连港集团可视化系统管理平台为核心服 务，可以通过对各视频监控多媒体集成系统，为大连港集团、二级单位用户提供 多视角、多媒体、多功能、多应用的综合视频监控方案。同时，该系统还将逐步 整合信息系统的各项功能，通过结合现有信息化应用系统，最大化地利用监控资 源信息，为大连港集团的生产、安全管理等搭建服务平台。 由于港区覆盖面大，监控点位多，针对目前大连港集团对于可视化管理的要 求及各单位配备设施应用现状，该系统在实施过程中将采取统一规划、数字组网、 分步实施、逐步完善的方法，推进可视化管理在大连港的应用。据了解，前期实 施范围主要试点部门、单位有大连港集团业务部、大连港油品码头公司新港作业 区、大连港铁路公司大窑湾分公司、大连港杂货码头公司大连湾作业区。 1 2 4 广州港 2 0 0 6 年1 2 月3 1 日，广州港引航站正式挂牌成立，与引航管理体制改革配 套的广州港通讯调度指挥中心( 直属广州港务局) 也已于2 0 0 7 年4 月1 日正式 开始运作。为了保障广州港出海航道的正常运输秩序和安全生产，通信调度必须 上海海事大学硕士学位论文 集中统一，广州港为此正筹备建立覆盖整个港区水域的船舶通讯调度引航指挥监 控体系。通讯调度指挥中心建立后将每日发布广州港出海航道进出船舶总计划， 计划包括所有广州港集团和非广州港集团所有的码头作业情况。 今后，在广州港出海航道水域运行的任何船舶和水上设施，包括在出海航道 航行、迸港顺序的安排；锚地使用的申请和安排：船舶遇紧急情况所采取的应急 措施；灾害性天气的防范与抗御时的行动，都必须在广州港务管理机构通讯调度 指挥中心的统一指挥下进行。广州港通讯调度指挥中心将对全港船舶进出港统一 指挥、统一管理、统一引航，实现广州港航道、引航、锚地和通讯调度管理“四 统一”的目标，以确保船舶航行安全，提高港日集疏运效率。这对提高引航效率 和服务水平，进一步增强广州港综合竞争力具有重要意义。 1 3 本文研究背景及创新点 1 3 1 广州港集团简介 广州港是我国沿海主要港口和国家综合运输体系的重要枢纽，是华南地区综 合性主枢纽港。广州港是广州市拓展城市功能、调整产业结构、发展重化工业的 重要依托，是珠江三角洲地区进一步扩大对外开放、加快外向型经济发展的重要 战略资源，是广东省能源物资、重要原材料和外贸物资的主要中转港，是广东省 及华南和华中地区广泛连接国际市场、全面参与国际经济竞争与合作的重要支 撑。在地区和腹地经济持续快速发展的推动下，广州港货物吞吐量持续增长。1 9 9 9 年全港货物吞吐量突破1 亿吨，成为中国大陆第二个跨入世界亿吨大港的港口。 之后，港口发展一年一大步，到2 0 0 5 年吞吐量达到2 5 亿吨，全港集装箱吞吐 量4 6 8 万标准箱，港口货物吞吐量居全国沿海港口第3 位，世界十大港前列。 广州港集团有限公司是广州港的主体，是2 0 0 4 年2 月2 6 日经广州市人民政 府批准，由原广州港务局依法按照现代企业制度的要求改制而成立的具有法人资 格的国有独资有限责任公司。 广州港集团有限公司主要从事石油、煤炭、粮食、化肥，钢材、矿石、集装 箱、汽车等货物装卸( 包括码头、锚地过驳) 和仓储、货物保税业务以及国内外 货物代理和船舶代理；代办中转、代理客运；国内外船舶进出港引航、水路货物 和旅客运输、物流服务，兼营港口相关业务。 2 0 ( 5 年广州港集团货物吞吐量1 5 9 亿吨，集装箱吞吐量3 1 5 6 万标准箱。 广州港集团现有万吨级以上泊位3 9 个；万吨级以上装卸作业浮筒1 3 个；万吨级 6 上海海事大学硕士学位论文 装卸锚地2 3 个( 其中最大锚泊能力3 0 万吨) 。 广州港集团码头泊位主要分布在5 个大型港区：从南到北依次为珠江口水 域、南沙港区( 含小虎作业区) 、新沙港区、黄埔港区和广州内港区。 ( 1 ) 珠江口水域：以水上过驳作业为主，目前主要从事大型船舶过驳作业 和企业专用或区域性货物装卸。 ( 2 ) 南沙港区( 含小虎作业区) ：以外贸集装箱运输为主，兼顾大宗散货运 输，小虎岛作业区专门从事油品、液体化工品运输。 ( 3 ) 新沙港区：是目前集团公司的核心港区之一，主要从事集装箱、煤炭、 铁矿石、粮食、化肥、汽车和件杂货等货物装卸和中转运输。 ( 4 ) 黄埔港区：由新港和老港区两部分组成，新港区是目前集团公司的核 心港区之一，主要从事集装箱、粮食、件杂货、食用油、煤炭等物资运输；老港 区主要以件杂货运输为主，同时兼顾部分内贸集装箱和外贸集装箱驳船员支线运 输； ( 5 ) 广州内港区：以内外贸小型船舶经营为主，以外贸集装箱驳船支线和 小型内贸集装箱船舶运输为主，目前功能正在调整。 1 3 2 研究背景 本文的研究是以导师的广州港集团管理信息系统系统分析与设计项目为 背景展开的。该项目为北京交通大学与上海海事大学合作研究课题，项目的主要 任务有三个，一是编制广州港集团2 0 0 7 2 0 1 5 年信息化规划，二是完成广 州港集团管理信息系统的概要设计，三是完成广州港集团生产业务管理系统 的详细设计。 在课题调研过程中，通过与码头工作人员座谈，参观码头设施设备及现场作 业情况，参观现有计算机控制及管理系统的演示，查阅并收集港口调度日志、昼 夜船舶作业计划、工班作业计划、作业票、出入库单、装卸货凭单、货物分票手 册、船舶资料、费用结算清单等所有港口文档，下发岗位调查材料，整理港口业 务流程及数据流程图，撰写调研报告等活动，充分熟悉并了解了港口作业过程及 业务流程，为毕业设计的顺利开展和毕业论文的撰写打下了坚实的基础。 本文的撰写正是在这些工作的基础上进行的，在一方面对研究生就读期间从 事的港口信息化相关部分的工作进行总结的同时，另一方面对港口生产的核心问 题即港口船舶调度问题进行了分析探讨。 7 上海海事大学硕士学位论文 1 3 3 研究方法 本文在研究过程中注重多种研究方法的实验比较，无论是遗传算子的选择、 程序实现的细节还是参数的设定，大都经过了多次运行试验才给予确定，以期获 得较好的研究效果。 1 、模拟试验研究方法：论文中提出的模型和算法都经过了相应的模拟试验， 并且在多次实验结果的基础上进行了分析验证，保证了模型和算法的合理性。 2 、理论研究与实证研究相结合：本文采用理论分析和实际应用研究相结合 的方法，在对现有港口系统及生产过程调研和分析的基础上，建立问题的数学模 型、并设计相应求解算法，对提出的模型和设计的算法进行程序实现，实现了最 终实验结果的可视化，保证了实验结论的可靠性。 3 、本文模型和算法模拟试验过程中用到了较多的数据参数( 船舶到港及配 载信息参数表、泊位机械配置信息参数表、不同货类装卸效率参数表以及遗传算 法中涉及的选择概率、交叉概率和变异概率等) ，这些数据均来源于实际调研和 相关文献报道，并经过多次试验给予验证，与实际情况接近，保证了分析结果的 有效性。 1 3 4 本文组织结构与创新点 本文组织结构安排如下，第一章主要对港口调度问题研究的对象、目的及意 义进行了阐述，并分析了港口调度的研究及应用现状，指出了研究背景、研究方 法和创新点；第二章主要对港口调度相关问题进行了分析，对其中的港口船舶调 度问题进行了重点描述，并建立了船舶调度参考模型；第三章对一般优化方法作 了简单介绍和比较，重点介绍了遗传算法的基本概念和理论；第四章对建立的船 舶调度参考模型用遗传算法进行了设计实现，并对实验结果作了分析；第五章总 结全文，对后续研究进行了展望。 本文研究的主要创新点如下。 1 、在现有泊位调度模型的基础上，通过考虑船舶装载货类、装载货物吨位 以及泊位机械配置等港1 3 实际调度中必须考虑的重要因素，把一般的静态船舶作 业时间变为动态船舶作业时间；通过对单纯船舶在港时间加权的方式，引入了更 为符合港口调度实际的大船优先策略，把一般的所有船舶在港时间变换为所有船 舶加权在港时间，把狭义的船舶在港时间目标函数变为广义上的船舶在港时间目 标函数，建立了更为贴近港口实际的船舶调度参考模型，从而能够更为有效的指 8 上海海事大学硕士学位论文 导港口船舶调度作业。 2 、对建立的船舶调度参考模型，利用基于整数编码的遗传算法予以实现， 并设计了新的交叉算子基于滑动窗口的两点交叉算子，在一定程度上提高了 算法的执行效率和执行结果的优良性，得出了船舶调度近似最优解，可实际指导 港口船舶调度作业。 1 4 本章小结 本章对港口调度问题研究的对象、目的及意义进行了阐述，并分析了港口调 度的研究及应用现状，在对目前研究应用现状分析的基础上，指出了本文的研究 背景、研究方法和创新点。 9 上海海事大学硕士学位论文 2 1 港口调度问题 第2 章港口船舶调度 港口生产组织是从接待船舶开始，经过船舶装卸，再到送走船舶结束的一个 生产周期。船舶连续不断地到达，经过装卸又离去，因此，港口生产便是一个周 期接一个周期地进行下去。生产过程组织就是研究从船舶到达，在港口装卸作业， 货物在不同运输方式之间完成换装的组织过程。港口生产的组织过程实质是通过 人的思维对各种生产要素进行合理组合的过程。所谓合理的组合就是根据一定的 组织原理进行统筹安排，使港口各环节的能力与船舶流、货物流在空间上、时间 上、经济上得到统一。港口调度就是保证港口企业生产计划组织实施而进行的一 系列部署和指挥、检查和督促、协调和平衡的总称1 8 , 1 s , 2 ”。因此，从某种意义上 说，港口调度工作就是港口企业有效组织实施其生产过程的大脑和中枢。 随着我国社会主义经济体制的改革，特别是随着全球经济一体化和我国加入 w t o ，社会主义市场经济全面发展，贸易竞争日趋激烈，作为贸易运输的枢纽和 主要接力泵站，为适应航运市场的营销一体化、船舶大型化、航线主干化竞争的 需要，港口也经历着码头深水化、生产专业化、业务物流化、中转枢纽化、管理 信息化和经营效益化的转变。通过近年来港口体制改革的逐步实施，我国各大港 口已经顺利实现政企分开，形成了上海港、天津港、大连港、青岛港、广州港、 深圳港以及宁波港等为代表的大型港口集团，港口经营行为已由社会公益性向经 济效益性过渡转变。港口调度在港口生产中的地位和作用也随着主体服务角色的 转变而变化，老的调度规程的部分内容已不适应新形势下的港口生产。如何在新 形势下提高调度管理水平，发挥调度作用，是目前我国港口企业的调度管理部门 所要探索的课题【4 】。 通常，港口调度根据调度对象的不同可划分为船舶调度、堆场调度、装卸作 业机械及人员调度、集疏运工具调度等五大部分。这五部分调度的相互关联如图 二1 所示。 l o 上海海事大学硕士学位论文 图2 一l 港口调度各部分关联示意图 港口调度问题实质由以上五个子问题构成，显而易见，港口调度问题以船舶 调度为核心，堆场调度为重点的。船舶调度问题的解决效率直接关系到堆场调度、 集疏运工具的调度、装卸作业机械及人员调度、引航员及拖轮调度的顺利进行， 安排船舶调度时必须考虑其它港口资源的乖j 用及调度状况网。 2 1 1 船舶调度 船舶调度的具体任务主要包括1 3 8 ： 1 、生产计划编制 在集团总调层次，编制昼夜生产计划主要依据如下一些信息： ( 1 ) 各港口装卸分公司、控股子公司的详细生产业务动态信息，包括在港 船舶装卸动态信息、堆场货物结存信息、大型装卸设备的状态信息等； ( 2 ) 引航公司的引航员动态信息： ( 3 ) 拖轮公司的拖轮作业动态信息； ( 4 ) 船务公司的减载船舶动态信息； ( 5 ) 海事部门的船舶动态信息； ( 6 ) 气象信息。 集团生产计划编制完毕后，一般需要通过网络及时下发至各下属公司及其他 生产部门。 对于集团下属各公司的二级调度来说，其生产计划编制首先要获取集团生产 计划，其次要实现装卸公司船舶装卸计划、拖轮生产计划、引航生产计划等的信 息共享。 2 、船舶进出港调度指挥 上海海事大学硕士学位论文 船舶进出港动态信息对于港口生产调度极其重要。港口应能够共享海事部门 的v t s 、a i s 、气象相关信息，以便了解和掌握船舶到达锚地、码头的准确时间， 及时安排和调整相关生产计划。 3 、港务公司装卸作业调度指挥 港务公司装卸作业调度指挥主要依靠昼夜计划、工班计划的编制和执行来完 成。应及时提供集团生产计划、拖轮与引航生产计划、所需拖轮及引航员动态信 息、驳船配载信息、火车到达计划、检验检疫信息、气象信息等外部信息，以及 出勤机械、作业队动态信息，船舶作业情况、堆场结存动态信息、驳船报到情况 等。港务公司装卸作业调度指挥要能够尽可能及时地获得作业现场实际作业情况 的准确数据。 在船舶调度的以上具体任务中，生产计划的编制是至关重要的，编制生产计 划时主要考虑的是港口可利用资源情况。另外，由于泊位空间是码头的主要稀缺 资源，因此船舶调度中最能体现码头服务水平的问题就是泊位分配问题。 泊位分配就是对来港船舶分配合理的停靠泊位，使在一定时间内所有来港船 舶的总的在港时间最短，以提高港口营运效率，从而吸引较多船舶挂靠。因此， 泊位分配问题是船舶调度问题需要重点考虑的一个方面，甚至可以说，泊位分配 问题是船舶调度问题的子问题。 决定泊位分配的因素主要有：船舶相关信息，如：船期计划、吨位、装卸 箱量等；岸边资源情况，如：泊位数量、起吊设备配置等；其他物理条件， 如：水深、泊位长度等。理想的状态是船舶无需等待泊位，同时泊位的利用率达 到1 0 0 。显然这是不能达到的，因为来港船舶、装卸需求、装卸效率等关键性 因素都有不同程度的不均衡性和不确定性。一方面，当来港船舶较多时，船舶不 可避免地要排队等候，有可能导致船舶滞港、压船、压货等现象。如果泊位的分 配不合理，将会造成巨大的经济损失；另一方面，当来港船舶较少时，将造成泊 位的空闲。通常泊位的分配标准是：最小化船舶的等待时间、最小化泊位和相应 堆场的距离和最大化泊位和岸边起吊设备的利用率。对于这样一个复杂的多目标 问题，国际上多采用智能决策系统来进行码头泊位分配【8 船”。 在泊位分配模型和研究方法上，目前流行的方法主要分为两大类：一类就是 将码头岸线划分成若干独立的泊位来进行分配，而另一类泊位分配方法则将整个 码头岸线看作是连续的水边线，只要有满足到港船舶物理条件( 水深和长度) 限制 的位置就可以进行停泊。由于连续岸线优化分配问题较为复杂，相关的研究也比 较少。另外，还有部分研究将泊位分配问题也看作一个可同时处理多个任务的处 理机调度问题阴。 上海海事大学硕士学位论文 2 1 2 堆场调度 堆场是供装卸船舶临时堆放货物的场所，同时也是临时保管和向货主交接货 物的地方。根据堆放货物类型的不同，堆场又可分为仓库堆场和露天堆场。无论 是仓库堆场还是露天堆场，往往都需要对货物进行分区分类堆放，并按照货物的 规格尺寸，在堆场上划出分界标志线，标明号码，以便对堆放货物的管理和查找。 尽管业务模式的差异使得各种堆场的服务功能不尽相同，但所有业务功能都是在 堆场服务功能之上发展而来，因此他们的关键业务基本一致，堆场的主要业务工 作是办理货物的装卸、转运、集装箱的装拆箱、收发、交接保管、堆存、捆扎、 搬运、以及承揽货源等，此外，还受理货物的有关衡量等工作。 港口堆场通常被分为前方堆场( m a r s h a l l i n gy a r d ) 和后方堆场( c o n t a i n e ry a r d ) 两个部分。前方堆场是指在靠近码头前沿处，为加速船舶装卸作业，暂时堆放船 舶直接装卸货物的场地。其作业内容是：当船舶到港前，有计划有次序地按积载 图要求将出口货物整齐地集中堆放，卸船时将进口货物暂时堆放在码头前方，以 加速船舶装卸作业。 港口后方堆场是船舶装卸货物保管和堆存的场所，并与货主进行集疏运货物 的交接，集装箱的装拆箱操作也往往在此进行。有些港口的堆场并不分前方堆场 或后方堆场，而统称为堆场【l 蹈”。 堆场调度指港口货物堆场或仓库的安排策略，主要和港口的船舶调度及集疏 运情况相关。堆场调度主要考虑的是可用堆存容量，当接到船舶到港预报后，如 发现现有空闲堆场不足以满足到港船舶货物( 如有货物直提，则此部分货物不需 占用港口堆场) 的堆存要求，则必须加快现有堆存货物的疏港，否则只有延缓该 船的靠泊或装卸时间。而一旦延长船舶在港时间，则势必增加船舶相关费用，也 将影响到后续至0 港船舶的正常靠泊。由此可见，堆场调度是否及时有效，堆场空 间利用率的高低，直接影响到港口生产能否顺利进行1 3 s - 3 7 。 2 i 3 作业机械和人员调度 因为机械和人员存在较强的相关性，在港口企业往往按一定的比例进行配 备，所以放在一起作为一类资源给予考虑。机械主要指装卸作业过程中的起重机 械以及门吊、桥吊等设备，人员主要指操作机械的装卸作业工班人员。机械和人 员调度就是根据船舶装卸任务和装卸工艺要求等对作业机械和人员进行安排。 上海海事大学硕士学位论文 2 1 4 集琉运工具调度 集疏运是港口货物集港过程和疏运过程的简称。港口常用的集疏运工具主要 有火车、汽车及驳船等。在出口货物装船之前，往往需要先通过火车、汽车或驳 船等集疏运工具将出口货物分期分批集中到港口指定货物堆场临时存放，清点备 齐，待货物报检通关，船舶靠泊之后，方可装船出口。当货物通过各种集疏运工 具集港时，港方必须根据货物和集疏运工具的特征安排相应机械和人员负责卸货 进库。由于作业机械和人员的调度、堆场容量往往受到一定限制，所以，货物集 港计划必须纳入整个港口的工班作业计划。反之，对于港口货物疏运情况，和集 港情况类似。 由此可见，集疏运工具调度主要和船舶调度、堆场调度相关。 2 1 5 引航员及拖轮调度 对于外贸船舶及内贸大船等需要拖轮和引航员的船舶，涉及到引航员及拖轮 资源的调度安排。当引航员或拖轮未能准备就绪时，该类船舶的靠泊离泊必须等 待。引航员及拖轮调度一般和船舶调度中的大船和外贸船舶的调度相关l ”】。 从以上分析可以看出，港口调度问题的五个部分是相互联系不可分割的。以 上五方面资源的调度安排以船舶调度为主，船舶调度的效率直接影响到港口的作 业效率，但是船舶调度又受到其它四方面调度的制约，制订船舶调度方案时必须 考虑其它四类资源的使用情况。并且由于船舶到达的随机性，制订堆场调度、集 疏运工具调度、机械和人员调度以及引航员和拖轮调度方案时必须考虑资源预留 情况，以便后续船舶的装卸作业能够顺利进行。 根据港口的实际作业情况，堆场调度对制订船舶调度方案虽有影响，但是可 以根据船舶预报和现有堆场占用情况，对堆场货物制定有针对性的集疏运计划来 有效解决，所以堆场占用情况在本文建立的船舶调度参考模型中没有考虑。 另外，引航员和拖轮调度一般只有大船才有，虽然引航员和拖轮的资源占用 情况对大船调度有一定影响，但是由于这两种资源的调度在某种程度上还与船舶 引航员及驾驶员水平有关，在船舶调度参考模型中不便考虑，所以在一般泊位调 度模型及本文所建立的船舶调度参考模型中也均未考虑。 2 1 6 港口调度的原则 由于港口所拥有的泊位往往适用于不同的船型和货物的装卸，而且各泊位的 1 4 上海海事大学硕士学位论文 岸边堆场通常都有一定的容量，因此，为了获得船舶在港最小停留时间，就必须 对到港船舶情况进行分析，选择最适合的泊位为之服务。船舶泊位安排涉及等泊 船舶作业次序选择、泊位对船舶的适应性以及作业时间最短等问题。当到港船舶 频度大于船舶作业服务频度时，将发生船舶在锚地等待作业的现象。当这种情况 发生时，就有一个船舶作业顺序选择的问题。港口生产作业的特点有其特殊性， 港口调度必须树立市场竞争面前人人平等的原则，遵循已被港口、航运、贸易界 广泛认同接受的调度排船规则。 通常到港船舶进港作业次序安排遵循以下原则【4 刀： p l 、泊位适应优先原则： p 2 、时效性货物优先原则； p 3 、重点物资运输原则； p 4 、班轮或计划内运输优先原则； p 5 、支付速遣费货物优先原则； p 6 、外贸货物、远洋船舶优先原则； p 7 、先干线后支线原则； p 8 、先到先服务原则等。 一般而言，上述原则之间存在着以下优先考虑的顺序： p i p 2 p 3 p 4 p 5 p 6 p 7 p 8 ， 港口调度是港口权威的象征，也是对外服务的直接窗口。港口企业是以效益 为优先的服务企业，港口调度工作的好坏直接影响着港口企业形象，决定着港口 企业的竞争力。强调服务，体现公平，重视规范，注重合法、合理、合情的调度 排船原则，有利于形成约定成俗的市场规则，营造公正有序的港口环境和市场氛 围，维护港口形象，真正树立港口调度的信誉和权威。 2 i 7 港口调度的任务及目标 港口生产调度的基本任务是：以货物装卸为中心，掌握市场信息，编制和执 行水运生产计划，经济合理地利用船舶、港口设备能力，协调各有关部门、环节 间的生产，连续不问断地监督生产和随时调整生产中出现的不平衡，加速车、船、 货周转，高质量地完成货物装卸任务，努力为国民经济、对外贸易、人民生活和 国防建设服务。 港口调度管理目标主要有； l 、计划和组织机械进行船舶装卸作业； 上海海事大学硕士学位论文 2 、协调港内外各部门之间的联系，尽可能缩短船、货、车在港停留时间， 加速船、机周转，提高港口通过能力，扩大吞吐量。 为完成任务达到以上目标，传统的港口调度管理以调度电话会议形式指挥港 口生产，以调度日志、单船报表为载体体现调度动态管理，以电话、电报、传真、 无线高频电话为主要通讯手段的调度方式已经远远不能满足经济快速发展的要 求1 4 】。 在电子商务、网络信息技术高度发展的今天，作为港口企业的生产指挥中心， 现代港口调度管理应紧跟现代科技特别是信息技术应用发展的步伐，建立完善的 调度指挥系统，条件成熟的还要与现代港口的e d i 、p o r t i c 系统联网，充分利用智 能计算算法、计算机网络通讯及视频技术等先进科技成果，促迸港口生产和管理 的现代化发展瞄弦碉。随着世界经济一体化程度的不断加深，尤其是我国加入世 界贸易组织( w t o ) 对外开放步伐的进一步加快，国内各港口管理企业将面临更加 巨大的竞争压力，因此只有努力提高自身的科学管理水平，采用先进科学技术， 充分利用现有的各种人、财、物的资源，才有可能立足于世界范围内的高水平竞 争。 1 6 上海海事大学硕士学位论文 2 2 船舶调度模型 2 2 1 船舶调度问题描述 开始 船舶捌港搦确攫 船端剜港，锚地捧孰 等嫉嚣泊 港i1 撤姑船舶资誊 做好壤驹 卜 惫i ，袈簿作业汁划 报据堆场计划和装卸计期做好 概槭和人爨计翻、集照廷计划 港力调搜躲舶靠泊，擞嚣需要 调度引航员、拖轮辅助仔烫 港疗指挥虮城、入盟及禁琉露 z 具进行瓣舶装镩作诹 做好船黻鏖l 水，赞f l 结彝嚣端 躺瘩泊出港准备 港力调缆船舶离 f j ，嘏器篱蜃 调瘦引簸璇，拖轮辅助作照 船舶离港 结束 图2 2 港口船舶调度作业流程 在研究船舶调度问题的时，必须先弄清港口码头的装卸作业过程。港口作业 主要分