（运筹学与控制论专业论文）港口对单船作业岸桥调度研究.pdf

南开大学学位论文使用授权书 根据南开大学关于研究生学位论文收藏和利用管理办法，我校的博士、硕士学位 获得者均须向南开大学提交本人的学位论文纸质本及相应电子版。 本人完全了解南开大学有关研究生学位论文收藏和利用的管理规定。南开大学拥有在 著作权法规定范围内的学位论文使用权，p p - ( 1 ) 学位获得者必须按规定提交学位论文 ( 包括纸质印刷本及电子版) ，学校可以采用影印、缩印或其他复制手段保存研究生学位论 文，并编入南开大学博硕士学位论文全文数据库；( 2 ) 为教学和科研目的，学校可以将 公开的学位论文作为资料在图书馆等场所提供校内师生阅读，在校园网上提供论文目录检 索、文摘以及论文全文浏览、下载等免费信息服务；( 3 ) 根据教育部有关规定，南开大学向 教育部指定单位提交公开的学位论文；( 4 ) 学位论文作者授权学校向中国科技信息研究所和 中国学术期刊( 光盘) 电子出版杜提交规定范围的学位论文及其电子版并收入相应学位论文 数据库，通过其相关网站对外进行信息服务。同时本人保留在其他媒体发表论文的权利。 非公开学位论文，保密期限内不向外提交和提供服务，解密后提交和服务同公开论文。 论文电子版提交至校图书馆网站：h t t p ：2 0 2 1 1 3 2 0 1 6 1 ：8 0 0 1 i n d e x h t m 。 本人承诺：本人的学位论文是在南开大学学习期间创作完成的作品，并已通过论文答 辩；提交的学位论文电子版与纸质本论文的内容一致，如因不同造成不良后果由本人自负。 本人同意遵守上述规定。本授权书签署一式两份，由研究生院和图书馆留存。 作者暨授权人签字：割艳埋 2 0 1 0 年6 uu月2 日十，丁二u 南开大学研究生学位论文作者信息 论文题目港口对单船作业岸桥调度研究 姓名 刘艳娜学号 2 1 2 0 0 7 0 1 6 6 答辩日期2 0 1 0 年5 月2 4 日 论文类别博士口学历硕士硕士专业学位口高校教师口同等学力硕士口 院系所信息技术科学学院 专业 运筹学与控制论 联系电话 1 3 3 1 2 1 4 6 6 5 9e m a i l l i u y a n n a m a i l n a n k a i e d u c a 通信地址( 邮编) ：天津市河东区嘉华园9 - 2 - 6 0 1( 邮编：3 0 0 1 6 1 ) 备注： 是否批准为非公开论文 否 注：本授权书适用我校授予的所有博士、硕士的学位论文。由作者填写( 一式两份) 签字后交校图书 馆，非公开学位论文须附南开大学研究生申请非公开学位论文审批表。 i 一 南开大学学位论文使用授权书 根据南开大学关于研究生学位论文收藏和利用管理办法我校的博士、硕士学位获 得者均须向南开大学提交本人的学位论文纸质本及相应电子版。 本人完全了解南开大学有关研究生学位论文收藏和利用的管理规定。南开大学拥有在 著作权法规定范围内的学位论文使用权，即：( 1 ) 学位获得者必须按规定提交学位论文( 包 括纸质印刷本及电子版) ，学校可以采用影印、缩印或其他复制手段保存研究生学位论文， 并编入 3 0m s 主 要 起升速度 0 5m s0 6m s0 6 7m s0 8 3m s 参 数跨距 1 0 8 7 ml o m2 6 m3 0 m 外伸距2 3 7 m 3 5 m 3 7 。3 m3 6 - 4 4 m4 4 4 8 m 总重 3 5 0 t6 8 0 t7 5 0 t8 5 0 t 9 第二章码头装卸系统和岸桥调度优化算法理论 从表中可以看出来，集装箱港站装卸搬运系统趋于集成化和自动化，集装 箱装卸桥趋于大型化和高效化。以装卸桥外伸距为例，现有的装卸桥外伸距一 般为3 5 m 到3 8 m 。然而，为了接纳超巴拿马型船舶，大多数港口都必须重新订购 外伸距至少为4 4 m 的装卸桥。1 9 9 2 - - - 1 9 9 3 年首次出现外伸距为4 8 m 的装卸桥， 这是宽达1 8 行集装箱( 相当于4 5 m ) 的高级超巴拿马型集装箱船所需的最小外 伸距。随着集装箱船载箱能力和海运业务要求的提高，外伸距又增加到5 0 m ，5 2 m 以上。鹿特丹港已拥有了几台外伸距为5 6 m 的装卸桥n 羽。 2 、集装箱装卸桥的技术发展的特点 ( 1 ) 适应船舶的大型化要求的大型化集装箱装卸桥。 随着集装箱船舶的大型化，作为装卸设备的岸边式集装箱装卸桥的大型化 已成必然的趋势。对于很多港口来说，购买高效、大型的集装箱装卸桥能使港 口在竞争激烈的市场上增强竞争能力，并取得较好的投资回报。另外，通过购 置大型装卸桥除了谋求枢纽港地位外，还可以通过技术创新来提高业效。在竞 争日益激烈的市场上，高效率的港站作业对于港口争取更大的运量来说，的确 是一个至关重要的条件。许多港口越来越倾向于订购大功率、高速度的集装箱 装卸桥，由此可知，外伸距长、速度快以及起重量大是目前装卸桥发展的主要 趋势。 ( 2 ) 适应集装箱装卸高效化要求的新型装卸桥结构。 为提高集装箱装卸进度，人们提出了很多改进集装箱装卸桥的设想，并进 行了大量的研究。为进一步提高集装箱重箱速度，近年来在提高常规集装箱装 卸桥性能的同时，提出了一些有价值的设想，如双小车方式；带有可移动式过 渡吊篮的双起升式集装箱装卸桥：基础高架的多台集装箱装卸桥系统方案；桥 架可升降式集装箱装卸桥；增设提升机式集装箱装卸桥。新型的装卸桥在提高 对船舶的适应性以及生产效率方面已获得了较好的效果，这些技术将会对未来 集装箱装卸设备的发展产生影响u 引。 岸边集装箱装卸桥是港口装卸作业的关键设备，岸桥作业效率的高低将直 接影响港口的正常运转与否。本文从港口装卸作业的“瓶颈 集装箱装卸 桥进行研究，对于到港的一条集装箱船在给定岸桥数目的情况下，从港口实际 操作出发，考虑港口作业的随机性、动态性等特点，建立岸桥调度的不确定规 划模型，确定岸桥作业的顺序，减少船舶在港滞留时间。希望通过提高装卸桥 的作业效率进而提高港口的效率和其经济效益。 1 0 第二章码头装卸系统和岸桥调度优化算法理论 2 2 2 集装箱码头装卸工艺 集装箱装卸工艺，涉及集装箱作业中的装卸方法和所配备的集装箱装卸设 备。根据作业场所、条件、对象的不同，配备适量不同类型的装卸设备和作业 人数，采用正确的作业方法，才能达到快速装卸集装箱的目的。 我国集装箱码头装卸工艺方式比较单一，装卸桥作业绝大多数采用吊上吊 下方式。采用岸边集装箱装卸桥进行装卸作业；集装箱水平运输采用集装箱拖 挂车或集装箱跨运车；堆场作业主要采用轮胎式集装箱龙门起重机，个别码头 采用轨道式集装箱龙门起重机或跨运车。空箱作业多采用正面吊、大型叉车等 设备。下面介绍两种常用的港口装卸工艺。 1 、装卸桥龙门起重机 目前我国大多数港口采用装卸桥龙门起重机装卸工艺。码头前方为装 卸船作业区域，布置集装箱装卸桥装卸船作业通道，舱盖板堆放及临时堆箱区 域，以及泊位之间的联系通道。集装箱一般平行于码头岸线堆放，后方堆场为 轮胎龙门起重机或轨道龙门起重机作业区。出口集装箱按轻重箱分别堆放在前 方堆场，进口集装箱按货票堆放在后方堆场。该装卸工艺的优点是：单位面积 堆存量大；堆场面积利用率高；营运费用低；易于实现自动化控制等。其缺点 主要是龙门起重机作业的缺点，相对而言，轮胎式龙门起重机比轨道式龙门起 重机具有更多的优点，故目前采用较多。 2 、装卸桥一跨运车 码头前沿为装卸船作业区域，宽度为4 5 6 0 米，其中包括集装箱装卸桥跨 下用于跨运车行走和集装箱转接场地；海侧轨至码头前沿线范围，陆侧轨至前 方堆场范围。后者用于堆放舱盖板及布置泊位间的联系通道区域。该装卸工艺 的优点是机动灵活，作业范围大；港站前沿装卸船的接运采用“落地 作业方 式，装卸桥从船上卸下货物，不受等候平板车和装车对位等因素的影响，因而 提高了装卸的效率，使之成为国外应用最为普遍的集装箱装卸工艺。集装箱跨 运车在我国应用较少，目前厦门港、南京港和珠海九州港采用了跨运车方式。 该工艺的缺点是由跨运车的缺点引起的，为了客服这些缺点，要求港站场地要 平整，司机操作技术要过硬，并且注意对跨运车的维护和保养啪1 。 港口集装箱装卸工艺中，关键工序是集装箱装卸船作业。除此之外，集装 箱堆场、车辆( 汽车、火车) 以及拆装箱作业，与铁路、公路、大型货场、中 第二章码头装卸系统和岸桥调度优化算法理论 转站作业过程大致相同，所配备的装卸工艺方式及其设备大同小异。 第三节岸桥调度问题优化算法理论 2 3 1 模拟退火算法简介 模拟退火算法( 简称s a ) 是属于一种通用的随机搜索算法，是对局部搜索 算法的扩展。与一般局部搜索算法不同，模拟退火算法以一定的概率选择邻域 中目标相对较小的状态，是一种理论上的全局最优算法。它的早期思想是在1 9 5 3 年由m e t r o p o l i s 提出来的，但直到19 8 3 年由k i r k p a t r i c k 等人成功地应用在组合 最优化问题中，才真正创建了现代的模拟退火算法。由于现代的模拟退火算法 能够有效地解决具有n p 复杂性的问题，避免陷入局部最优解，克服初值依赖性、 具有渐近收敛性等优点，已在理论上被证明是一种以概率1 收敛于全局最优 解的全局优化算法。因此应用十分广泛，如生产调度、控制理论、神经网络和 图像处理等领域。 模拟退火算法的基本思想来源于固体的退火过程，当加热固体到一定温度 后，它的所有分子在状态空间自由运动。随着温度的逐渐下降，分子停留在不 同的状态，分子运动逐渐趋于有序，最后以一定的结构排列。这种由高温向低 温逐渐降温的过程称为退火。退火过程中系统的熵值不断减小，系统能量随温 度的降低趋于最小值。在退火中，需要保证系统在每一个恒定温度下都要达到 充分的热平衡，这个过程可以用m o n t e c a r l o 的方法加以模拟，该方法虽然比较 简单，但需要大量的采样才能获得比较精确地结果，计算量较大。鉴于物理系 统倾向于能量较低的状态，而热运动又妨碍它准确落回到最低态的物理形态， 采样时只需着重取那些有贡献作用的状态则可较快达到较好的结果。1 9 5 3 年， m e t r o p o l i s 等人提出了一种重要性采样法，即以概率来接受新状态。在温度t 时， 由当前状态，产生新状态j j f ，两者的能量分别为e 和e ，若巨 e ，则接受新状 态，为当前状态；否则，以一定的概率 x p 掣 旺， 来接受状态，其中k 为b o l t z m a n n 常数。这里e x p x 1 即为指数函数e j 。当这种 1 2 第二章码头装卸系统和岸桥调度优化算法理论 过程多次重复，即经过大量迁移后，系统将趋于能量较低的平衡态，各状态的 概率分布将趋于一定的正则分布。这种接受新状态的方法被称为m e t r o p o l i s 准 则，它能够大大减少采样的计算量。 对于一个典型的组合优化问题，其目标是寻找一个x 。，使得对v x , q ，有 厂( x l = m i n 厂( x il ， ( 2 2 ) 其中q = 而，x 2 ，吒 为由所有解构成的解空间，厂( 而) 为解毛对应的目标函 数值。在模拟退火算法中，优化问题中的一个解蕾及其目标函数f 薯) 分别可以 看成物理退火中物体的一个状态和能量函数，而最优解x 就是最低能量的状态。 而设定一个初始高温、基于m e t r o p o l i s 准则的搜索和控制温度参数f 的下降分别 相当于物理退火的加温、等温和冷却过程。组合优化问题的求解过程与物理退 火过程之间的对应关系如表2 2 所示。 表2 2 组合优化问题的求解过程与物理退火过程之间的对应关系 优化问题物理退火 解状态 目标函数 能量函数 最优解最低能量的状态 设定初始高温加温过程 基于m e t r o p o l i s 准则的搜索 等温过程 控制温度参数，的下降冷却过程 2 3 2 模拟退火算法的基本思想及流程 模拟退火算法是一种启发式的随机寻优算法，它的基本思想是：模拟物理 退火过程，由一个给定的初始高温开始，利用具有概率突跳性的m e t r o p o l i s 抽样 策略在解空间中随机进行搜索，伴随温度的不断下降重复抽样过程，最终得到 问题的全局最优解。 模拟退火算法描述的m e t r o p o l i s 准则既接受优化解也接受劣化解。算法开始 时f 值较大，就可能接受较差的劣质解，但随t 的减小，只会接受较好的劣化解， 最后在，值趋于零时，就不再接受劣化解了。因此，模拟退火算法能从局部最优 的陷阱中跳出来，以较大的概率获得全局最优解。 1 3 第二章码头装卸系统和岸桥调度优化算法理论 一个优化问题可以描述为 m i n f ( i ) ，f s ( 2 3 ) 其中s 是一个离散有限状态空间，i 代表状态。针对这样一个优化问题，模 拟退火算法的计算步骤： 1 、初始化，任选初始解f s ，给定初始温度r o 和终止温度l ，令迭代指标 k = o ，瓦= t o ，并计算f 点处的函数值厂( j ) ； 2 、随机产生扰动万，得到新点j = i + 8 ，计算新点的函数值厂( _ ，) 及函数差 值鲈= s ( j ) - f ( i ) ； 3 、若a s 0 ，则计算新点的接受概率 笪 p ( a f ) = e 孓， ( 2 4 ) 产生【o ，l 】区间上的均匀分布的伪随机数孝，孝【o ，l 】，若e ( a i ) 孝，则接受新点 为下一次模拟的初始点，否则放弃新点，仍取原来的点作为下一次模拟的初始 点。则令扛j ， 5 、若达到热平衡( 内循环次数大于疗( 瓦) ) 转至第6 步，否则转至第2 步。 6 、降低瓦，k = k + 1 ，若瓦 l ，则算法停止，否则转至第2 步。 根据上述计算步骤，模拟退火算法的流程图如图2 3 所示晗。 模拟退火算法用一组冷却进度表参数来控制算法的进程，使算法在控制参 数t ( 随算法进程递减) 徐徐“降温 并趋于零时，最终求得组合优化问题的相 对全局最优解。冷却进度表参数包括控制参数，的初始值f o 、衰减函数、终止准 则及m a r k o v 链长度厶，优化问题的一个解f 及其目标函数f ( i ) 分别与固体的一 个微观状态f 及其能量e 相对应。令控制参数f 担当固体退火过程中温度r 的角 色，对r 的每一个取值，采用m e t r o p o l i s 接受准则，持续进行“产生新解判 断接受或舍弃 的迭代过程，最终达到该温度下的“平衡点 c z 2 。 分析模拟退火算法的基本原理可以看出，理论上是用一个m a r k o v 链描述模 拟退火算法的变化过程，所以具有全局最优性，在具体应用模拟退火算法中发 现，它也有一些不足，主要是有许多参数需要人为调整，如起始温度、温度下 降方案、固定温度时的迭代长度、终止规则等等，这样就造成了计算结果的差 异，因而很难保证计算结果为全局最优点，这就需要通过大量的数值模拟计算 来选择好的参数。 1 4 第二章码头装卸系统和岸桥调度优化算法理论 图2 3 模拟退火算法流程图 第四节本章小结 本章首先介绍了集装箱码头的概况，重点介绍了集装箱装卸桥和与其相关 的装卸系统，为后面研究岸桥调度问题提供了一个背景知识。最后介绍了论文 要用到的模拟退火算法的基本思想、计算步骤和使用时需注意的一些问题，为 下面章节中使用模拟退火算法研究岸桥调度问题奠定了理论基础。 1 5 第三章基丁模拟退火算法的单船岸桥调度问题 第三章基于模拟退火算法的单船岸桥调度问题 第一节引言 在现代物流体系中，港口是远洋、内河航运以及内陆运输( 公路、铁路、 管道) 的重要枢纽，在国际工业品运输链上具有举足轻重的地位。现代集装箱 运输具有运输速度快、装卸方便、机械化程度高、作业效率高、便于水陆联运 等优点，自2 0 世纪5 0 年代出现以来即得到蓬勃发展。随着世界经济一体化的 加深以及跨国公司的快速成长，集装箱运输业务必将在世界经济发展中扮演着 日益重要的角色集装箱正使世界变小。进入新世纪，我国对外开放政策坚 定不移地推进，在区域经济乃至世界经济发展中逐渐体现出“龙头 拉动作用。 与港口发展伴随的是日益增长的压力。一方面，港口间对腹地货源和客户的争 夺日益激烈：另一方面，船舶的大型化、快速化对港口的基础设施和服务水平 提出了新的挑战。港口是一个资源密集型的物流节点，如何利用有限的资源提 升自己的服务水平一直是业界和研究界关注的焦点。 集装箱码头是由多种设施构成的大型复杂系统，如何将各种设施和资源有 机地组织起来，使各项作业协调通畅，形成一个完整高效的作业系统已成为目 前国内外学者研究的热点。目前国内外关于集装箱码头优化调度问题的研究可 划分为以下两种情况：一类是建立仿真模型对码头调度问题进行仿真。由于码 头生产调度系统规模庞大、结构复杂、属性及目标多样，使得其优化调度问题 具有随机性、多目标性和决策的复杂性等困难。在考虑系统不确定性与随机因 素时，常面临模型过于简化或计算过于复杂的问题。因此，利用仿真技术研究 集装箱码头优化调度问题具有指导实际操作的重要意义。另一类是建立优化模 型和运用算法求解。集装箱码头包括多个复杂的作业系统，难以用一个模型处 理整体优化问题。这一类研究通常是将码头的作业系统分为若干个环节，如泊 位的分配、岸边装卸桥的分配和调度、集卡的配置、场桥的分配和调度、堆场 堆存策略等来考虑建立优化模型，并运用智能算法对其求解。在集装箱码头的 各个子系统中，集装箱装卸桥是制约集装箱码头装卸效率的主要瓶颈，装卸桥 的作业顺序决定着码头陆域上其他装卸设备的调度，是集装箱码头作业重要的 1 6 环节。 何安排 小。最 3 2 1 集 日 顺序排 中间两 自船中向左舷边的列位号分别为0 2 、0 4 、0 6 、0 8 ，自船中至右舷边列位号分 别为0 1 、0 3 、0 5 、0 7 。后两位编号为层号，甲板和舱内全用偶数表示层号， 但开头数字不同。舱内自下而上依次用0 2 、0 4 、0 6 表示；甲板上从甲板底层 算起，往上依次用数字8 2 、8 4 、8 6 表示绷。集装箱船横截面如图3 1 所示。 贝位 蔓寸集装箱贝号 仁二；_ 厂一- 。弋 ! 装i 时集装筘贝号 美贷口一 行号引一蚋引。 ：竺苫。_ ! = 图3 1 集装箱船横截面示意图 1 7 号f屡，蘑 一 - -一-口垤皤鸥晚冒一糠h对廿幡西m 一 第三章基丁二模拟退火算法的单船岸桥调度问题 在图3 1 中，每个小方块为箱位。用行号表示横向坐标，以船舶中剖线为 基准，向右、左分别以奇数、偶数表示；用层号表示垂直坐标，舱内集装箱层 编号从舱底开始，舱上面层编号从舱面开始。当然，贝位图的表示方法不仅限 于上面提到的，在这里就不做介绍了。 通常，对于进口的集装箱，把来源港口和集装箱尺寸都相同的编为一组 ( g r o u p ) 。类似地，目的港口和尺寸都相同的出口集装箱也编为一组。出于装 卸效率的考虑，一组的集装箱在船舶上常常放在一起，即它们占用连续的箱位 空间( s l o t ) 。集装箱码头进行装卸时要制定配载图和积载图。积载图 ( s t o w a g e p l a n ) 是以船舶总截面的形式表示的图形，它显示船上货物的位置。 图3 2 是一个简单的船舶积载图心钔。 鞫 号i 圈霞冒嚣o 圈酽固翠 目圈咽目。圈目o 霭窜 图3 2 船舶积载图 图3 2 中每个小方块表示一个箱位空间，为便于管理，逻辑上将箱位空间 划分为若干个贝位( b a y ) ，图中所示有贝位1 ，贝位3 ，贝位5 ，贝位7 共4 个 贝位。阴影的区域表示这些箱区的集装箱要在该码头进行装卸；具有相同外观 的阴影方块表示其对应的集装箱属于同一个组，图3 2 中，有4 组集装箱待装， 4 组集装箱待卸。位于同一个贝位且属于同一组的集装箱，它们的装操作成为一 个任务，卸操作也成为一个任务，一个任务对应的所有集装箱成为一簇( c l u s t e r ) ， 在图3 2 中，有5 个装箱任务( 对应簇l 一簇5 ) ，5 个卸箱任务( 对应簇6 _ 1 8 ，(，l，j、，l 簇1 0 ) ； 途打断其作业，只有这个簇的集装箱全部作业完成后，别的岸桥才能移到该贝 位作业。 3 2 2 岸桥作业特点 对于到港的船舶，岸桥要为其提供装卸服务，这是集装箱码头日常生产中 最重要的作业之一，也是码头昼夜生产调度的主要内容之一，装卸作业的效率 是码头生产效率的重要指标。与普通的并行机调度问题相比，岸桥的装卸作业 有其特殊性。 第一、装卸作业的任务之间有一定的前后顺序。如，对于同一个贝位中的 多个任务，先卸甲板上的箱子、再卸船舱内的箱子、然后向船舱内装箱子，最 后装甲板上的箱子，有时为了平衡各个贝位的工作量；会增加一些额外的任务 顺序约束。 第二、有些任务不能同时进行：一个贝位在某一特定时刻，只能停靠一台 岸桥，因此，这个贝位中的诸任务不能同时被操作；由于相邻的岸桥间通常要 保持一个贝位的安全距离，两个相邻贝位中的任务不能同时进行；有时，考虑 到堆场中场桥的工作负荷和转场要求，也会要求一些任务不能同时进行。 第三、所有岸桥在同一个轨道上移动，所以一台岸桥移动时不能跨越另一 台岸桥。 制定装卸计划不但要确定每个岸桥完成哪些任务，而且须确定每个任务的 开始执行时间。表3 1 即是一个岸桥调度方案的例子。 表3 1 岸桥调度方案示例 岸桥l ( 作业时间：9 - 1 2 点)岸桥2 ( 作业时问：9 - 1 2 点) 顺簇 任务集装开始结束 顺 簇任务 集装开始结束 序号 位置位置 类型箱数时间时间 序 号类型 箱数 时间时间 161h o l dd4 79 ：0 09 ：4 7173d e c kd3 99 ：0 09 ：3 9 211h o l dl4 2 9 ：4 71 0 ：2 92 95h o l dd4 6 9 ：4 11 0 ：2 6 383h o l dd3 2 1 0 ：3 l1 l ：0 3 355h o i dl2 3 1 0 ：2 61 0 ：4 9 4 4 3h o l dl8 l l ：0 31 1 ：1 i41 0 3d e c k d 2 4 1 0 ：5 i1 1 ：1 4 533d e c kl81 1 ：1 1 1 l ：1 9 623d e c kl1 6 1 1 ：1 9儿：3 5 注：d - d is c h a r g e ，l - - l o a d 1 9 第三章基丁模拟退火算法的单船岸桥调度问题 第三节岸桥调度模型 岸桥调度的优化没有固定的目标，可以是令所有船舶延迟时间的总和最小， 或者是单船平均装卸效率最高，或者是岸桥工作平衡，还可以是岸桥利用率最经 济。在实际工作中，优化目标依赖于码头实际情况以及码头的经营目标心朝。 k i ma n dp a r k ( 2 0 0 4 ) 啪1 考虑了货物的优先权和岸桥之间的相互影响，建立 了关于单船作业岸桥调度问题的数学模型，作者提出了一种精确算法分支 定界算法。实验表明，分支定界算法在小规模问题时表现良好，但对于中等规 模和大规模问题( 岸桥数目3 且任务数目2 0 ) 无能为力。针对中等规模和大 规模问题，作者提出了一种启发式算法贪婪随机自适应搜索算法，并得到 了较好的计算结果。 m o c c i ae t a l ( 2 0 0 6 ) 啪1 在k i ma n dp a r k ( 2 0 0 4 ) 研究的基础上，深入研究了 岸桥间的相互影响，在其数学模型中加入了约束条件( 3 1 0 ) ，( 3 11 ) 和( 3 1 2 ) ( 见3 3 2 数学模型) ，且对模型中的约束条件进行了细致的变换，基于此作 者提出了又一种精确算法一分支切割算法。实验表明，作者提出的分支切割 法比分支定界法在求解质量和求解效率上有很大提高，可以作为设计启发式算 法的基准。 后来许多研究者在m o c c i ae t a l ( 2 0 0 6 ) 建立的优化模型基础上进行研究，如 s a m m a r r ae t a l ( 2 0 0 7 ) 例在前人建立的模型基础上进行了修改，把单船装卸作 业的岸桥调度问题分解为两个子问题，在此基础上设计了一种禁忌搜索算法。 s a m m a r r ae t a l ( 2 0 0 7 ) 优化模型考虑的目标函数是：使船舶能够尽快离港，即最 小化这艘船装卸作业的船舶服务时间( m a k e s p a n ) ；同时，使所有岸桥的总完 工时间达到最小：当两个调度方案的船舶服务时间( m a k e s p a n ) 都达到最小时， 如果其中的一个方案岸桥总完工时间较小，意味着在该船舶离港之前有更多的 岸桥可以为其它船舶提供服务。本章在该模型的基础上，由贪婪随机方法得到 问题的初始解，再运用模拟退火算法求最优解，以期得到好的计算结果。 考虑的约束主要有： 1 、某一特定时刻，一个贝位上只能有一台岸桥停靠作业。 2 、每台岸桥有一个最早可用时间，每台岸桥只有在此时间之后才是可用的。 3 、所用岸桥分布在同一个轨道上，岸桥之间不能相互跨越。 4 、同一个贝位中的任务之间有先后顺序：先卸甲板上的箱子、再卸船舱内 第三章基于模拟退火算法的单船岸桥调度问题 的箱子、然后往船舱内装箱子，最后装甲板上的箱子。 5 、相邻的岸桥间要保持一个贝位的安全距离，即相邻贝位的任务不能同时 进行。 6 、与第一个约束相关，值得注意的是，某个时刻，某个贝位置上的岸桥q g 作业完毕，另一个贝位曰，上的岸桥q g 恰好可以移到到贝位e 作业，这时，q q 必须等到阮移动到相邻泊位后方可开始作业。 为便于研究，我们假设岸边的岸桥从左到右依次编号为q c ，9 c 2 ，船舶 的贝位也从左到右依次编号1 ，2 ，3 ，任务和簇的编号相同。 3 3 1 符号说明 q = 1 ，2 ，刀 ：任务集合。 若定义两个虚拟任务，任务0 ：每个岸桥最先开始的任务； 任务r ：每个岸桥最后完成的任务； 因此，任务的全部集合为孬= q u o ，丁 q = 1 ，2 ，q ：岸桥集合。 岛：任务f 的作业时间，即i q ，显然风= p r = 0 ：任务f 的位置，用其所在的贝位号标识。z + 痧= 砸，j ) if ，j q ，f 必须在，之前进行 ， 吵= 形，j ) ii ，j q ，i ，师能同时进行 ， 显然，痧少。除了痧外，妒还表示相邻贝位的任务不能同时进行。 ，：岸桥七的最早可用时间。 f ：岸桥由一个贝位移动到相邻贝位的移动时间( t r a v e l i n gt i m e ) 。 ， ，= 讹- i ，1 岸桥由任务i 所在贝位移动到任务，所在贝位的移动时间。 类似地， 岛= ，阽一，l i ：岸桥七从开始位置移动到它的第一个任务j 所用的移动时间， ，各= 讹一引：岸桥七从贝位i 执行所有任务后离开此船的移动时间。 栅画嘲) - 搿旅帆黼碗觥射膝捕断脚 删删= ：霈旅札蚴桃射就插聪 2 l c f ( f f 2 ) ：任务f 的完工时间( c o m p l e t i o nt i m e ) 。 j ，( 七t 3 ) ：岸桥七的完工时间。 w ：整个调度方案的时间跨度( m a k e s p a n ) 。 3 3 2 数学模型汹1 m i n i m i z e 口1 w + 口2 y k e q y 。sw ( 七eq ) ， x 乞= 1 ( 七q ) ， j e l l x 务= 1 ( 七q ) ， j e q x ；= l ( i eq ) ， x ；一砖= o ( i eq ，k q ) ， j e f l u r j e n u o q + ， ，+ p j - c j m ( 1 一k ) ( f ，_ ，孬，k q ) ， c i + p c 。，) 咖) ， c i + p ，- - c j - m o 一乃) ( f ，j e q ) ， ”p 厂c j + 磁m ( 1 一乃) k e q e q u o 。，- c j p j c ts 地口 o ，q ) ， c 厂p 厂c j - 域 口，这里我们取口，= 0 。约束( 3 2 ) 是m a k e s p a n 的定义，整个船的 服务时间；约束( 3 3 ) ( 3 4 ) 是路径约束，每个岸桥k 从初始位置0 进入，到 最后位置丁结束；约束( 3 5 ) 表示一个任务由一台岸桥且仅由一台岸桥作业； 约束( 3 6 ) 对每一个任务每一个岸桥定义的路径约束( 出入平衡) ，保证每个 任务按照既定的顺序完成；约束( 3 7 ) 是调度方案中岸桥k 执行的前后相连的 两个任务在完成时间上的关系，避免出现子任务；约束( 3 8 ) 是优先顺序，是 技术上对任务的执行顺序的约束；约束( 3 9 ) 是两个不在同一个贝位上但时间 上有前后关系的任务须满足的约束。定义z f ，任务，在任务f 之后，z ，= 1 ，否 则为o ；约束( 3 1 0 ) 保证当( f j ) 甲时，任务f 和任务，不同时进行；约束( 3 1 1 ) 保证岸桥之间没有交叉。如果任务f 和任务同时进行并且， ，则毛+ z = 0 假设岸桥和任务的排序是按照他们沿贝位方向升序排列，即如果k 。 ，则接受新解 q c 。，q c ：k + 。作为下一次模拟的初始点进行下一次迭代；否则放弃新解，仍取 原来的解 9 c 。，q c 2 。作为下一次模拟的初始点，继续在原解的基础上产生新 解、进行判断。表3 2 是对3 7 个测试数据进行模拟得到的最优解。 2 、参数说明 下面先给出模拟退火算法中参数的取值，计算结果分析里将详细说明参数 的确定过程。 ( 1 ) 初始温度瓦的选取应满足“初始接受概率近似等于1 的条件，即 p 何) ：e 一一等1 l ， ( 3 2 4 ) 上七一， 我们取初始温度瓦= 2 0 0 0 。 ( 2 )由于温度大小决定着模拟退火算法进行广域搜索还是局域搜索。若 温度下降过快，可能造成过早地陷入局部最优状态。如果温度下降地过慢，会 增加计算时间。依照k i r k p a t r i c k 提出的降温函数：瓦+ l = a r k ，即每一步温度以 相同比率下降，其中k 0 ，a 为接近1 的常数，这里我们取降温系数a = 0 9 。 ( 3 ) 模拟退火算法的全局搜索性与每一温度的迭代长度密切相关。一般 地，同一温度下的充分搜索是必要的，但需以时间的增加为代价。m a r k o v 链是 指在某一温度水平下迭代的次数，采用固定迭代步数，即在每一温度都设置相 同的迭代步数保证算法的收敛性。这里我们取内循环次数为1 0 0 。当温度下降至 充分低时，停止迭代。 2 6 第三章基于模拟退火算法的单船岸桥调度问题 最后，得到该问题最优解为：q c 。： 2 ，1 ，5 ，9 ，6 ，q c 2 ： 3 ，7 ，1 0 ，4 ，8 ) ， 整个调度方案的时间跨度( m a k e s p a n ) 为5 9 3 。 表3 2 数据i n s t a n c e1 3 h s t a n c e4 9 计算结果( 模拟退火算法) 序号岸桥数任务数 m a k e s p a n序号 岸桥数任务数 m a k e s p a n 1 321 05 9 33 221 58 2 8 1 421 04 7 13 332 07 2 6 1 521 05 6 93 432 05 5 9 1 621 05 3 73 532 05 3 l 1 721 04 6 4 3 6 32 09 1 3 1 8 21 05 2 7 3 7 32 05 9 9 1 921 04 4 53 832 07 4 4 2 021 05 2 03 932 05 2 l 2 121 05 4 64 032 06 6 4 2 221 05 1 34 132 06 5 5 2 321 58 1 14 232 57 2 6 2 421 56 1 24 332 59 5 8 2 521 58 6 94 432 59 6 8 2 6 21 57 7 64 53 32 58 8 4 2 7 21 55 5 64 632 58 3 2 2 821 59 2 84 732 57 3 4 2 921 56 7 24 832 58 6 5 3 021 56 9 84 932 58 6 4 3 l21 59 1 4 3 4 3 计算结果分析 l 、贪婪随机方法得到的初始解具有以下特点： ( 1 ) 因为贪婪随机方法考虑了，甲中任务的约束，所以所得的调度方案 各个岸桥可以同时作业而互不影响，整个调度方案的时间跨度( m a k e s p a n ) 即 为岸桥中最大的作业时间。 第三章基于模拟退火算法的单船岸桥调度问题 ( 2 ) 因为贪婪随机方法中“贪婪的思想，所以，一般情况下，各个岸桥 最终完成的作业任务，都是在某一段贝位，没有交叉。例如i n s t a n c e1 3 中o c 所 有的任务都是在贝位1 - 3 中，q c ，所有的任务都是在贝位5 - 9 中。 ( 3 ) 贪婪随机方法计算结果可能会出现某一岸桥总的作业时间太长，整个 调度方案的时间跨度( m a k e s p a n ) 也就越长。 文献 2 4 在求解模型时使用了贪婪随机自适应搜索算法，随着贪婪算法迭 代次数的增加时，其计算结果将接近最优值。下面使用贪婪算法进行计算并与 模拟退火算法得到的结果相比较。表3 3 是由贪婪算法得到的最优解。 表3 3 数据i n s t a n c e1 3 l n s t a n c e3 2 计算结果( 贪婪算法) 序号岸桥数任务数 m a k e s p a n序号 岸桥数任务数 m a k e s p a n 1 3 21 0 5 9 33 22 1 5 7 5 2 1 4 21 0 4 7 1 3 3 3 2 0 7 2 6 1 521 05 6 93 432 05 5 7j ， 1 621 05 3 73 532 05 3 l 1 721 04 6 43 632 09 1 3 1 821 05 8 1 个3 732 05 9 9 1 921 04 4 53 832 09 3 6 2 021 05 2 03 932 05 2 1 2 121 05 4 64 032 06 6 4 2 221 05 4 5 个4 132 06 6 2 个 2 321 57 7 3 山4 23 2 57 2 8 个 2 421 56 1 24 332 59 7 6 1 2 521 58 7 1 个4 432 59 6 8 2 621 57 7 64 532 58 8 4 2 721 55 5 64 632 58 3 2 2 821 59 2 84 732 57 3 4 2 921 56 7 24 832 58 6 5 3 021 57 0 4 1 4 932 58 8 7 个 3 l21 59 4 7 个 表3 3 中“个 表示贪婪算法的结果大于模拟退火算法的结果；“上 表示 贪婪算法的结果小 由表3 3 可见， 试数据的结果比模 火算法得到的结果大：剩余的2 6 个测试数据的结果与模拟退火算法得到的结果 是相同的。 2 、贪婪随机自适应搜索算法中参数的选取 为了确定参数的取值，下面通过模拟来确定贪婪算法中的迭代次数和常数， 的值。令贪婪随机自适应算法中的迭代次数分别取1 0 ，2 0 ，5 0 ，8 0 ，1 0 0 参数，分别 取0 1 ，0 2 ，0 4 ，0 6 ，0 8 ，模拟的次数不超过以上两个参数组合数2 5 次。测试 数据取i n s t a n c e1 3 - i n s t a n c e2 0 ，迭代次数选取1 0 0 ，模拟结果如图3 3