（计算机软件与理论专业论文）基于遗传算法的进口箱堆场bay位分配优化模型研究.pdf

中山大学硕士学位论文 基于遗传算法的进口箱堆场b a y 位分配优化模型研究 基于遗传算法的进口箱堆场b a y 位分配优化模型研究 专业：计算机软件与理论 硕士生：周留井 指导老师：姜云飞教授 摘要 集装箱码头的堆场部分可分为前方堆场和后方堆场，它的主要作用是为集装 箱提供临时的集中堆存。堆场管理是码头生产的一个重要环节，它包括多个方面， 主要包括堆存优化和堆场机械调度等。本文的研究仅限于后方堆场的进口箱( 本 文所提到的进口箱通常情况下指进口重箱) 堆存优化方面。堆存优化主要包括以 二 下两个领域，第一个领域主要从有效利用堆场空间的角度考虑；第二个领域主要 从减少倒箱次数的角度考虑。这两个领域追求的目标不同。在优化一个目标时， 要充分考虑另一个目标的制约作用。 本文建立的进口箱堆存优化模型主要是从充分利用堆场空间的角度考虑，同 时尽量减少倒箱次数。本文以一b a y 为对象，采用混合堆存策略，考虑不断变 化的堆存状态和操作难度，为每一个动态到达后方堆场的进口箱安排b a y 位僳 装箱在& 谨内的箱位) ，目的是在提箱作业期间倒箱次数最少。该问题是一个 n p 难问题，很难用传统的优化方法解决。文中对该问题进行了一定程度的简化， 首先针对倒箱次数建立了数学模型，然后采用并行遗传算法对模型进行求解。同 时文中给出了算法所需的各种参数的值，包括子种群数目、进化代数、遗传算子 的取值和相应的编码策略。论文最后针对不同情况下的优化结果进行了比较，对 该问题的研究进行了总结和展望并提出了进一步研究的着眼点。 ： 关键词：集装箱堆场，b a y 位，倒箱，混合堆存，并行遗传算法 中山大学硕士学位论文 基于遗传算法的进口箱堆场b a y 位分配优化模型研究 t h er e s e a r c ho nt h eo p t i m i z a t i o nm o d e lo nb a y s l o ta l l l o c a t i o n f o re a c hi m p o r tc o n t a i n e rb a s e do ng a m a j o r ：c c 脚p u t e rs o 加，a r e 如d1 1 l 巧 n a m e ：z l l o u u u j i n g s u p e n ，i r ：p f e s rj i a n gy u n f e i a b s t r a c t t h e 咖t a i n e fy 棚，w h i c hm a i nr o l ei st 0p m 、，i d et e m p o f a r ) ，c o n t a i n e r n 仃a l i z e dd u m p s ， c a nb cd i v i d e di n t 0t h e 觚 n ty a r d 觚dt h er e 缸y 删c 0 n t a i n e ry a r dm 孤a g e m e n ti s 腑i n l yt 0 0 p t i m i z ct h e n t a i 】1 e rd u m p si n 伽e 功蚪粕dt h es c h e d l l l e d q u 锄c eo fy a r dm a c h i l l 胬n l i s p a p e fi sh m i t e dt 0t h cr e s e a r c h0 ft h e0 p t i m j 妇t i o no fb a ys 1 0 ta l l o c a t i o nf o re a c hi m p o r t c o m a i n 盯i nt h e 删匿y 缸d c 0 n t a i n e rd u m p s 0 p i m i z a t i c 姐b cc o n s i d e r e d 劬mt h ee 疵d i v e u s e0 fy 缸ds p a ，0 r 缸 mi e 够tt i m e s0 fr e h 姐d l e s ，w h i c ha 他c 0 i 仃e l a t e dt 0e ho t h e l l l l t h i s p a p e f t h e o p t i m i 船t i o n 脚d c l i m p o n c o n t a i n e r d u m p s i s b u i l t m “y 肋m 岫 p o i n to f 访e wo ft h ee m 斌i v eu o fy a r ds p a ，w h i l em i 血m i z i n gm en u m _ b c r0 fr e h 缸d l 伪 t h i sp a p e ri st os t u d yh o wt 0 髑i 印ak a t i 吼i n eb a y t 0 觚i n l p o nc o n t a i l l e rt 0i i l i n h i z e t h e肌皿l b e ro f s t l i f i 【i n g n t a i n e 璐晰t h t h ct c c h n o l o 斟0 fm i 】【e ds t a c k w h 钮 a w e i g l l t - i m p o n 啪n t a i n 盯删v e si nt h e 坨牡y 棚m d o i n l y ，i ti sd e s dt h a t 佗h 锄d l 伪t i m 锶 a r cm i n 咖t 0c o n s i d e rt h es i t u a t i o nt 0s t o 佗姐dt h el e v e l0 f 衄五c l l l t y s i i l c ct h ep r o b l e mi s n p h a r d ，i ti sq u i t ed 硒c i l l tt os o l v ei tu s i n g d i t i o n a lo p t i m 协dm e t h o d s ht h i sp a p e r ，t h e a u t h o rs i m p l i f i e st h ep r o b l e m sc o m p l e xt o m ed e 黟e ea n db u i l d st h ei d e l0 nt h eg o a l0 f t h el e 勰tt i m 路o fr e h a i i d l e s a n d m e n ，g i v e nt h es p e c i a lc o d i n gp o l i c y 柚dt h ev 2 l l u eo fr e l a t e d p a r a m e t e r s ，t h ea u t h o rc h 0 0 s e sp g at os o l v ei t f i n a u y ，t h ea u t h o rp r e s e n t st h ev i e wo f o p t i m i z i n gt h i sp r o b l e ma n dw h a tt 0f b c u so nf b rf u n h e rs t u d y k 田w o r d s ：n t a i n e ry a r d ，b a ys l o t ，f e h a n d l e ，n i i x e ds t a c l 【，p a r a u e lg e n e t i ca 1 9 0 r i t h m s ( p g a ) 中山大学硕士学位论文基于遗传算法的进【j 箱堆场b a y 碰分配优化模型研究 论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进行研究 工作所取得的成果。除文中已经注明引用的内容外，本论文不包含任何其他个人 或集体已经发表或撰写过的作品成果。对本文的研究作出重要贡献的个人和集 体，均已在文中以明确方式标明。本人完全意识到本声明的法律结果由本人承担。 学位论文作者签名7 司饧背 日期：刀d 易年易月冲日 中山大学硕上学位论文基于遗传算法的进口箱堆场b a y 位分配优化模型哑壅 学位论文使用授权声明 本人完全了解中山大学有关保留、使用学位论文的规定，即：学校有权保留 学位论文并向国家主管部门或其指定机构送交论文的电子版和纸质版，有权将学 位论文用于非赢利目的的少量复制并允许论文进入学校图书馆、院系资料室被查 阅，有权将学位论文的内容编入有关数据库进行检索，可以采用复印、缩印或其 他方法保存学位论文。 学位论文作者签名：目够本翩签名毒。睑 日期：矽d 多年杉月冲日 日期：加8 年厂月择日 中山大学硕士学位论文 基于遗传算法的进口箱堆场b a y 位分配优化模型研究 第1 章绪论 随着物流行业的不断发展，集装箱成为目前国际运输中最为流行的新型运输 工具。由于它快速、敏捷、安全而广泛被货主所认可。特别是在东、西方货运条 款不一致的情况下，集装箱运输显得尤为重要，它的发展越来越受到世界各国的 重视。随着科技的进步，集装箱运输管理越来越趋于自动化。近年来，国内外学 者对集装箱堆场管理的研究方兴未艾。这一领域的研究对于提高集装箱运输的效 率和效益、提高港口物流公司的利润、改善公司服务水平、加速码头堆场现代化 管理的进程，将具有重要意义。 1 1 课题的来源 本课题的研究来源于中山大学与佛山研究院合作的应用于佛山市新港码头 的项目“基于智能规划的港口作业调度管理中间件刀。 1 2 研究背景及意义 随着经济的全球化和信息化发展，现代物流业已经从为社会提供传统的运输 服务，发展为以现代科技、管理和信息技术为支撑的综合性物流服务。与传统方 式相比较，采用集装箱运输时码头堆场空间能够被充分利用，货物堆存密度高， 车船周转速度快，装卸作业效率高，节省费用。并且，货物在堆场的堆存方式也 发生了重要变化，更便于计算机管理，从而实现作业的自动化和标准化1 1 1 。 海运作为现代物流环节中的重要组成部分，能够提供可靠、灵活的运输服务。 据估计世界贸易的9 0 以上是通过海运方式实现的。集装箱船舶运输优势确立之 后，大宗散货集装箱化和件杂货集装箱化运输成为全球运输业的重要发展趋势。 随着中国加入w t o 、西部大开发、“走出去 三大战略进入实质性启动阶段，我 国与世界各国之间的贸易迅速发展，港口集装箱吞吐量保持了高速持续的增长。 2 0 年来，我国集装箱运输事业有了突破性的发展。2 0 0 3 年中国港口集装箱吞吐 量增长速度遥遥领先于世界各国的增长速度，总量接近5 0 0 0 万标准箱，比2 0 0 2 年递增3 2 【2 1 。目前，中国港口集装箱吞吐量已经超过美国，跃居世界第一。由 中山大学硕士学位论文基于遗传算法的进口箱堆场b a y 位分配优化模型研究 于我国8 5 以上的进出口贸易依靠海运完成，且由于我国对外贸易结构的调整， 我国港口的集装箱吞吐量将继续保持高速度的增长。据预测，到2 0 1 0 年，世界 货物海运量近7 0 亿吨。其中，中国港口货物吞吐量近4 0 亿吨，集装箱吞吐量约 1 1 亿标准箱【3 1 。 随着港口集装箱吞吐量的飞速增长，集装箱码头对堆场装卸效率要求越来越 高。集装箱堆场装卸效率的高低直接关系到整个港口运输过程的效率和成本，关 系到船公司的效益和货主的切身利益。目前大多数港口都面临堆场空间有限，堆 场管理方式落后等问题，这些现存的问题大大降低了堆场的装卸效率。提高装卸 效率最直接的方法不外乎扩大堆场面积，采购或更新设备。然而，港口装卸设备 价格昂贵，扩大场地需要投入巨额的资金，投入成本高、回收慢。因此，不能一 味地追求先进的设施、设备，而忽视高效率的基础一生产组织管型4 1 。港口必须 在现有装卸技术和硬件设施的基础上实现更高的作业效率，必须通过对现有资源 ( 场地、装卸设备、集装箱卡车和人力资源等) 的合理配置来提高码头的生产能力。 如何对港口现有资源进行更合理有效的规划和使用，提高装卸效率，降低成本和 费用，从而吸引较多的船舶挂靠，产生更好的经济效益，是港口目前急需解决的 问题。 堆场管理是码头生产的一个重要环节，因为从面积上来说，堆场占有码头的 面积最大，而装卸效率的提高很大程度上取决于码头堆场箱区、q 位安排的 合理性。合理的布局不仅能减少翻箱率，减少堆场作业的时间，提高码头装卸速 度，而且还能最大限度地提高码头堆场利用率和码头通过能力，降低码头生产成 本；不合理的布局则会降低码头的堆存能力，降低服务质量，增加码头生产成本， 降低堆场作业效率，从而导致码头通过能力的下降。因此，有效的堆场管理是提 高港口效益，解决港口问题的重要因素【引。由于前方堆场堆存能力的局限性，后 方堆场的建设和管理越来越受到人 l j 的关注。只有采用科学的堆存策略进行有效 的管理，才能进一步提高堆场利用率，从而为经营者降低经营成本，带) k 更大的 收益。所以对一个港口来说，在现有的堆存能力的情况下，尽可能的发掘潜力是 非常重要的。 港口集装箱运输投资规模大，需要投入大量的资金购买各种装卸设备及支付 场地维护费用。从投资效益角度讲，应该充分利用港口设施，充分使用场地的空 2 中山大学硕士学位论文基于遗传算法的进口箱堆场b a y 位分配优化模型研究 间，使港口的投资得到最大的回报。然而现有的堆存策略是将进口箱按照不同提 单或者不同货主的集装箱放在不同的b a y 上，这样每一b a y 都浪费一些空间， 综合考虑就严重浪费了堆场空间资源。这样虽然在一定程度上解决了提箱时倒箱 的问题，但相对于浪费的堆场空间以及卸船作业过程中增加的机械磨损和人工时 间等是得不偿失的。 码头堆场的利用率是港口装卸工艺设计中一个不可或缺的重要参数，它客观 反映了港口规划的合理性、港口通过能力的现状及潜力，并为分析港口内部经济 效益提供了理论基础【4 】。如果堆场空间利用率过高，就会出现大量的压箱现象， 降低提箱作业的效率；堆场空间利用率过低，则码头实际生产能力得不到充分发 挥。要确定一个堆场的最佳利用就需要做大量深入细致的调研工作，必须全盘了 解码头及集装箱船舶生产工艺流程；必须实地考察，掌握码头的堆存规则，成型 的操作习惯和要求，学习后方堆场理货员安排进口箱堆场b a y 位的经验，货主 一般的提箱时间，货主提箱目的地距离堆场的远近等因素，然后利用计算机仿真 优化等方法，求出进口箱的最佳堆存位置，以便提箱时间最短，倒箱次数最少。 在堆垛位置分配过程中，进口重箱到达后方堆场是随机的，在时间上是离散 的，每一个进口箱的提箱时间和提箱目的地都可能不同，这些变量具有一定的随 机性和动态性。所以整个进口箱的堆存b a y 分配过程是一个离散的、动态的随 机过程，进口箱堆场b a y 位分配问题是一个n p 难的组合优化问题。随着问题 规模的增大，组合优化问题的搜索空间也急剧扩大，有时在目前的计算机上很难 或者不能用枚举法求解最优值。遗传算法经过三十多年的开发研究和应用实践， 已初步显示出其解决复杂系统优化问题的良好能力，特别是对一些n p 组合优化 问题的求解，更表现出了优异的性能。研究表明，经过适当改进后的遗传算法对 任意优化问题以概率1 收敛于全局最优解【5 1 。实践证明，遗传算法对于组合优化 中的n p 问题计算效率高，适用范围广，是一种非常有效的工具。 进口卸船作业是大多数港口的主要或重要的业务，后方堆场的很大一部分堆 区专门用来存放进口重箱。因此采用什么样的堆存策略以方便合理地安排进口重 箱的堆放位置，对于提高堆场利用率和提箱作业的效率有很大的影响。然而，虽 然有很多对堆场优化等类似的问题的研究，国内针对后方堆场进口箱的b a y 堆 存优化问题真正结合实际应用且易于为港口所使用的软件成果很少。本文根据实 3 中山大学硕士学位论文基于遗传算法的进口箱堆场b a y 位分配优化模型研究 际情况，采用计算机仿真技术，用二维b a y 位图模拟进口箱在后方堆场的动态 堆放过程，提出基于遗传算法的进口箱堆场& w 位分配优化模型。使其在卸船 作业过程中，协助后方堆场理货员进行有效的决策，为随机到达的进口箱分配合 理的b a y 位，具有重要的现实意义和研究意义。 1 3 国内外的研究现状 堆场管理是港口物流作业链中重要确是比较困难的一部分，因为堆场作业涉 及到各种随机的动态的复杂的因素，关联着港口物流的方方面面。为了能够经济 合理地使用堆场和有计划地进行集装箱的装卸工作，必须制定相关的堆存计划。 由于进口业务是港口的主要或重点业务，制定合理的进口箱堆存计划也就成为堆 场管理人员工作的重点。 进口箱堆存计划指的是在一定的集装箱操作难度级别上，在后方堆场当前的 堆垛状态下，为随机到达的进口重箱指定一个合理的b a y 位进行放置。该计划 只针对通用集装箱，冷冻箱、熏蒸箱等特殊集装箱数量比较少，并且有专门的特 殊区域存放，需另作计划。 国外有不少学者致力于集装箱堆场管理的研究并提出了一些有用的管理方 案和堆存方法： 1 ) k h m 通过考察不同码头堆场的布局及其对堆场作业过程中平均倒箱 次数的影响，建立了回归方程对集装箱堆存情况进行简化求解【6 】。k h k i m 等人 分别分析了集装箱按固定速率到达、按周期到达及动态到达的情况，以极小化总 倒箱次数期望值为目标函数，研究了堆存空间分配策略，并给出了一些算例1 7 l 。 k h 飚m 等人以最小化装船过程中的倒箱次数期望值为目标，考虑到堆场的布 局、当前堆场内集装箱重量的分布、以及到达的集装箱重量，提 f 了动态规划模 型来求解出口箱的堆存位置问题，从动态规划的最优解集中导出了快速决策树以 供实时决策【引。 劲t e l e b i b r a l l i m i 等人分析了集装箱堆场位置分配问题，提出可以为比分配 的空闲b a y 位早到的集装箱提供一个临时的缓冲区，通过对进门箱和出口箱在 不同堆放策略下所需的堆场面积进行比较，得出了相应的堆存工作量【9 1 。但是， 这篇文章集中在为集装箱指定堆场内的某一存放区域确没有真正的考虑怎样具 4 中山大学硕士学位论文 基于遗传算法的进口箱堆场b a y 位分配优化模型研究 体确定集装箱在堆场中的存储b a y 位。 3 ) i w a t 锄e b e 在重箱先于轻箱进行装载的原则下，采用动态规划模型，以翻 箱作业量最小化为目标，为出口集装箱确定在前方堆场的存储位置【姗。 4 ) b d e c 缸t i l h 和c f d a g a 舵。指出，为了较好地实现堆场的效益优化，需要 对集装箱情况进行估计，并将其作为堆场层高相对布局的策略函数从而在层高、 堆场的利用率以及堆场操作效率间达成平衡【1 1 l 。 5 ) p d e s t o n 和k o z 觚将不同作业顺序下如何确定最优堆存位置的问题抽象成 一个n p 难的混合整数规划( m i p ) 模型，提出基于遗传算法以最小化船舶装卸时 间的求解方法。其计算结果表明，堆场布局较合理的情况下作业顺序对船舶的装 卸时间没有影响，而当堆场利用率在1 0 5 0 之间变动时，装卸时间线性变动1 1 2 l 。 6 ) k h 1 【i m 等在预计堆场设备的操作能力的基础上，为动态到达的集装箱分 配堆场存储位置【1 3 】。 7 ) k h 磁m 和p 破研究了提高堆场空间利用率和装船作业效率的出口箱堆 放空间动态分配方法，提出了基本的混合整数规划模型。并通过算例比较了两种 启发式算法： 近视算法( m y o p i cm e t h o d ) 和次梯度法( s u b g 阻d i e n tm e t h o d ) 【1 4 1 。 8 ) m a r kb d u i n k e r k e n 等人提出了堆场堆码的最大剩余堆存空间( r e m a i n s t a c kc a p a c i t y ) 策吲1 5 j 。 9 ) b c a 0 和q u e b e ，j h o l g l l i i l - v e r s 和s j a r a d i a z ，c yc h e n 等人，采用 启发式规则讨论了堆场的集装箱的分配问题1 1 “1 8 1 。 目前国内这一领域的研究还不成熟，尤其针对后方堆场管理的研究几乎为 零，郝聚民等针对前方堆场，在图搜索技术和模式识别理论的基础上建立了随机 条件下的混合顺序作业堆场b a y 优化模型【1 9 1 。这种模型可以在堆场作业不倒箱 的情况下，产生符合装船配载要求的堆场状态。 由于集装箱堆存的实际情况极其复杂，很难得到解析解，国内外发表的有关 集装箱堆存的文献少之又少，并且绝大多数研究都以静态的方式进行【2 0 1 。到目 前为止，尚未有成功解决动态情况下后方堆场进口箱分配调度优化问题的文献记 载。目前国内在这些方面的研究几乎还是一个空白，大部分研究仅停留在对堆存 方式和堆存原则的定性讨论上。本文将尝试从动态角度，综合考虑提箱时间和提 箱目的地两个参数，根据堆场作业的实际情况进行数学建模，并以最小化倒箱次 5 中山大学硕士学位论文基于遗传算法的进口箱堆场b a y 位分配优化模型研究 数为目标用并行遗传算法对问题进行求解。 1 4 主要研究内容和解决的关键问题 本文在对佛山市新港码头堆场作业实际深入调研的基础上，结合国内各大港 口的目前的实际作业方式，集中于码头卸船作业过程中进口箱进入后方堆场 b a y 位分配问题的研究。针对某种场地类型，根据集装箱后方堆场作业的特点， 对集装箱后方堆场的b a y 位分配过程进行深入分析和问题描述。并在其基础上 建立符合实际堆场作业情况的数学模型，采用并行遗传算法对模型进行优化，为 每个随机到达后方堆场的进口箱求解出b a y 内合适的堆放箱位。 本文的主要研究内容如下： 1 ) 集装箱在后方堆场的存取过程研究。通过分析提箱作业过程中产生倒箱 的原因以及卸船作业和提箱作业的特点，采用不同提单的进口箱混合堆放在同一 b a y 上的堆存策略，提高后方堆场空间的利用率。 2 ) 同& w 内具体箱位分配策略。根据卸船作业过程中进口箱进入后方堆 场的具体过程，对进口箱堆场& w 位分配问题进行具体描述，建立进口箱堆存 过程的数学模型，并以最小化倒箱次数为目标，利用并行遗传算法对分配策略进 行优化及求解。 3 ) 运用遗传算法对模型进行优化求解。由于存在约束和边界条件，在具体 运用时，需要对遗传算法进行一定程度的改进，进而得出进口箱堆场锊位分 配的最终优化方案。以m a t l a b 软件为基础，利用s h e f ! f i e l d 大学提供的“g a t b x 遗传算法工具箱，进行实际的编程运算，求出该问题的最优解或满意解。最后通 过具体实例，将现行策略与本论文提出的策略分别应用于b a = y 位分配问题求解， 通过优化结果的对比来考察策略的优劣。 本文解决的关键问题如下： 1 ) 进口箱堆场b a y 位分配问题数学模型的建。其中包括以最小化倒箱次数 为目标建立的目标函数。 劲模型的优化求解。进口箱堆场b a y 位分配问题是多变量的非线性整数规 划问题，本文采用遗传算法进行模型的优化求解。 3 ) 编码方案的选择。使用遗传算法求解的第一步是根据具体领域的问题选 6 中山大学硕士学位论文基于遗传算法的进口箱堆场w 位分配优化模型研究 择与实际结合紧密的编码方案。由于二迸制编码和实数编码在求解实际问题时均 存在一定的缺点，本文采用兼顾二者优点的整数编码方案。 4 ) 约束条件的处理。实际应用中的优化问题般都含有一定的约束条件， 它们的描述形式各种各样。在遗传算法的应用中，必须对这些约束条件进行处理， 而目前还未找到一种能够处理各种约束条件的一般化方法。所以对约束条件进行 处理时，只能是针对具体应用问题及约束条件的特征，再考虑遗传算法中遗传算 子的运行能力，选用不同的处理方法。 1 5 研究方法 1 ) 对佛山市新港码头堆场作业进行实际深入的调研，查阅港口方面相关的 文献资料，分析提箱过程中产生倒箱的原因，提出问题，设定解决问题需要考虑 的各种实际因素，为数学模型的建立提供现实依据。 2 ) 建立符合大多数港口实际情况的进口箱堆场b a y 位分配问题数学模型。 3 ) 使用遗传算法对已建立的数学模型进行优化求解。如图1 1 所示，求解 优化问题的遗传算法基本构造过程为：a 确定决策变量和约束条件：b 建立优化 模型；c 确定编码方法；d 确定个体评价方法，即确定适应度函数及其变换方法； e 设计遗传算子和确定遗传算法的运行参数。 b a y 位优化问题描述 上 确定决策变量和约束条件 上 建立优化模型 上 确定编码策略和设计适应度函数 上 设计遗传算子和确定运行参数 士 实现遗传算法 图1 1 求解b a y 位优化问题的遗传算法构造过程 7 中山大学硕士学位论文基于遗传算法的进口箱堆场b a y 位分配优化模型研究 1 6 论文的组织结构 本文的主要内容安排如下： 第1 章介绍了课题的来源、研究背景及意义，简单讨论了国内外对该类问题 的研究现状、论文的主要内容以及所要解决的关键问题，说明了本文的研究方法、 技术路线以及论文的创新点和组织结构。 第2 章简要介绍了堆场的一些基础知识，结合实际对进口箱堆场b a y 位分 配问题进行了分析和描述，并对该问题建立数学模型。 第3 章首先简要介绍了遗传算法的基本思想、特点及理论基础，然后详细说 明了遗传算法的实施过程，应用遗传算法对问题进行了研究，最后给出了遗传算 法的编码实现和算例。 第4 章讨论了静态条件下的进口箱堆场b a y 位分配模型，并将其求解的结 果与本文提出的利用遗传算法进行动态求解的优化结果进行对比分析。 第5 章对全文进行了总结和展望。 8 中山大学硕士学位论文基于遗传算法的进口箱堆场b a y 位分配优化模型研究 第2 章进口箱堆场b a y 位分配问题数学模型的建立 2 1 堆场简介 2 1 1 堆场定义 集装箱堆场是港口码头区域内用于集装箱堆存的场所。码头堆场一般分为前 方堆场和后方堆场。前方堆场是用来暂存出口重箱的，也称为码头前沿，其作用 是当船舶到港之前，有计划有次序地按集装箱装船配载要求将出口集装箱整齐地 集中堆放。卸船时可以将进口集装箱暂时堆放在前方堆场，以加速船舶装卸作业， 减少船舶在港时间。集装箱后方堆场则是进行重箱或空箱交接、保管和堆存的场 所。卸船的进口集装箱一般堆存在后方堆场，以方便货主提箱。有些国家对集装 箱堆场并不分前方堆场或后方堆场，统称为堆场。 2 1 2 堆场位置标识 箱区：又称段位，在集装箱堆场上，按照集装箱相应的标准尺度画成有规则 的用以指示堆放集装箱的格状位置，并在& 蚪位上编写号码。 贝( b a y ) ：又称间位，集装箱在专用堆场上的纵列位置。由堆场的东面至西 面( 或由西面至东面) ，单号为：0 1 、0 3 、0 5 、，双号：0 2 、0 4 、0 6 、。 列位：又称行位，集装箱在专用堆场上的横排位置。编号的标准方法是从堆 场的南面至北面依此标明：0 1 、0 2 、0 3 、。 层位：堆场的堆垛列的层。编号的标准方法是从堆场的下层至上层依此标明： 0 1 、0 2 、0 3 、。 2 1 3 场地类型 使用不同机械作业的场地其堆存的层高限制不同。堆场根据使用的作业机械 不同，一般分为龙门吊场地( 轮胎龙门吊和轨道式龙门吊场地) 、堆高机场地、正 面吊场地等。 轮胎龙门吊场地使用轮胎龙门吊作业的堆场，一般每个箱区堆放6 列，3 巧 9 中山大学硕士学位论文基于遗传算法的进口箱堆场b a y 位分配优化模型研究 层高，每个b a y 放1 6 3 1 个箱子，主要堆放进出口重箱及部分空箱。 轨道式龙门吊场地使用轨道式龙门吊作业的堆场，一般每个箱区堆放6 列以 上，3 6 层高，主要堆放进出口重箱及部分空箱。 堆高机场地使用堆高机作业的堆场，码头堆存一般堆高6 层，主要堆放进出 口空箱。 正面吊场地使用正面吊作业的堆场，码头堆存一般高度为1 4 层，主要堆放 部分进出口超限重箱。 2 1 4 堆场的堆存标准及要求 根据堆场的总体规划在计算机系统里进行堆场的总体创建、定义和堆存状态 的设置及相应操作类别代码的定义。 堆场整体规划的集装箱基本堆存原则【5 1 ： 1 ) 进、出口箱原则上分堆( 可以按箱区、b a y 、列位) 放置： 劲空、重箱原则上分堆放置； 3 ) 非标准箱与标准箱分堆放置； 4 ) 2 0 英尺、4 0 英尺、4 5 英尺等不同箱型分堆放置； 5 ) 空箱按箱主、尺寸、箱型分堆放置( 堆高机场地) ； 6 ) 温控重箱、危险品重箱、超限箱等特种集装箱应放入专用场地堆存，并 按相关标准堆放； 7 ) 国际中转箱、内支中转箱、废品箱、海关查验箱、残损箱、污箱等有特 殊作业要求的集装箱应设置专门的堆存位置，并放入相应的场地堆存。 进口集装箱基本堆存标准【5 】： 1 ) 就近原则。保证各个吊机并行作业，尽量平衡各吊机的工作量； 2 ) 进口空、重箱原则上分开堆放； 3 ) 进口的非标准箱与标准箱要分堆放置； 4 ) 进口空箱按箱主、尺寸、类型分开堆放( 堆高机场地) ； 5 ) 进口冷、危、超等特种集装箱应放入专用场地堆存，并按相关标准堆放； 国进口的国际中转箱、内支中转箱、废品箱、海关查验箱、残损箱、污箱 等有特殊作业要求的集装箱应设置专门的堆存位置，并放入相应的场地堆存。 1 0 中山大学硕士学位论文基于遗传算法的进口箱堆场b a y 位分配优化模型研究 2 1 5 堆场作业类型 港口目前的作业关系可归纳为5 大类集装箱的作业：卸船作业、装船作业、 提箱作业、收箱作业、倒箱作业。实际的业务流程可分为7 种：进口卸船作业流 程、出口装船作业流程、提重回吉作业流程、提吉回重作业流程、堆场委托作业 流程、车运转入作业流程、车运转出作业流程。 卸船作业指集装箱船进入港口，集装箱从船上卸下，之后放入后方堆场的作 业。这里主要涉及集装箱在后方堆场进行堆放的原则，以使集装箱能放在最合理 的位置。 装船作业指集装箱需要及时( 提前) 堆放到前方堆场，然后在集装箱船靠岸后 将集装箱装入船的作业。 倒箱作业指由于受某些因素的影响而发生的对堆场内已经放置好的集装箱 进行重新堆码或放置。即把需要倒箱的集装箱从堆场的一个b a y 位搬移到另外 一个b a y 位，然后更新记录集装箱的堆场b a y 位。倒箱作业是一种浪费人力、 物力、财力的作业方式，因此必须对其进行必要的控制，这种控制也是堆场管理 的重要内容【2 2 1 。 提重回吉作业指重集装箱( 也称作重柜，一般是进口箱) 需要从堆场提取出 来，由集装箱卡车拖运，经过闸口放行后运送给货主，之后再将卸货后的空箱运 回堆场的作业。 提吉回重作业指空集装箱( 也称作吉柜) 需要从堆场提取出来，由集卡拖运到 货主现场进行装货，然后再将已经装货的重箱拖运回来，经过闸口检查，之后放 入堆场的作业。 提重回吉作业和提吉回重作业伴随着提箱和收箱两个作业过程。提箱作业过 程中，往往需要进行倒箱作业。 2 1 6 进口箱堆场倒箱的原因 进口箱在后方堆场的堆垛状态直接影响到提箱作业的效率和港口的经济效 益。压箱是指先提的集装箱被积压在后提的集装箱下面的情形，如果要提取下面 的集装箱，则必须先把上面的集装箱移走到另外一个b a y 位重新放置。因此如 果要提取的集装箱被压箱，在提箱过程中，就须要进行倒箱。 中山大学硕士学位论文基于遗传算法的进口箱堆场b a y 位分配优化模型研究 集装箱的压箱是由于港口堆场空间资源有限造成的。实际卸船作业过程中， 集装箱进入后方堆场的顺序具有一定的随机性，且没有制定合适的堆存计划。因 此，有时候不得不人为地将不同货主的集装箱混和堆放，这样在提箱作业过程中 就无法避免倒箱。 进口箱堆场堆存计划是指根据进口船舶的运载箱数，在后方堆场安排适当的 若干b a y 位以堆存该船舶载运的进口箱。该计划只针对装载一般货物的集装箱 ( 通用集装箱) 。而装载特殊货物的集装箱如冷冻箱和熏蒸箱等( 特殊集装箱) 需要 安排在冷冻区和熏蒸区等特定区域，须另作计划。 2 2 问题描述 本人对佛山市新港码头进行了3 个月左右的实际调研和分析，结合了解的目 前各大港口的实际设备情况，决定采用轮胎式龙门起重机系统进行后方堆场的集 装箱装卸作业。后方堆场被划分为若干个大堆区，每个大堆区又被划分为若干个 段( 即是小堆区) 。每段包括2 0 旬0b a y ，每b a y 一般放1 6 0 1 个箱子，本文采 用6 列4 层共2 4 个b a y 位。在大多数情况下，无论怎样堆放，都免不了倒箱p j 。 所以，在实际卸船作业过程中，为进口集装箱安排堆场b a y 时每b a y 要留出 2 0 个空b a y 位以方便b a y 内倒箱。本文采用2 个空b a y 位。因此，实际上， 每个& w 只有2 2 个b a y 位。如图2 1 所示为b a y 位的示意图。 图2 1b a y 位示意图 1 2 中山大学硕士学位论文基于遗传算法的进口箱堆场b a y 位分配优化模型研究 如图2 - 1 中所示t r 砚s f e rc r a n e 即是轮胎式龙门起重机，卸船作业过程中， 它负责把进口集装箱从t m c k 上卸载下来并放其到指定的箱b a y 上，提箱作业 过程中，则负责把指定b a y 位上的集装箱装到t r u c k 上以运送给货主。t r u c k 即 为集装箱卡车，负责集装箱的运输。s l o t 即为勘锊位。 为了建立出符合实际作业情况且行之有效的数学模型，在建立进口箱堆场 勘蟠位分配模型之前，我们需要了解卸船作业过程中b a y 位分配的流程和特点。 传统情况下，在卸船作业过程中，后方堆场的理货员根据个人经验负责进口 箱的堆场劭锊位安排，尽量将不同提单不同货主的集装箱分开放置在不同的 b a y 上，这样做明显减少倒箱的次数，但是也存在一定的问题： 1 ) 堆场使用缺乏整体规划。理货员只能考虑当前的堆放情况，而无法考虑 其他状况。 萄堆场空间的利用率低。某个提单或某个货主的集装箱通常比一b a y 的容 量小的多，这样每& 蚪都会浪费一些b a y 位，综合起来会是一个很大的数字。 3 ) 降低卸船作业效率。作业过程中，由于进口箱到达后方堆场的随机性， 轮胎式起重机可能会经常移动较大的距离，这样就增加了作业的时间，导致工作 效率的降低。 4 ) 增大轮胎式起重机的负担，增加它的磨损。 理想的堆存策略是将不同货主的箱子混合堆存，一b a y 不满尽量不将到达 的集装箱安排在下一b a y 上，在充分利用堆场空间资源的情况下，提高工作效 率，同时减少起重机的磨损。但是，这样的做法存在一个很大的风险，即是提箱 作业过程中很可能出现大量的倒箱操作，从而导致得不偿失的后果。 本文采用不同提单不同货主的集装箱混合堆放在同一b a y 的堆存策略。根 据集装箱提箱时间和提箱目的地距离堆场的远近这两个影响提箱顺序的主要因 素来制定进口箱堆存计划，为每一个随机到达的进口箱分配合适的堆存位置，这 两个因素的具体参数值要根据集装箱的实际情况来决定。 提箱时间是影响集装箱提取顺序的最主要因素。实际工作中，港口规定了进 口箱在堆场的免费堆存期限。货主一般在集装箱到港的有限个工作日即港口规定 期限内提箱，不同的港口存在不同的期限限制。本文将期限设定为3 个工作日内， 根据不同集装箱的提箱时间设定提箱时间段。若时间段的划分过细，则不利于堆 中山大学硕士学位论文基于遗传算法的进口箱堆场b a y 位分配优化模型研究 场的安排，容易造成堆场的堆存不均，造成堆存能力的浪费；若划分过粗，也不 利于安排堆位，很可能造成提箱过程中经常的倒箱、磨损机械。本文把一个工作 日以半个工作日为单位分为两个时间段，将提箱时间划分到不同的时间段内。 提箱目的地距离堆场的远近在一定程度上影响着集装箱提取的顺序。一般情 况下，不同货主的提箱目的地距离堆场的远近不同，根据距离的远近将集装箱划 分为不同的距离等级。同一提箱目的地的集装箱距离等级相同。距离等级若划分 过细，级别设立过多，则不利于堆场的安排，容易造成堆存能力的浪费；若划分 过粗，级别设立过少，也不利于安排堆位，或造成提箱过程中的倒箱、磨损机械。 因此，一般根据提箱目的地的个数将距离级别选定在1 q 级。 后方堆场堆存和提取箱都存在不同初始状态有不同操作难度的情况。这里将 操作难度进行定义和分级，如图2 2 所示，其中虚线框表示当前要堆放的位置， 称为目标位置。 难度等级1 难度等级3 2 3 建立数学模型 难度等级2 r 、 i卜 。? 黎，i 难度等级4 图2 2 堆放操作难度级别示意图 2 3 1 模型的假设条件 1 ) 所考虑的集装箱都是2 0 英尺长的标准通用集装箱。 不考虑超高柜，加长柜，开顶柜，以及其他作为特殊用途的集装箱类型。考 虑的集装箱的结构为封闭式，用以装载除液体货物、需调节温度及特种货物( 如 1 4 中山大学硕士学位论文基于遗传算法的进口箱堆场b a y 位分配优化模型研究 需冷藏或熏蒸的货物) 外的一般杂货或器械。 2 ) 同一条进口船舶载运的不同货主的箱子混合堆存在同一b a y 中。 3 ) 卸船作业过程中，对于已经堆存好的集装箱不进行倒箱。 4 ) 货主必须在约定的时间提箱，并且由港口根据约定时间安排车辆运送。 本文的算例中，约束在3 个工作日内提箱。考虑到实际情况，把3 个工作日 以半个工作日为单位划分为6 个提箱时间段，并按时间先后将其映射为6 个十进 制数字，如表2 1 所列。货主把提箱的时间段在进口舱单生成之前反馈给港口相 关人员。本文在研究过程中选取一个实际进口舱单，以该舱单上各个集装箱的提 箱时间顺序为主要依据( 提箱时间越晚，集装箱的优先级越小) ，考虑集装箱的提 箱目的地距离堆场的远近( 本文的算例中将集装箱距离堆场的远近划分为3 个级 别，距离越大，优先级越小) 等因素，对进口重集装箱在后方堆场的优化堆存进 行研究。 表2 1 时间段映射表 f 时间段 当天下午j魔二天上午第二天下午第三天上午 第三天下午魔四天上午 i 映射值 12345 6 5 ) 倒箱在同一& 裎内进行，不考虑倒箱的具体操作。 2 3 2 模型的参数和变量 模型参数设计： 1 ) 蹴政p ) - 仕2 ，3 ， 表示同一& 谨上所有堆垛列的集合。 2 ) 妣z 秘( s ) 一仉2 ，3 ，s 表示集装箱不同搬移阶段组成的集合。在取箱作 业( 提重回吉) 过程中，每搬移一个集装箱，为一个阶段，s 为总的要搬移的集装 箱数，也就是总的阶段数。 3 ) c 肠豁一仙2 ，3 ，c 定义集装箱的优先级别，数值越小，优先级别越高。 4 ) 口馏f 龇络扎2 ，3 ，口抛f 西幻8 以姗) 表示当前待分配集装箱的可行位置 个数的集合，最多有口w f b 勿加删个可行位置。 5 ) 肌动f o ，) - 绋 o ，1 2 ，f 表示第s 阶段b a y 上某堆垛列的高度。一 般情况下在后方堆场进口箱在相应的堆存区可堆成6 列4 层，本文即采用这种堆 1 5 中山大学硕士学位论文基于遗传算法的进口箱堆场b a y 位分配优化模型研究 存形式来研究，即f 不大于4 。 6 ) 暑砂觑f f 妣矧? ，炙) c ，o ，一l 定义进口b a y 位初始化状态，c 表示错 上第，堆垛列的第七层堆放了优先级位为c 的箱子，0 表示该位置为预留位置， 供b a y 内倒箱时使用，1 表示以后随机到达的集装箱的可行位置。 7 ) b 如c 七锄绍p ，厂) = 以，定义s 阶段某堆垛列厂上阻塞最大优先级别箱子的集 装箱数，即是第s 阶段需要提取该堆垛列某个b a y 位上的箱子时倒箱到其他列 的箱子数。称这些阻碍当前状态最大优先级别的箱子被提取的集装箱为阻塞箱。 阻塞箱的计算方法：在当前状态下，记录当前堆垛列的高度以，并记录优先 级最大的箱子位置为j ，计算以一，并更新堆垛高度坼j 及堆垛状态。以- j 的值即为阻塞箱的个数，如表2 _ 2 所列。 表2 2 第s 阶段& w 上阻塞箱状态 堆垛列 123456 2 33 23 2 2 12 36 22 13 2 3 22 36 33 26 33 2 5 26 15 l3 32 33 3 阻塞箱个数 11o020 如表2 2 中的二位整数表示集装箱的特征，十位代表该集装箱的提箱时间， 个位代表提箱目的地距离大小，整数值越大，提箱的优先级越低，即整数值大的 放在下面，整数值小的放在上面，否则在提箱过程中要进行移箱。如表2 2 中特 征值字体加粗的位置上的箱子为阻塞箱。 模型变量设计： 1 ) 助踟j 龇纪( s ，厂，) p ，吣记录b a y 上某个& “位状态。取值为c 时表 示第s 阶段第，堆垛列第f 层有优先级为c 的箱子，取值为o 时表示该位置无箱。 2 ) 孙妇d 比f ( s ，f ) 1 ，町记录集装箱的搬移状态。取值为1 时表示第s 阶段 第厂堆垛列第f 层的箱子被搬移，取值为0 时表示没有被搬移。 3 ) 而砌o ，f ) 仙阱记录集装箱的置入状态。取值为1 时表示第s 阶段第 ，堆垛列第f 层有箱子被置入，取值o 时表示没有箱子被置入。 1 6 中山大学硕士学位论文基于遗传算法的进口箱堆场b a y 位分配优化模型研究 4 ) 工0 ，厂，d ) 仉o 记录倒箱状态。取值为1 时表示第s 阶段集装箱从，堆 垛列被移到d 堆垛列，取值为0 时表示没有被移动。 5 ) 舷纪( s ，) ab 肠曲白括p ，厂) 表示第s 阶段第，堆垛列第歹层箱子的取 箱代价为该堆垛列当前状态下该堆垛列的阻塞箱数。 文中所涉及的取箱代价指的是当前状态下最大优先级别箱子的取箱代价，定 义最上层箱子的取箱代价为o 。 2 3 3 模型的目标函数和约束条件 曲地，d ) + 口o ， | ) ( 3 1 ) j e 氯呻孵，e 姒威缸砖 式( 3 1 ) 为目标函数，表示倒箱数最少。 勋妇耐 ， d + a 枥啦，d s l 热e 芗魄c g e ，r 5 绷如j s 蚴 ，)( 3 2 ) 式( 3 - 2 ) 表示某个特定阶段s 只容许一个箱子的移动，即只能取走一个箱子或 者移入一个箱子。 警盖j 未酗，婚镧 邕盖i 未釉严- ，r ，舻s q 圆 式( 3 3 ) 表示取箱