（机械电子工程专业论文）基于遗传算法的堆场贝位分配优化问题研究.pdf

摘要 集装箱码头是专供停靠集装箱船舶，装卸集装箱的港口作业场所。在集装箱运输 过程中码头是水路和陆路运输的连接点，也是集装箱多式联运的枢纽。集装箱码头的 堆场部分可分为前方堆场和后方堆场，其主要作用是为集装箱提供临时的集中堆存。 因为集装箱码头装卸企业生产具有连续性、协作性和不平衡性等显著的特点，所以为 确保港1 3 码头的高吞吐量，保证为每一个集装箱船舶提供快速高效的服务，堆场管理 必不可少。 堆场管理包括多个方面，主要包括堆存优化和堆场机械调度等。本文研究仅限于 堆存优化方面，以一贝为对象，根据混合堆存工艺，考虑不断变化的当前堆存状态和 操作难度，为每一个动态到达的集装箱安摊位置。其目的是在装船作业期闻，在前方 堆场取箱操作过程中倒箱次数最少。该实际问题属于n p 难问题，很难用传统的优化方 法解决。文中对实际问题进行了一定程度的简化，首先针对倒箱次数建立了数学模型， 然后考虑实际作业难度，对上述模型进行了改进。最后采用遗传算法进行求解。针对 遗传算法的性质和求解过程，提出采用并行遗传策略。同时文中给出了算法所需的各 种参数的值，包括子种群数目、进化代数、遗传算子的取值及相应的编码策略。论文 最后还对不同情况下的优化结果进行了比较，对该问题的研究进行了展望并提出了进 一步研究的着眼点。 关键词：堆场；遗传算法；倒箱；堆垛位；混合堆存 c o n t a i n e rw h a l _ fi st h es p e c i a lw o r k i n gp l a c eo fh a r b o rf o rl o a d i n ga n du n l o a d i n g c o n t a i n e r s w h a r fi st h ej o i n tb e t w e e nt h eu a n s p o r to fl a n dw a ya n dw a t e r w a yi nt h ec o u r s e o fc o n t a i n e rt r a n s p o r t , a n di st h eh i n g eo fm u l t i - m o d a lt r a n s p o r tt o o c o n t a i n e ry a r di s s e p a r a t e di n t om a r s h a l l i n gy a r da n dc o n t a i n e ry a r d , w h i c hi t sm a i ne f f e c t i sp r o v i d e dt h e t e m p o r a r yp l a c et os t o r e b e c a u s et h ee n t e r p r i s e so fc o n t a i n e rw h a r fh a v es o m e 玳炯b k c h a r a c t e r ss u c ha ss u c c e s s i o n , c o n c u r r e n ta n dd i s e q u i l i b r i u m , t h em a n a g e m e n to fc o n t a i n e r y a r di sa b s o l u t e l yn e c e s s a r y s oa st ok e e ph i g ht h r o u g h p u t sa n dp r o m i s et h eq u i c ke f f i c i e n c y f o re v e r ys h i po f l o a d e da n du n l o a d e dc o n t a i n e r t h em a n a g e m e n to ff i e l di n c l u d e sm a n y 弱p c c t s i ti sm a i n l yt oo p t i m i z ec o n t a i n e r l o c a t i o ni nb a ya n ds e q u e n c eo fy a r dm a c h i n e s t h i sp a p e ri ss t u d yh o wt oo p t i m i z e c o n t a i n e rl o c a t i o nw i t ht h et e c h n o l o g yo fm i x e ds m c lv l ，l u c naw e i g h t - c o n t a i n e ra r r i v e si n t h ey a r do nr a n d o m , i ti sd e s i r et h a ts e t u pa r r a n g e m e n tt i m e si sm i n i m u mt oc o n s i d e rt h e s i t u a t i o nt os t o r ea n dt h ed e g r e eo fd i f f i c u l t y s i n c et h ep r o b l e mi sk n o w nt ob ea n p - h a r do n e i ti sv e r yd i f f i c u l tt h a ts o l v ei tb yu s i n gt r a d i t i o n a lo p t i m i z em e t h o d s i nt h i s p a p e r , t h ea u t h o rp r e d i g e s t st h eq u e s t i o ni ns o m ed e g r e ea n db u i l d s t h em o d e lf o rt h e m i n i m u mo fs e t u pa r r a n g e m e n tt i m e s a n dt h e n , i ti si m p r o v e dt oc o n s i d e rt h ed i f f i c u l t y o ft h ey a r d sw o r k a f t e ri ti sg i v e nt h es p e c i a lc o d i n gp o l i c ya n dt h ev a l u eo fp a r a m e t e r s , g ai sc h o s e nt os o l v ei t f i n a l l y , t h ep a p e ri sp r e s e n t e dt h ev i e wo ft oo p t i m i z et h i sq u e s t i o na n dn e x th o w t o r e s e a r c hm a n yo p i n i o n s k e y w o r d s ：c o n t a i n e ry a r d ；g e n e t i ca l g o r i t h m s ( g a ) ；s e t u pa r r a n g e m e n t ，s t o r a g e l o c a t i o n ；m i x e ds t a c k 青岛大学硕士学位论文 学位论文独创性声明 本人声明，所呈交的学位论文系本人在导师指导下独立完成的研究成果。文中 依法引用他人的成果，均已做出明确标注或得到许可。论文内容未包含法律意义上 已属于他人的任何形式的研究成果，也不包含本人已用于其他学位申请的论文或成 果。 本人如违反上述声明，愿意承担由此引发的一切责任和后果。 论文作者签名。z 冁霸弓 日期：工习年月，o 日 学位论文知识产权权属声明 本人在导师指导下所完成的学位论文及相关的职务作品，知识产权归属学校。 学校享有以任何方式发表、复制、公开阅览、借阅以及申请专利等权利。本人离校 后发表或使用学位论文或与该论文直接相关的学术论文或成果时，署名单位仍然为 青岛大学。 本学位论文属于： 保密口，在 年解密后适用于本声明。 不保密醇 ( 请在以上方框内打“”) 论文作者签名：6 月序日 导师签名：了继霉 吼御年月。日 ( 本声明的版权归青岛大学所有，未经许可，任何单位及任何个人不得擅自使用) 第一章绪论 1 1 研究的目的和意义 第一章绪论 随着海上集装箱运输业的高速发展，国内外对于集装箱运输管理的研究正日益 广泛和深入。与传统方式相比较 3 】，采用集装箱运输时码头堆场空间能够被充分利 用，货物堆存密度高，周转速度快，并且货物在堆场的堆存方式也发生了重要变化。 集装箱在码头不再是根据货物提单号分票堆放，而是根据运载集装箱船舶的不同要 求，分港口、分重量级跺码堆存。 为保证集装箱堆场的合理使用，以及高效率的装船，堆场管理员制定了一整套 完整的集装箱堆存原则，以期尽可能避免在装船作业过程中产生取箱冲突。因此在 整个集装箱流 i 3 】中，码头堆场的管理占据着极为重要的地位管理水平的优劣直接 影响到集装箱周转时间，在管理中采用先进管理技术可以产生显著的经济效益。码 头堆场一般分为前方堆场和后方堆场，前方堆场是用来暂存出口重箱的 4 9 】，一般称 为码头前沿，其作用是当集装箱船到港前，有计划有次序地按积载要求将出口集装 箱整齐地集中堆放，卸船时将进口集装箱暂时堆放在码头前方，以加速船舶装卸作 业。集装箱后方堆场则是进行重箱或空箱交接、保管和堆存的场所。有些国家对集 装箱堆场并不分前方堆场或后方堆场，统称为堆场。重箱作业操作难度大，时间效 率要求高，是与集装箱堆跺方式直接相关的。长久以来，堆跺方式一直是堆场管理 的重要环节。不同的堆跺状态决定不同的装船顺序，由于集装箱专用船舶结构特殊， 很容易产生中拱，装船时就必须要充分考虑集装箱装船顺序。另外，还要考虑船舶 是否具备合理的稳性和吃水差i 若将集装箱在船上理想的堆存顺序“倒扣”在堆场i 再配合有序的机械运作，将是最合理的码头作业方式。但由于集装箱到港时间和顺 序的随机性，这种方式很难实现，因此必须优化堆场堆跺的方式。 在市场经济条件下，港口市场不断开放，港口之间的竞争越来越激烈。由于运 输船只及港口相关设备价格昂贵，并且运输船只在港停泊时间的长短直接影响的港 口的经济效益和社会效益，因此如何对港口物流系统进行更合理有效的规划，提高 运营效率，降低费用和价格，从而吸引较多的船舶挂靠，产生更好地经济效益，是 目前急需解决的问题。 另一方面，港口投资规模大，各种设备及场地维护需要大量的资金投入从投 资效益角度讲，应该使港口设施充分利用，不出现闲置现象，从而使港口的投资得 到最大的回报。但是现有的工艺流程是将出口箱按照p s c w 原则堆放，严重浪费了 青岛大学硕士学位论文 堆场空间资源。虽然在一定程度上解决了装船时倒箱的问题，但相对于浪费的堆场 空间以及浪费的因重箱堆垛时龙门起重机的大车运行距离加大而增加的能源、人工 时间等是得不偿失的。 海运是现代物流环节中的重要组成部分【3 l 能提供可靠、灵活的运输服务。现 代港口的综合服务水平是衡量一个国家物流水平的重要标志。集装箱船舶运输优势 确立之后，件杂货集装箱化和大宗散货集装箱化运输成为全球运输业的重要发展趋 势。堆场是决定集装箱港口码头的一个重要组成部分，因为在面积上来说，堆场占 码头面积最大，不合理的布局会导致堆存能力的降低，从而导致码头通过能力的下 降。所以在现有的堆存能力的情况下，尽可能的发掘潜力对一个港口来说是非常重 要的。 随着现代物流的不断发展，港口管理者越来越意识到提高港口内部物流运作效 率对港口发展的重要性港口内部物流效率的高低不仅影响到港口本身的竞争力水 平，还影响到以港口为基本节点的整个物流运输链的效率。同时随着国际航运业的 迅猛发展，集装箱运输量的大量增加，集装箱码头管理者纷纷采取不同的措施努力 提高物流的运作效率。其中最直接的方法不外乎扩大运营面积，采购或更新设备。 考虑到巨额的成本问题，不能通过无限制购进设备，扩大场地来满足箱量的需求和 提高码头服务水平。必须通过对现有资源( 场地、桥吊、集卡和人力等) 合理配置 来提高码头装卸效率。 码头堆场的利用率是港口装卸工艺设计中一个不可或缺的重要参数，它客观反 映了港口规划的合理性、港口通过能力的现状及潜力，并为分析港口内部经济效益 提供了理论基础【4 9 l 。如果堆场空间利用率过高，就会造成龙门吊有效工作时间的减 少；堆场空间利用率过低，则码头实际生产能力得不到发挥。同时要确定一个堆场 的最佳利用需要做大量深入细致的工作，必须全盘了解码头及集装箱船舶生产工艺； 必须实地考察，掌握码头年生产任务，各船务公司成型的操作习惯及要求，到港代 表船型、到港时间等因素，然后利用排队论或计算机仿真优化的方法，求出最佳堆 存位置，以便装船时间最短，倒箱次数最少。从而使船舶在港时间最短，并减少设 备无效动作使码头运营费用最省。 在堆垛位置分配过程中，重箱到港是随机的，在时间上是离散的，每一个重箱 的重量和目的港都可能不同，这些变量也具有随机性、动态性。所以整个堆存位置 分配过程是一个离散的、动态的随机过程。对于这类问题，很难用确定性的数学模 型进行描述，因而难以采用一般的优化方法进行求解。 实践表明，遗传算法求解最优化问题计算效率比较高、适用范围相当广。h o l l a n d 2 第一章绪论 给出的图式定理解释了这一现象。所谓图式，就是某些码位取相同值的编码的集合。 图式定理说明在进化过程的各代中，属于适应度高、阶数低且长度短的图式编码数 量将随代数以指数形式增长，使遗传算法求解问题的效率相应的得到很大的提高。 另外遗传算法具有隐含的并行计算的特性，不易收敛于局部最优解研究表明，上 述遗传算法经适当改进后对任意优化问题以概率1 收敛于全局最优解【5 7 。 另外，港口作为一个服务系统，货流量、货物流向以及港口生产过程都具有随 机的性质，从而为科学决策管理带来一定的难度。将计算机仿真技术应用到港口物 流中，对规划设计及运营中的问题进行分析，预测生产的发展趋势，对拟定的多种 方案进行模拟，将结果进行比较和选优，可为物流系统提供定量化的决策支持信息， 因而具有重要的现实意义。国内外虽然对港口码头类似的研究工作不少，但在国内 结合实际应用且易于为港口所使用的软件成果很少。根据现有的或规划中的码头堆 场的设施和设备情况进行过程仿真，用二维图像显示集装箱码头堆场贝位分配的动 态工作过程，为物流系统的规划和管理提供了可靠而直观的决策辅助手段。随着离 散事件系统理论的日趋完善和计算机软件的发展，为人们解决复杂的离散事件系统 的决策问题提供了手段，因此计算机仿真已逐步成为对集装箱码头进行分析和设计 的有力工具。 1 2 国内外研究现状 码头工作涉及方面较广并且极为复杂，必须制定相关的工作计划。在按照时问长 度分类的各项计划中，堆场计划为中期计划。具体是根据集装箱流预测值、船舶类 型、船舶航行信息( 提前几周获知) 等，作出堆场空间堆放策略“”。出口箱进场堆 存计划是堆场计划管理的重点。 出口箱堆场堆存计划是根据出口船舶该航次的预配箱量，安排恰当的出口堆场的 若干排、区用于该航次船舶出口箱的堆存。该计划只针对于货箱，冷冻箱都安排在 冷冻箱专用场地。由于冷冻箱数量较干货箱少的多，作业计划也相对简单的多。 堆场计划研究是相关学者的研究重点之一 1 ) t e l e b - - - i b r a h i m i 等“”( 1 9 9 3 ) 分析了集装箱港口堆场位置分配问题，并提出可以 为比分配位空闲早到的集装箱提供一个临时的缓冲区。这篇文章集中于为每艘到港 的船确定堆场存放区域而没有真正考虑如何具体确定集装箱在堆场中的存贮位置。 2 ) 1 w a t a n e b e ( 1 9 9 1 ) 在重箱先于轻箱进行装载的原则下，采用动态规划模型， 以翻箱作业量最小化为目标，为出口集装箱确定堆场位置。 青岛大学硕士学位论文 3 ) b d e c a s t i l h o 和c j d a g a n ( 1 9 9 3 ) 指出，为了较好地实现堆场的效益优化， 需要对集装箱情况进行估计并将其作为堆场层高相对布局的策略函数并最终在层 高、堆场的利用率以及堆场操作效率间达成妥协。 4 ) k h i g m 等( 1 9 9 4 ) ”1 在预计堆场设备的操作能力的基础上，为动态到达的出 口集装箱分配堆场位置，该方法也可用于为到港的集装箱上卸载的集装箱分配堆场 位置。k h k i m ( 1 9 9 - 0 研究了当进港集装箱以随机方式到达时对翻箱率的估计问 题。k h k i m 和h b k i m ( 1 9 9 8 ) 讨论了进口集装箱的存贮以及翻箱问题，并讨论 了启发式规则下堆场的集装箱分配问题。k h k i m 嘲等( 2 0 0 0 ) 考虑了具有权重的 出口港集装箱的堆放配位问题，以及最小化翻箱作业量问题。 目前针对集装箱在堆场的配位问题的文献资料主要考虑如何在最小化翻箱作业 量与最大化堆场利用率之间达成妥协，而且绝大多数研究都以静态的方式进行到 目前为止，尚未有成功解决动态情况下堆场集装箱分配调度优化问题的文献记载。 在我国，目前对这些方面的研究几乎还是一个空白，大部分研究仅停留在堆存方式 和原则的定性讨论上。本文尝试从动态角度，综合考虑箱重和目的港两个参数，采 用进化规划和启发式算法对问题进行描述并以最小化倒箱次数为目标进行计算机建 模及仿真。 1 3 研究的内容和解决的关键问题 ( 1 ) 研究的主要内容 在日常生活及工程中，组合优化问题无处不在、无时不有。它研究的是含有有 限个可行解的问题。这其中一个重要并且普遍的应用领域就是考虑如何有效利用稀 缺的资源来提高生产力。典型的工程设计问题包括集覆盖、装箱、背包、二次分配、 确定最小生成树、机器调度排序与平衡、制造元设计、车辆路径、网络密度、设备 定位与布局、旅行推销员分配等。 虽然理论上这种问题的最优解可以通过简单枚举得到，但实际上通常不能实现。 特别对于实际规模的问题来说，可行解的数量可能特别巨大。组合优化中最具挑战 性的问题之一就是如何有效处理组合爆炸。解决这类困难问题的一种重要思路就是 采用遗传算法。 我们现在就是要解决如何为一个随机到达的重箱分配一个最优的堆存位置问题 【3 1 。这里针对青岛港具体情况，建立箱位( 专业术语是贝位- - b a y ，以下同) 分配的 数学模型，从而确定出优化目标( 倒箱次数最小) 、约束条件( 如在物理意义方面可行 等1 和边界条件。 4 第一章绪论 运用遗传算法对模型进行优化。考虑到约束和边界条件，在具体运用时，对遗 传算法进行一定程度的改进，从而得出贝位分配的最终优化方案。针对青岛港口集 装箱码头的现状，以m a t l a b 软件为基础，利用遗传算法工具箱，对解决该实际问题 进行编程运算。实现人机实时交互控制等内容。 ( 2 ) 解决的关键问题 1 ) 建立包括目标函数在内的贝位分配数学模型。目标函数是以倒箱次数最少为 目标。 2 ) 确定有关参数。目标函数中的参数可分为两类，一类是作为已知量输入的参 数，如堆垛状态，可行位置。这些参数直接影响到优化结果，必须符合港口的实际 情况另一类是事先无法得知的参数，如下一个重箱的重量级别、目的港等。在以 往的一些模型中，大多数把问题简化为静态问题，这与实际工作有很大的出入。 3 ) 约束条件的考虑。约束条件根据具体的港口有不同的考虑，如一贝的行、列 数、预留空位数等。 4 1 模型的求解。港口贝位分配是多变量的非线性整数规划问题，在这里我们采 用的寻优方法是遗传算法。 5 1 遗传编码的确定。应用遗传算法的第一步是编码方案的确定。不同领域的问 题需采用不同类的编码方案。大多数工程问题不可能采取二进制编码来表示问题的 解，本论文整数编码方案与实际问题结合紧密。 6 ) 初始种群的生成。遗传算法同时运算在由已编码的参数集组成的称为种群的 大量可能答案上【5 9 1 。初始种群的生成必须重点考虑，不仅要符合实际问题还要尽可 能少的包含不可行解。 7 ) 遗传算子的确定。对于组合优化问题，遗传算法的收敛速度较慢。算法中杂 交和变异两个算子都很重要。选用不同的算子将可能得不同的优化结果，有时不合 适的算子可导致优化过程的失败。 1 4 采取的研究方法和技术路线 ( 1 ) 查阅港口方面相关文献资料，对港口进行实地考察，了解制定一个贝位分配 计划所要考虑的各种实际因素，为建立数学模型提供现实的依据。 ( 2 ) 建立港口贝位分配的数学模型后，将它与以往的模型进行比较并逐步完善， 使模型更加符合港口的实际情况。 5 青岛大学硕士学位论文 ( 3 ) 用遗传算法对数学模型进行优化计算。利用遗传算法求解最优化问题，首先 应对可行域中的解进行编码，然后在可行域中随机挑选一些编码组成作为进化起点 的第一代编码组，并计算每个解的目标函数值，也就是编码的适应度。然后利用选 择机制从编码组中随机挑选编码作为遗传操作过程前的编码样本。选择机制应保证 适应度较高的解能够保留较多的样本：而适应度较低的解则保留较少的样本，甚至淘 汰。在接下去的过程中，遗传算法提供了交叉和变异两种算子对挑选后的样本进行 交换。交叉算子交换随机挑选的两个编码的某些位，变异算子则直接对一个编码中 的随机挑选的某一位进行反转。这样通过选择和繁殖就产生了下一代编码组。重复 上述选择和繁殖过程，直到结束条件得到满足为止。进化过程最后一代中的最优解 就是用遗传算法解最优化问题所得到的最终结果。如下图1 1 所示为应用遗传算法 解决实际问题的步骤，在应用过程中，针对贝位分配具体的数学模型，对遗传算法 进行了改进。 图1 1 贝位分配问题优化流程图 ( 4 ) 采用大型软件m a t l a b 遗传算法工具箱编程计算。 1 5 创新点 ( 1 ) 建立了随机条件下确定贝位的数学模型； 6 第一章绪论 ( 2 ) 数学模型基于集装箱混合堆存工艺； ( 3 ) 针对所到达集装箱重量级别和目的港的随机性，采用了动态向量描述表示法； ( 4 ) 针对不同的初始状态有不同的可行位置的特点，利用遗传算法进行并行计算； ( 5 ) 将遗传算法应用动态闯题的结果与静态条件下的优化结果进行分析比较； 全文分为4 章，第一章论述了课题的来源、目的、意义，简单讨论了贝位分配 问题、物流系统仿真的国内外发展动态，论文的主要内容及所解决的关键问题：第二 章具体对贝位分配问题进行分析，建立贝位分配问题的数学模型；第三章应用遗传 算法对问题进行了研究，并给出了算例；第四章讨论了静态下集装箱堆场贝位分配 启发式算法模型和动态规划模型，比较了优化结果。最后对全文进行总结和展望。 7 青岛大学硕士学位论文 第二章贝位分配问题数学模型的建立 2 1 问题的描述 青岛集装箱码头采用的是轮台式龙门起重机系统。堆场被划分为若干区，每区又 被划分为若干段。每段包括2 0 - 3 0 贝，每贝有6 列4 层共2 4 个贝位。实际工作中， 倒箱是不可避免得。因此，每贝一般留出2 3 个空贝位( 本论文采用3 个空贝位) ， 实际贝位只有2 1 个如下图2 1 所示： 图2 1 贝位示意图 t r a n s f e rc r a n e ：轮台式龙门起重机。由前后两片门框和底梁组成门架，支撑在 橡胶轮胎上。装有集装箱吊具的行走小车沿着门框横梁上的轨道运行，配合地盘车 进行集装箱堆码和装卸作业。大车沿段位方向水平运行；小车运行包括抓起、平移、 放下，其中平移方向与大车水平运动方向垂直。 t r u c k ：集装箱卡车。用于集装箱在堆场的水平运输。 b l o c k ：段区。由若干贝组成。 在建立贝位分配数学模型之前，我们需要了解贝位分配的流程和特点，才能建 立出行之有效的模型。 出口箱堆场堆存计划是根据出口船舶该航次的预配箱量，安排恰当的出口堆场的 若干排区用于该航次船舶出口箱子的堆存。该计划只真对干货箱，冷冻箱都安排在 冷冻专场，另作计划。 8 第二章贝位分配问题数学模型的建立 对于货箱主要是按港口( 或码头) 、箱型、重量进行安排，以利于箱子的装船。重 量是按划分重量级别而定，而不是完全按重量而来。重量级别的划分一般视装箱量 而定。重量级别若划分过细级别设立过多，则不利于堆场的安排，容易造成堆场 的堆存不均，造成堆存能力的浪费；若划分过粗重量级别设立过少，也不利于装 船，或造成经常的捣箱、磨损机械，或造成在装船中轻重倒置，船舶稳性不好。因 此，重量级别一般选定在l 3 级，依航次装箱量与船舶情况而定。 堆场计划还需有利于装船的多条作业线的安捧若将所有同一艘船的出口箱都安 排在一起，当需要开多条作业线时，就会造成场内机械、车子的混乱，线路交叉； 轻则降低装船速度，增加装船时间，重则造成装错箱子，甚至交通事故。这是堆场 计划的重点。当某一卸货港箱子数量过多，需要开两路以上作业线作业，就需将该 港箱子分别堆存在有两台桥吊的作业区，以便多路作业。 堆场堆存的传统做法是将不同目的港的集装箱堆存在不同段位上，同时在同一段 位上的贝位上堆存相同重量级别的箱子。采取这样的堆存工艺，可以在不倒箱的情 况下完成集装箱的装载。但问题有两个： ( 1 ) 堆场空间的浪费 相同重量级别的箱子的数量经常比每一贝的容量小的多，每贝都会浪费一定数 量的空间，综合起来将是个巨大的数字。 ( 2 ) 堆场龙门起重机大车工作效率低 堆场龙门起重机大车沿段位纵向移动、小车横向移动。当两个相邻到达的集装 箱不是同一重量级别或不是同一目的港时，大车将移动较大距离，以达到工作区 域。 理想的堆存工艺是将不同目的港、不同重量级别的箱子混合堆存，一贝不满尽 量不将到达的集装箱安排在下一贝上，以减少大车移动距离，提高工作效率。 前方堆场堆箱和取箱都存在不同初始状态有不同操作难度的情况。这里将操作 难度进行定义和分级。通常情况下，存在下面几种情况： 9 青岛大学硕士学位论文 直飞亘可口 2 2 数学模型的建立 2 2 1 基本假设： 厂日， p _ ilil 曩爱善暖4 图2 0 操作难度等级示意图 ( 1 ) 所考虑的集装箱都是标准干箱，即尺寸为2 0 英尺的通用集装箱。其结构为封闭 式，用以装载除液体货物、需调节温度及特种货物外的一般件杂货。 ( 2 ) 按照目的港和重量将待安排集装箱分类。重箱进入前方堆场时，这两个参数都可 以通过相关单证( 如提单等) 的记录而得到。本文在研究过程中选取一条实际航 线，以航线上各个港口顺序为依据，并将箱子划分为三个重量级别来研究。 ( 3 同一集装箱船舶承运的不同目的港的、不同重量级别的集装箱可以混合堆存在同 一贝中。 ( 4 ) 倒箱在同一贝内进行。 ( 5 ) 集卡按照先入先出( f i f o ) 原则运行。同一时间、同地点只有一辆集卡等待 装箱或卸箱。 ( 6 ) 轮胎式龙门吊的动作简化为抓起、平移和放下三个过程，并将一次抓起一平移一 放下过程视为一次倒箱。 f 7 ) 堆存过程中不就已经堆存好的集装箱进行倒箱。 为说明贝位分配过程，先说明重箱入场流程。青岛前湾港重箱入场流程如下： s t e p l 集卡司机持相关单证到q q c t 检查口申请作业。 第二章贝位分配问题数学模型的建立 s t e p 2 检查口业务员为核对装箱单内容，打印进场小票。 s t e p 3 司机根据进场小票到指定箱区由堆场管理员指导安排贝位。 s t e p 4 堆场管理员根据小票指挥机械操作员将重箱放入指定位置，并注明实际贝位。 s t e p 5 司机将进场小票交回检查口，办理出场手续。 图2 3 堆场收箱流程图 依照上述流程，重箱贝位的确定是由堆场管理员根据当前情况，并根据以往经 验指定。由于不能准确预测下一个到港的集装箱的情况，港口为避免大量倒箱采用 折中的办法，就是将不同目的港的集装箱分段堆存，将不同重量级别的集装箱分贝 堆存。 这里采用将不同重量级别、不同目的港的集装箱混合堆存的工艺，假设贝位初 始状态为空。随机到达的集装箱记为gp l ，2 ，2 1 。分两个方面考虑集装箱的贝位： 1 、整个前方堆场贝位堆存问题含有动态性、阶段性。按照动态规划的思想，每 1 1 青岛大学硕士学位论文 个阶段达到最优并不能保证整个过程的最优。 2 、考虑到前方堆场作业繁忙和连续性，有必要考虑如何在装船取箱作业中，降 低工作难度。 针对于第一个方面，可以采用适当的编码方法和种群生成方法解决；第二个方 面可以根据堆场实地情况以约束的形式体现。下面将有详细介绍。 2 2 2 设计变量及参数： c l a s s = 1 ，2 ，c 为由箱子优先级别组成的集合，数值越大，其优先级别越大； s t a c k ( s ) = 1 ，2 ，斟为贝位所有堆垛列组成的集合； s t a g e = 1 ，2 ，t 表示由不同装载阶段组成的集合，集装箱船舶装载时，贝上 每搬移一个箱子，为一个阶段；每搬移一次箱子为一个s t a g e ，t 为总的阶段数量； m a x p ( t ) = c 记录当前状态下的最大优先级别； 月j 自咖讹泸协6 b j i j 表示某堆垛列在的高度，当前流行的堆存工艺是龙门吊一 集卡工艺，可堆成6 列4 层。 b a y l n i t s t a t i o n ( i 棚i c 2 一( 1 ) 式2 一( 1 ) 表示贝初始堆放状态；c 表示有重量级别为c 的重箱；0 表示没有箱。 s h e l v e ( s ) = n b n 3 n s 表示某堆垛列的压箱数量，压箱数量的计算下图2 3 。在 b a y 位的某一个堆垛列中，假设己装有若干个集装箱，集装箱上面标出的数字表示 其优先级别，数字大者表示优先级别高应置于上方，上下相邻的两个箱子，若上方 集装箱的数字小于其下方集装箱，则表示需要倒箱。如优先级别为k 的箱子在优先 级别为，的箱子下面，而k - f ，则优先级别为l 的箱子阻塞了重量级别为k 箱子通路， 称为阻塞箱。 压箱数量确定：在当前状态下，记录当前堆垛列高度e 取优先级最大的箱子， 并记录位置为计算肛并更新堆垛高度西可一及堆垛状态。当1 t - - 1 时结束判断， 计算删的和即为压箱数量，如图2 4 所示。 第二章贝位分配问题数学模型的建立 r o w 1 2 3 4 56 围 5 2 回 4 3 5 l 5 2 5 2 4 2 4 2 o 5 l 4 2 同 3 2 4 25 2 1 2 2 33 i 2 3 2 3 4 2 压箱数 1 020 00 图2 4 压箱量的计算 图中二位整数表示集装箱的特征，十位表示该箱的目的港；个位表示该箱的重 量级别，下面会详细介绍。被小矩形框起的即为阻塞箱。 设计变量 比彤，一s 紫袖橼弛棚到冽 弛眦咖s 嚣筋列莉的箱子被取走 h 酬净s 鳊堞冽射层有衍放入 2 一( 2 ) 2 一( 3 ) 2 - ( 4 ) r c 阶段t 第i 列第j 层有优先级为c 的箱子 $ 1 0 t s t a t i o n ( t ，i ，) j0 ，- 1 ，且该位置无箱 2 一( 5 ) i 一1 否则 2 一( 6 ) 式2 - ( 5 ) 记录阶段s t a g e ( t ) b a y 位状态； 式2 - ( 6 ) 为s c a g e ( o gi 列第，层箱子的取箱代价，每一个堆垛列最上层箱子的取 箱代价为0 。 文中所涉及的取箱代价指的是当前状态下最大优先级别箱子的取箱代价。 青岛大学硕士学位论文 2 2 3 目标函数及约束条件 曲盖五盖地y 声)名表名缸名厶一。 忍触f o ，i ， ) + x x x p u t l n ( t ，i ，d 1 s l o t s t a t i o n ( t + l i ，) o ：p u t l n ( t ，i ，j + 1 ) 一1 砒伽f ( f ，i ，) + 珈o ，i ，j ) - l s l o t s t a t i o n ( t + l i ，) 一- 1 ：t a k e o u t ( t ，i ，+ 1 ) 一1 x ( t ，y ，z ) - l ：p u t l n ( t ，i ，j ) 一1 目标函数表示倒箱数量最少； 式2 - ( 8 ) 表示每一个s t a g e ( t ) 对应一种b a y 位的存储状态，在某一个s t a g e 内最多只容 许一只箱子的移动； 式2 ( 9 ) 表示当一个堆垛列中放入一个箱子时，不会出现悬空的情形；式中的“：” 号表示当前一个式子的条件存在时，后一个式子“成立”； 式2 - ( 1 0 ) 表示移箱次数与取箱次数的和组成所有的作业阶段； 式2 - ( 1 1 ) 表示取箱操作时，则只能是最上层的箱子； 式2 - ( 1 2 ) 表示只有发生倒箱操作时，才会产生p u t n 动作。 1 4 埘 蚴 纠 纠 醐 州 州 第三章基于遗传算法的贝位分配问题研究 第三章基于遗传算法的贝位分配问题研究 3 1 遗传算法简介 遗传算法是进化计算三大分支之一，是一种模拟生物进化过程与机制求解问题 的自组织、自适应性人工智能技术。遗传算法是结合了达尔文的自然选择与孟德尔 的遗传变异理论，将生物进化中的四种基本形式：繁殖、变异、竞争和选择引入到算 法的过程中，指导算法的进行。 把计算机科学与进化论结合起来的尝试开始与2 0 世纪5 0 年代末，但是由于缺 乏一种通用的编码方案，使得人们只能依赖变异而不是杂交来产生新的基因结构， 故而收效甚微。到2 0 世纪6 0 年代中期，美国m i c h i g a n 大学的j o h nh o l l a n d 在as f r a s e 和h j b r e m e r m a n n 等工作的基础上提出了位串编码技术，这种编码即适合于 变异又适合于杂交操作，而且他强调将杂交作为主要的遗传操作。随后，j o h nh o l l a n d 将该算法用于自然和人工系统的自适应行为的研究之中，并于1 9 7 5 年出版其开创性 的著作( a d a p t a t i o ni nn a t u r a la n d a r t i f i c i a ls y s t e m s 。后来，j o h nh o l l a n d 和它的学 生们将该算法加以推广并应用到优化及机器学习等问题之中，并且正式定名为遗传 算法。遗传算法的通用编码技术及简单有效的遗传操作为其广泛的应用和成功奠定 了基础。 h o l l a n d 的遗传算法常被称为简单遗传算法( s g a ) 。s g a 的操作对象是一群二进制 串佛为染色体、个体) ，即种群( p o p u l a t i o n ) 。这里每个染色体都对应于问题的一个解。 从初始种群出发，采用基于适应值比例的选择策略在当前种群中选择个体，采用杂 交( c r o s s o v e r ) 和变异( m u t a t i o n ) 来产生下一代种群。如此一代一代的进化下去，直到 满意期望的终止条件。 遗传算法可以形式化描述如下： g a - ( p ( 0 ) ，f ，j ，g ，p ，f ，f ) 这里e ( o ) 0 。( o ) ，a ：( o ) ，a ，( o ) ) ，v ( o ) 一瓴( o ) ，a ：( o ) ，a ，( o ) ) ，表示初始 种群； i 一- o ，珥表示长度为1 的二进制串全体，称为位串空间； 表示种群中含有个体的个数； ，表示二进制串的长度： 青岛大学硕士学位论文 j ? ，卅表示选择策略： g 表示遗传算子，通常它包括繁殖算子d ，叽杂交算子d c ：，x ，吁和变异 算子o l m ：卜q ： p 表示遗传算子的操作概率，包括繁殖概率办、杂交概率m 和变异概率p m ： 甜幔堤适应函数： o ，叫d ，j ，是终止准则。 3 1 1 遗传算法主要特点 遗传算法主要特点可以概述如下： ( 1 ) 自组织、自适应和自学习性( 智能性) 。应用遗传算法求解问题时，在编码方 案、适应度函数及遗传算子确定后，算法将利用进化过程中获得的信息自行组织搜 索。由于基于自然的选择策略为“适者生存，不适应者被淘汰”，因而适应度大的个 体具有较高的生存概率。通常，适应度大的个体具有更适应环境的基因结构，再通 过基因重组和基因突变等遗传操作，就可能产生更适应环境的后代进化算法的这 种自组织、自适应特征，使它同时具有能根据环境变化来自动发现环境的特性和规 律的能力，自然选择消除了算法设计过程中的一个最大障碍，即需要事先描述问题 的全部特点，并要说明针对问题的不同特点算法应采取的措施。因此，利用遗传算 法的方法，我们可以解决那些复杂的非结构问题。 ( 2 ) 遗传算法的本质并行性。遗传算法按并行方式搜索一个种群数目的点，而不 是单点。它的并行性表现在两个方面，一是遗传算法是内在并行的，即遗传算法本 身非常适合大规模并行。最简单的并行方式是让几百甚至数千台计算机各自进行独 立种群的演化计算，运行过程中甚至不进行任何通信，等到运算结束时才通信比较， 选取最佳个体。这种并行处理方式对并行系统结构没有什么限制和要求，可以说， 遗传算法适合在目前所有的并行机或分布式系统上进行并行处理，而且对并行效率 没有太大影响。二是遗传算法的内含并行性。由于遗传算法采用种群的方式组织搜 索，因而可同时搜索解空间内的多个区域，并相互交流信息。使用这种搜索方式， 虽然每次只执行与种群规模n 成比例的计算，但实质上己进行了大约o ( n 3 ) 次有效搜 索，这就使遗传算法能以较少的计算获得较大的收益。 ( 3 ) 遗传算法不需要求导或其它辅助知识，而只需要影响搜索方向的目标函数和 相应的适应度函数。 ( 4 ) 遗传算法强调概率转换规则，而不是确定的转换规则。 ( 5 ) 遗传算法对给定问题，可以产生许多的潜在解，最终选择可以由使用者确定。 1 6 第三章基于遗传算法的贝位分配问题研究 3 1 2 遗传算法的一些基本概念 由于遗传算法是由进化论和遗传学机理而产生的直接搜索优化方法，故而在这 个算法中要用到各种进化和遗传学的概念。这些概念如下： ( 1 ) 串 咖) 它是个体伽幽树妇2 ) 的表达形式，在算法中为字符串，并且对应于遗传学中的 染色体( c h r o m o s o m e ) 。 ( 2 ) 群体( p o p u l a t i o n ) 个体的集合称为群体，串是群体中的元素。 ( 3 ) 群体大t j s ( p o p u l a t i o ns i z e ) 在群体中个体的数量称为群体的大小。 ( 4 ) 基因( g e n e ) 基因是串中的元素，基因用于表示个体的特征。例如有一个串s = i o l l ， 则其中的元素1 ，0 1 ，1 分别称为基因。它们的值称为等位基因6 4 t l e t e s ) 。 ( 5 ) 适应度( f i t n e s s ) 表示某一个体对环境的适应度。 3 1 3 遗传算法的流程 遗传算法的主要步骤如下： s t e p l ：随机产生一个由确定长度的特征串组成的初始群体： s t e p 2 ：算群体中的每个个体的适应值，判断是否符合优化准则，若符合，输 出最佳个体及其代表的最优解，并结束计算，否则转向s t e p 3 ； s t e p 3 ：依据适应度选择再生个体，适应度高的个体被选中的概率高，适应度低 的个体可能被淘汰； s t e p 4 ：按照一定的交叉概率和交叉方法，生成新的个体： s t e p s ：按照一定的变异概率和变异方法，生成新的个体： s t e p 6 ：由交叉和变异产生新一代的种群，返回s t e p 2 ； s t e p 7 ：终止运算后把在任一代中出现的最好的个体指定为遗传算法的执行结 1 7 青岛大学硕士学位论文 果。这个结果可以表示问题地一个解( 或近似解) 。 图3 1 基本遗传算法框图 基本的遗传算法框图由图3 1 给出。关于基本的遗传算法有许多描述形式， 它们之间的差异不大，这里给出的算法框图仅是其中的一种形式。例如，变异经常 视为与选择或交叉一起连续发生的操作，故一个给定个体可以在一代内进行选择和 交叉，或进行交叉和变异。另外，选择算子的执行次数应是一个明确的数，而不是 按照概率决定。 3 2 遗传算法的实施 应用遗传算法求解实际问题时，需要完成以下四个主要步骤： ( 1 ) 确定编码方案； ( 2 ) 确定适应值度量； ( 3 ) 确定控制算法的参数和变量； ( 4 ) 确定指定结果的方法或停止运行的准则； 在常规的遗传算法中，编码是把问题的搜索空间中的每个可能的点表示为确定长 度的字符串。编码方式的确定需要选择串长f 和字符串规模k 。遗传算法中常用的编 码方式有二进制编码、浮点数编码和整数编码等。 在本论文撰写的初期，笔者曾考虑采用简单二进制串编码。在随后的研究当中发 现，采用简单二进制串编码存在重大的问题。由于组合优化问题中带有复杂的约束， 简单二进制串根本不能工作，原因是它必然会产生大量不可行解甚至非法解。 第三章基于遗传算法的贝位分配问题研究 适应度的确定经常是由问题本身所具有性质确定。算法进行中，必须为群体中 每一个确定长度的特征串指定一个适应值；并且还必须有能力计算搜索空间中每个 解的特征串的适应值。控制遗传算法的主要参数有群体规模n 和算法执行的最大代 数目m ，次要参数有交叉概率p c 和变异概率厶等参数。 这些准备步骤完成后，就可以执行遗传计算，遗传计算的流程在上已经讲过，这 里不再重复。 在前面我们己经得出了倒箱次数最少问题的数学模型， 作难度，可以得到动态条件下贝位分配模型： 曲墨互盖圯儿咖毗l ，) 约束函数： 砒仇f p ，i ，) + 而砌( f ，i ，j ) 1 s l o t s t a t i o n ( t + 1 ，f ，) 0 ：p u t l n ( t ，i ，+ 1 ) - 1 死妇踟f o ，i ，) + 珈o ，i ，) - r s l o t s t a t i o n ( t + 1 f ，) - - 1 ：t a k e o u t ( t ，i ，j + 1 ) - 1 x o ，y ，z ) 一l ：p u t i n ( t ，) 一1 以此为基础，考虑到