集装箱码头堆场出口箱堆放位置分配问题.doc

集装箱码头堆场出口箱堆放位置分配问题摘要：随着全球化步伐的加快和国家贸易的迅猛增长，集装箱运输已成为连接全球供应链至关重要的一环。港口作为现代物流系统中的重要节点，是海陆运输的枢纽，爱全球化制造和国家贸易中扮演着不可或缺的角色。堆场是集装箱码头的重要资源，是港口的重要组成部分，其堆场集装箱堆位分配优劣直接影响码头整体的运作效率。本文着重以集装箱码头堆场出口箱堆位分配为研究内容，分为出口箱堆场空间场位问题和具体储存位置分配问题，运用混合整数规划和混合序列叠加算法两个阶段进行探讨和研究。 关键词： 集装箱码头 储位分配 混合整数模型 启发式算法 一绪论1.1问题背景 随着全球经济一体化的迅猛发展，一方面企业的采购仓储销售配送等协作关系日趋复杂，全球采购全球销售本土化生产的趋势越来越明显。国家经济与世界经济的发展更加紧密地融合在一起。这对于物流服务的速度以及吞吐量提出了更高的要求；另一方面，经济全球化在本国企业带来新的机遇的同时，也带来了巨大的挑战。企业面临的竞争日益加剧，如何降低企业的生产经营成本以增强盈利能力摆在所有企业面前的一道难题，而如何通过科学的手段在不影响物流服务水平的前提下降低物流成本，成为了各个企业关注的焦点，也成为研究的热点。集装箱运输的不断发展，一方面导致目前国内许多集装箱码头超负荷工作，给集装箱码头运用管理人员的日常决策带来了很多困难。为缓解集装箱运输业发展所带来的压力，国内许多港口城市竞相规划和建设大型集装箱深水码头，规模和投资十分巨大，这些设施的建设和投入使用无疑对我国区域经济的发展有着重要的推动作用。另一方面，由于集装箱码头企业管理模式没能与时俱进，因而导致企业成本居高不下，通过能力低下，造成生产能力的浪费。这些因素的存在，严重制约集装箱码头企业竞争力的提升。线代集装箱码头高度机械化的作业特点决定了其固定设备的投资是十分巨大的，作为其经营主题的码头公司必须考虑企业的生存盈利问题，因此不可能无限制的投入机械设备。同时，集装箱码头即使规模再大，其堆场和泊位等资源也是有限的。因此，通过注重现有资源的挖掘，逐步提高资源的综合利用率，成为提升集装箱码头作业效率的根本途径。面对集装箱码头的大型化和作业的复杂化高效化，传统的基于人工经验的计划方式已经越来越难以提供一个合理优化的作业方案，因此对于集装箱码头作业效率起着关键作用的码头资源优化调度问题，越来越受到人们的重视，这对我国正在加速发展的集装箱码头行业有重大的意义，因此开展这方面的研究势在必行。1.2问题提出 在集装箱计划中最重要的目标就是保证岸边作业效率，减少船舶在港周转时间。进出口集装箱的生产作业流程是不同的，进口箱大批大港，提箱时间不可预测。出口箱由于随机到港，所以船方和港口需要根据箱子目的地和尺寸制定严格的堆存及船舶积载计划一确保船舶稳性，装船要求。二正文根据阅读相关集装箱码头堆场问题的学术研究，我们发现针对出口箱的堆场堆存位置分配问题没有较深入的研究。本文将运用系统方法论研究该问题。目的：通过充分利用堆场的存储空间，出口箱在堆场和码头前沿之间的高效运输与降低运输距离和倒箱操作量来提高出口箱的装船效率。2. 问题描述和解决方法 2.1 问题描述集装箱码头出口生产作业流程：外部集卡道口闸口堆场场桥堆场（具体位置）场桥集卡岸桥在船舶抵港前，船方会根据集装箱发往目的地分类编制粗略的配积载计划，提交给港口和航线经营人等相关部门企业，港口根据船方提供的积载计划和箱子信息制定详细具体的配记载计划。储存计划指定堆场具体位置的集装箱将要装载的船上的具体位置。制定计划时要满足船舶的稳性要求和减小岸桥和堆场设备的使用负荷。我们知道出口箱被储存在堆场街区中（BLOCK），每个街区有2030个场位（场贝位）组成，堆垛高度45层。每个场位一般安排并列的六列集装箱（如图一）。一般情况下出口箱在船舶离港前34天集港，为了提高装船效率集装箱需要被安排在最佳的位置。但是由于集装箱集港具有随机性，不能保证理想的出口箱的布局堆放。一种有效的方法是根据集装箱的目的地和重量在装船前在堆场进行分组作业。此种作业需要一个堆场缓冲区域，留作集港集装箱临时堆放，同时需要更多的装卸搬运工作量，通常情况是在保证船舶装船的前提下利用设备空闲时间进行操作作业。港方在进行港口布局规划时，因为陆域面积的限制此种方法通常不能实现。因此决定堆场中出口箱的合理堆放位置对于提高港口的生产率，降低船舶在港时间来说是至关重要的一个环节。 图一2.2 解决方法堆场堆放位置分配问题涉及每艘船舶出口箱的堆放场位空间问题和具体的堆放位置问题。以上问题通过以下两个阶段进行研究：（1） 场位分配：第一阶段决定出口集装箱的场位空间位置和每个场位数量以满足减少出口作业时集卡在堆场和岸桥之间的搬运时间和均衡每个场位的工作量。（2） 具体堆放位置：第二阶段在第一阶段分配的场位中决定具体的堆放位置，目的是减少装船作业的倒箱操作。 以上问题构建模型如下。3. 构建模型 3.1 出口箱场位分配 该问题运用混合整数规划模型（MIP）。场位和每个场位位置数量在计划期内决定。假设条件如下：（1） 因为装卸系统的分配问题超出本课题研究范围，故假定出口箱生产作业过程中设计的设备数量充足。（2） 预计到港船舶泊位分配已知。（3） 假定集装箱尺寸为同一规格；场桥的工作量按照处理的集装箱数量计算；集装箱堆场堆放原则不同尺寸的集装箱堆放在不同街区；因此我们的研究方法不受集装箱的规格大小的直接影响，不同尺寸的箱子能被分离成独立的问题。（4） 堆场中进出口箱不堆放在同一街区。（5） 通常船舶航线挂靠几个港口，不同目的地的出口集装箱不堆放在同一场位。因为同组的集装箱会被装到船舶的相近位置，所以该原则能够减少倒箱操作。4,5假设基于上海港的集装箱码头的真实情况。 符号定义 K堆场堆放出口箱的街区总数 B堆放出口箱的场位总数SA计划期内应该被分配位置的船舶的集合 SL计划期内将装船的船舶集合SS以前计划期已经被分配的船舶集合 S计划期内的所有船舶集合 S=SASLSS i场位i 1iBj船舶j k街区k 1kKCi场位i的堆存容量 bi场位i占的集装箱街区数量mj船舶j 能够装载的最大集装箱贝位数量 Dj船舶j挂靠的港口数量 jSAVio计划期场位i的集装箱初始数量 1iB Nj计划期内装往船舶j的集装箱到港堆场的预计数量 jSA Bj船舶j已经分配的集装箱堆放场位集合；jSSA 表示来自SA 不能分配dij场位i与船舶j的泊位之间的搬运运输距离决策变量xij计划期内堆放在场位i中装往j船舶的集装箱数量 jSAij1 如果装往船舶j的集装箱堆放在场位i,为1，jSA。；否则为0；对于jSSA ，ij在以前的计划期决定。Mj船舶j分配的总场位数 jSA ；jSSA ，在以前的计划期决定。Vi场位i 计划期末的总集装箱数量 Wk计划期内k街区的工作量目标函数：约束条件：目标函数和约束条件说明： 属于船舶j的出口箱i在场位堆放位置与岸桥之间的运输距离取决于每艘船舶分配的空间位置。（1） 第一个式子表示总运输距离最小；第二个式子说明计划期内每个场位堆放的集装箱数量不均衡；w1 和w2作为调整两个目标重要性的权重（2） 计划期末场位中集装箱的总数量（3） 保证每个场位的集装箱数量在允许的范围内，是每个场位允许堆放集装箱的密度。在实际生产操作中需要有剩余空间进行倒箱操作（4） 表示装往j船舶的集装箱占用的场位将在下一个计划期可用，jSL（5） 确保计划期内每个船舶的空间需求（6） 定义变量，（7） 保证装往不同船舶的集装箱不混合在相同场位（8） 表示属于船舶j的集装箱所在场位的数量（9） 确保船舶安排的场位数量大于或等于Dj （10） 规定用于装往船舶j的集装箱堆场的场位最大数量，能避免集装箱分布于太大区域（11） 计划期内安排的场位数量不能超过码头可利用的场位数量（12） 表示计划期内集装箱的工作量即处理的集装箱数量（13） 保证变量无负值（14） 0-1问题目标函数不是线性规划模型，故采取如下方法进行转换：定义P= Q= 目标函数转变为 约束条件增加如下：新的线性规划模型等价于原始的规划模型。 3.2 决定出口箱的具体堆存位置第一阶段的模型解决了发往不同船舶的出口箱的场位分配问题，该阶段研究的目的是合理在选择好的场位中安排集装箱，最终的布局能够使装船效率最大化。 3.2.1 问题描述该阶段出口箱会被按集装箱的重量级分组，我们基于上一阶段分配的场位提出一个方法论来解决具体的场位问题。目标是减少生产作业时的倒箱作业。假定在一个确定场位内，重箱先于轻箱装船。对于不同重量级的集装箱生产作业时会比较复杂。例如，有的场位的集装箱装船时，轻箱先于重箱装载。通常情况，重箱更可能先装船。因此如果重箱堆放在低层时，将会产生倒箱操作、 3.2.2 序列叠加决定出口集装箱堆场堆放场位中的具体位置是一个实时决策问题，很难找到全局优化程序去解决。序列叠加被广泛应用于实践当中，相同重量级别的箱子被堆放在同层或堆叠。图二展示了一个序列叠加的构架。每个位置的数字代表该处集装箱的重量级别，数字越大，代表的重量级别越高，垂直堆放考虑5个重量级，水平堆放考虑4个重量级，图中空格处是预留的集装箱堆放缓冲区域。由于集装箱集港的随机性，很难获得图二所示的理想贝位模型。在堆放过程中会发生大量的倒箱操作。例如，图二a中的垂直堆放方法，如果大量重箱先到达堆场，卡车通道附近很快就会被堆满，因此在轻箱到达时场桥堆箱移动会变得非常困难。对于图二b的水平堆放，同样重箱先到，必须将其放入缓冲区域等轻箱到港才能进行堆放在场位。 垂直堆放 水平堆放图二 序列叠加 3.2.3 混合序列堆加此部分我们提出混合序列叠加的方法来弥补上述序列叠加的不足，混合序列叠加能够获得到港集装箱任意最佳的储存位置。图三展示了运用混合序列叠加得到的一个理想的贝位配置模型。数字代表与上述相同，不在过多赘述。每列集装箱的重量级向上依次递增，重箱堆放在左上部分，轻箱在右下的位置。相同重量级的集装箱堆放在不同层或不同列，此堆放方法能够在集装箱进场决定位置时时获得更优化的结果。方法的另一个优点是装船作业时左上方取走后会留下合适的空间便于场桥操作，加快港口生产率。图三中场位集装箱重量级分9个集合，利用协调重量级的方法每个场位包括多个最佳的储存位置。例如，重量级为6的集合有4处最佳的堆放位置。该方法不局限于9个级别，管理调度人员可以根据所在港口集装箱量，货物种类等多方面考虑合适的连续重量级别。 图三 贝位理想配置图 3.2.4 混合序列叠加算法（HHSA）符号定义：Wmin,Wmax 集装箱重量范围 Wc 集装箱c的重量Lc 集装箱c重量级别 l 重量级别lSl 重量级为l的最佳集装箱位置集合 （xl,yl） 集合Sl 位置的几何中心 （xc,yc） 集装箱c的最佳存储 位置 （xcs,ycs） 集装箱c不属于集合Sl, 的可利用储存位置通过下列式子可以根据给出的集装箱c的重量来计算重量级别LC ：一般规则延伸为重箱堆放位置在左上，轻箱的堆放位置在右下。根据问题属性可以得到解决问题的优化方案。4. 算例应用略5. 结论集装箱码头堆场堆放位置分配问题直接与生产作业效率相关，集装箱进港的随机性给问题的解决带来了很大难度。本文将问题转化为两个阶段，第一阶段主要解决出口