更多免费论文请到海员论坛下载 http:/bbs.haiyuan5.com动态负载下堆场资源规划的在线决策动态负载下堆场资源规划的在线决策白治江(上海海事大学 信息工程学院，上海 200135)摘摘 要要：以集装箱船在港时间最小化为目标，研究了动态负载下码头堆场资源配置的在线 决策问题。采用层次分解技术将复杂问题从逻辑上分解为几个目标一致的子问题，从而高 效可靠地做出决策。实验结果表明，新决策方案能有效地提升码头作业效率。 关键词关键词：动态负载，在线决策，层次分解，资源配置Online decision solution with dynamic workload in container terminalBAI Zhijiang(Information Engineering College, Shanghai Maritime Univ., Shanghai 200135, China) Abstract: With the minimization of ship turnaround time as the ultimate goal, the online resource allocation decisions in the terminal yard are studied under the condition of dynamic workload. The hierarchical decomposition technique is adopted to separate the complex problem into several substitute decisions logically, thus these decision can be made effectively and efficiently. The experiment result shows that the new solution can improve the terminal handling efficiently. Keywords: dynamic workload, online decision, hierarchical decomposition, recourse allocation1 引言引言为了应对未来挑战和有效处理复杂操作，采用智能决策支持工具是现代化集装箱码头 的必然选择。大型码头都具有为决策系统提供可靠数据的信息基础设施，所需要的是简单 实用的决策模型和求解模型的高效算法。Van Hee 等开发了一个规划码头效能的决策支持 系统1，但系统关注的是码头设计建设阶段的决策，而与码头日常决策无关。Roux 研究了 存储空间需求和道路拥堵问题2，Kim 等研究了空间需求和场桥配置问题3，Kim 等研究 了集装箱预编排策略4，Liu 等研究了完全自动化的系统5，其中场桥和自动引导车 （automated guided vehicles）完全由计算机控制。 但这些已有的研究都未考虑码头负载随时间变化的重要特征。码头在特定时段内的负 载就是该时段内处理的集装箱数量，它等于如下 4 个变量的和：（1）从船上卸载并存入堆 场的箱；（2）从堆场取出并装船的箱；（3）由外卡运来存入堆场的箱；（4）被客户从堆 场提走的箱。实际生产中，以上这四个变量在未来的任意一个时段内都具有不确定性，导 致码头负载随时间的分布并不均匀。概括地讲，码头负载有如下特点： 由于天气和交通状况等不确定因素的影响，负载在时间上的分布是不均匀的。 有时作业次序无法控制，即不知道作业准确到达的时间。 作业一旦到达就立即执行，一般情况下不能延误。 本文研究码头负载随时间动态变化的条件下，堆场资源规划的在线决策问题。在建立 模型和选择算法时，既要反映负载动态变化的特征，又要保证在实际使用中容易实现和维 护。本文其余内容安排如下：第二节，问题描述；第三节，空间分配、集卡指派和运行路 径的在线决策；第四节，仿真实验结果；第五节， 结论。基金项目：上海海事大学科研基金项目(20100090)作者简介：白治江(1962-)，男，陕西榆林人，博士，副教授，人工智能、系统工程，(E-mail)zjbaicen.shmtu.edu.cn更多免费论文请到海员论坛下载 http:/bbs.haiyuan5.com2 问题描述问题描述场桥为 RMGCs（rail mounted gantry cranes）的堆场其典型布局如下：堆场由箱区组成， 箱区中集装箱堆成 6 列，每列中一般包括 20 个以上的堆，每堆有 5 层，如图 1 所示。一 一 (bay)一 (stack)一 一 (slot)6一 (lane)一 一 一 一 (block)一 一 一 一 (RMGC)图 1：堆场结构示意图。左图：含有 12 个箱区（block）的堆场；右图：箱区内的术语说明外卡将出口集装箱通过门口运到堆场指定箱区存放，场桥把外卡上的集装箱移到存放 箱位；当出口箱装船时，场桥把集装箱从箱位取出放在内卡上，并运到岸桥装船。出口箱 流程由图 2 表示。进口箱流程的运行过程与出口的流程刚好相反，由图 3 表示。客户轮船岸边堆场大门 外卡内卡外卡岸桥取箱并装船到场并存放图 2：出口箱流程客户轮船岸边堆场大门 外卡内卡外卡岸桥卸箱并运到堆场客户提箱并运走图 3：进口箱流程集装箱码头 2 个最重要的指标是（1）船的在港时间 T（即平均装卸时间） ；(2)岸桥的 平均效率 =（装卸箱总量）/（岸桥的总工时） 。优化目标是使 T 最小化， 最大化。显然 当 提高，T 减少，反之亦然。其他重要优化指标还有：道路拥堵最小，集卡和岸桥的平 均等待时间最小，堆场内平均翻箱数最少等。 码头的日常操作是由一系列具有内在联系的决策组成的。由于决策的多样性和多目标 性以及决策过程的不确定性和复杂性，要想通过一个数学模型获得所有决策结果是不可能 的。所以本文采用层次分解办法逐个处理各个决策子问题。当然各子决策的目标函数要与 主要指标一致，即有助于降低轮船在港时间，提升岸桥效率。优化上述性能指标涉及如下 一系列资源配置决策：D1. 给到港船分配泊位决策；D2. 给靠港船分配岸桥决策；D3. 外 卡到港的预约决策；D4. 集卡运行路径决策；D5. 门口和泊位处集卡指派决策；D6. 堆存 空间分配决策；D7. 场桥调度决策；D8. 给岸桥的内卡配置决策。 与堆场资源规划相关的问题包括 D4，D5，D6，D7 和 D8，因篇幅所限本文先研究更多免费论文请到海员论坛下载 http:/bbs.haiyuan5.comD4，D5，D6 和 D8 的在线决策方案，D7 作为后继研究。 码头以 8 小时为单位 3 班倒，选择规划时段长度需考虑两个因素（1）能相当准确地估 计规划时段内的总负载；（2）总负载在规划时段内应尽可能地均匀分布。实践表明 4 小时 规划时段较好地满足这两方面的要求。时段太短，则负载估计精度差；时段太长，则负载 分布不均匀，以 4 小时为单位，一天可分为 6 个规划时段，在每个时段的末尾，使用最新 信息为下一个时段形成一个新的规划。 决策时的输入数据分为静态数据和动态数据，静态数据指在任何规划时段内都不变的 系统参数，如堆场的道路网络，箱区数及其容量，岸桥数和场桥数等，需要时直接访问数 据库即可。动态数据指随操作而变化的值，如设备的当前位置，每个箱区内存放的箱数， 每个箱存放的位置等。这些动态数据都被实时地更新，其当前值可从信息系统中获取。3 空间分配、集卡指派和运行路径的在线决策空间分配、集卡指派和运行路径的在线决策码头堆场将空间分配、门口和泊位处集卡指派以及路径决策三个问题紧密地联系在一 起，因此将它们作为有机整体放在一起研究。用一个有向图 G 表示码头内的运输网络，方 法是将门口、泊位、箱区和交叉路口设为节点，用一条有向弧（代表运输道路）连接两个 节点，若两个节点之间道路是双向的，则用两条有向弧连接。 如前所述，决策的规划时段设为 4 小时（即一个工班的前半段或后半段） ，决策模型的 输入数据包括道路网络图 G，船期数据（到港时间，装卸负载） ，装卸计划，以及下列数据：表 1：决策模型的输入数据b码头泊位数m堆场内箱区的总数 ki箱区 i 的存储容量，mi 1ESi(p)存于箱区 i 内在 p 时段装船的出口箱数，mi 1(p)ESd i在 ESi(p)中送往泊位 d 的箱数，bd 1ES(p)= m1i(p)ESi在 p 时段装船的出口箱总数 ISi(p)存于箱区 i 内将在 p 时段被客户提走的进口箱期望数，mi 1IS(p)= m1i(p)ISi在 p 时段被客户提走的进口箱期望总数(p)dP 时段在泊位 d 的船上卸载的进口箱数IM(p)= b1d(p)IMdP 时段从船上卸载的进口箱期望总数，EX(p)p 时段到港的出口箱期望总数XITi(t)t 时刻在箱区 i 内等待场桥服务的内/外卡数。其中，EX(p)和 IS(p)是根据预约数据库和过去的经验分布综合获取的期望值，因为并不 是所有的客户都在送箱或提箱之前与码头预约时间。 3.1 空间分配决策描述空间分配决策描述 设 p 是当前时段，下面讨论为 p+1 时段到港集装箱分配存储空间的决策过程。每一个 新到的箱必须分配特定的空间存放，理想的分配策略应当使道路网和箱区内的拥堵最小，更多免费论文请到海员论坛下载 http:/bbs.haiyuan5.com并使总的翻箱数最小。如果一次性为新到的 EX(p+1)+ IM(p+1)个集装箱分配具体箱位将产 生一个难于求解的大型数学模型6。为了降低求解复杂度，按照层次划分的方法将整个空 间分配过程分为三个阶段。 （1）第一阶段：箱区分配 本阶段的任务是确定箱区 i 在 p+1 时段的集装箱配额 xi(p+1)（即 p+1 时段存于箱区 i 内到港的进/出口箱总数） 。第一阶段只为各箱区确定配额，具体哪个箱将存于哪个箱区内 由第二阶段的指派策略确定。 （2）第二阶段：集卡指派策略 本阶段要确定门口处外卡和泊位处内卡到堆场箱区的指派策略，使得在本时段末各个 箱区内得到的集装箱数等于第一阶段确定的配额，同时在箱区和道路中的拥堵最小。指派 策略应保证将相继进入堆场的集卡指派到分布范围较大的不同箱区内，以便每个箱区在下 一集卡到达前有适当时间处理已到的集卡。同时集卡应派往不同方向以保证道路运输量在 各个方向上均匀分布。否则，若连续地向一个箱区指派集卡，该区内马上就会发生严重拥 堵。 （3）第三阶段：箱位分配 对每个到达箱区 i 的箱 A，确定 A 的最优存放位置，目标是在提取 A 下面的集装箱时， 对 A 的翻箱次数最小。3.2 三个阶段的具体实现过程三个阶段的具体实现过程 （1）饱和系数平衡法解箱区配额问题（第一阶段） 该算法的基本依据是，设第二阶段的指派策略将相继到达的集卡分散到整个堆场，若 所有箱区的饱和率保持近似相等，则交通拥堵会达到最小，因为交通量将均衡地分布 于堆场内的所有路段上和箱区内。模型的决策变量和参数说明如下： xi(p)：p 时段内箱区 i 的配额。 Fi(p)：p 时段开始时箱区 i 的饱和率。：p 时段开始时整个堆场（包括所有箱区）的饱和率。)(pGi(p)： p 时段开始时存于箱区 i 内的箱数 则确定决策变量 xi(p+1)的过程如下： Step1：用当前 p 时段的数据计算 p+1 时段开始时各箱区的饱和率iiiiiiiii/kpxpISpESkpF/kpGpF)()()()() 1() 1(Step2：用 step1 的饱和率，p+1 时段新到的和将被提走的集装箱期望数，计算各箱区的 配额，使得各箱区的饱和率在本时段末（p+2 时段开始）尽可能地相同。在 p+2 时段开始 时整个堆场的饱和率是 m1im1i