出口箱随机入港下的箱区选择与箱位分配协调调度.docx

出口箱随机入港下的箱区选择与箱位分配协调调度陈超， 台伟力， 杨逸蓝， 曾庆成（大连海事大学 交通运输管理学院，辽宁 大连 ）摘 要：针对出口箱随机入港下的分散堆放与随机选位对集装箱卡车行驶 和 场 桥 取 箱 作 业 的 影 响，提出了出口箱的箱区选择与箱位分配协调调度问题 ，并以箱区位置、箱量分配、箱位分配为决策 变量，以集装箱卡车接运单位 平均作业时间最少、场 桥作业成本最低为目标 ，构 建了出口箱 箱区选择与箱位分配两阶段非线性整数规划模型 设计了基于遗传算法的双层启发式算法 ，上层用 于箱区搜索，确定出口箱堆放箱区及箱量分配 ；下层用于箱位搜寻 ，并依据场桥取箱顺序规则 ，确定 具体堆放箱位或重选堆放箱区 通过算例分析结 果表明 ：与 集中入港下集中堆放相比，对 出口箱随 机入港下分散堆放的箱区选择与箱位分配进行协调调度同步优化 ，可 以减少单位 平均装卸 时间，并显著降低堆场作业成本 ，模型与算法可行有效 关键词：港口物流工程；集装箱码头；堆场作业；随机入港；箱区选择；箱位分配 中图分类号：文献标志码： ， ， ， （ ， ，）： ， ， ， ， ， ， ：； ； ； ；收稿日期 ：基金项目 ：国家自然科学基金资助项目（）作者简介 ：陈 超（），男 ，辽宁省大连市人 ，教 授 ，主要从事集装箱物流系统优化研究 电 话（）：；：第 期陈超，等：出口箱随机入港下的箱区选择与箱位分配协调调度出口箱箱区选择和箱位分配是决定集装箱卡车（集卡）行驶路径 与场桥取箱次序的关键环节 受 船 舶停靠泊位、装卸作业方法等因素影响 ，箱区选择不 同，箱位分配则不同鉴于两者相互影响、相互作用， 对码头装卸作业系统运行效率和运作成本影响的复 杂性，故只有统筹考虑、协调调度、同步优化，才能保 证码头堆场调度决策的科学性与合理性应对出口箱的箱区选择与箱位分配问题 ，产 业 界常规做法是，根据船舶靠泊计划与装卸作业计划 ， 在船舶抵港前，采 用集中入港、集 中堆放、按 序整理 的策略来解决的然 而，近 年来，随 着港口间竞争的 日益激烈，为了改 善出口箱集中入港给航运公司与 货主带来的提前截载与集中送货等不便 ，克 服由此 引发的港区周边交通压力过大等弊端 ，一 些港口开 始采用出口箱随机入港策略来改进服务质量 、提 升 竞争能力但在随机入港策略下 ，由于航次出口箱量 无法提前确定，码 头难以为过早入港的出口箱提前 预留整块箱区、实施集中堆放，只能根据堆场箱区的 空闲情况进行分散堆放 ，这无疑将给码头出口箱的 箱区选择与箱位分配带来巨大的难度 ，同 时也给码 头生产作业的调度决策提出了严峻的挑战目前，国 内外关于集装箱码头堆场作业调度的 研究已有很多，但 大多都是针对出口箱集中入港下 的相关 问 题，如 场 桥 与 任 务 分 配 调 度、箱 区 选 择、箱 位分配和 取箱顺序优化等，采 用 的 方法与 技 术 有 整 数 规 划、动 态 规 划 及 启 发 式 算 法 等，等就出口箱 随机入港下堆场堆存问 题，构建了以集卡 行驶路径最短为目标的混合整数 规划模型，并设计 了一种混合顺序堆存算法进行求 解，但仅考虑了出 口箱箱区位置与船舶停靠泊位的 关系同样，还有许多研究考虑了集卡在单船独立装 卸作业下的行驶距离 ，但缺乏对多船交叉混合装卸 作业下的行驶距离研究，；张艳伟等提 出 了从计划分配到动态分配的三阶段箱位分配法 ，其 堆放原则采用重箱压轻箱的策略 ，但重箱过多将导 致底层轻箱受损，缺乏对箱子重量等级的划分 ；陈超 等在研究交叉混合装卸 作业时 ，虽 然涉及了两船 交叉混合装卸作业下的箱区选择问题 ，但 欠缺对舱 内箱与甲板箱装船作业特点的考虑 、以 及这些特点 对出口箱箱区选择的影响 ，同时也 缺少对场桥装船 取箱操作与船舶积载安排协调要求的考虑本文在已有研究的基础上 ，针 对出口箱随机入 港下的分散堆放与随机选位对集卡行驶和场桥取箱作业的影响，提出 了出口箱的箱区选择与箱位分配 协调调度问题，并 以箱区位置、箱 量分配、箱 位分配 为决策变量，以集卡接运单位 平 均 作 业 时 间 最少、场桥作业成本最低为目标 ，构建了出口箱箱区 选择与箱位分配两阶段非线性整数规划模型 同时， 设计了基于遗传算法的双层启发式算法 ，对 模型进 行同步优化，并通过算例实验，验证了模型与算法的 有效性箱区选择与箱位分配模型 问题描述由于船舶舱盖宽度通常为多个箱宽 ，码 头在进 行装卸作业时，只能先对甲板箱进行卸船作业 ，再对 舱内箱进行装卸作业 ，最后再甲板箱进行装船作业 对甲板箱作业时，码头可能会采用单船独立装卸方 式作业，即集卡固 定在目标船与出口箱区或进口箱 区间行驶，故称作业线法；也可能会与其他船采用多 船交叉混合装卸作业 ，即 集卡灵活在两船与一个出 口箱区和一个进口箱区间行驶 ，故称作业面法而对 舱内箱作业时，码 头即可采用单船边装边卸方式作 业，也可以与其他 船采用多船交叉混合装卸方式作 业，集卡固定在目 标船舶或灵活在两船与一个进口 箱区和一个出口箱区之间行驶 根据上述码头作业 特点和作业方法，对于每一个随机入港的出口箱 ，码 头只能依据船舶计划停靠泊位 、堆场箱区空闲情况 首先，识别其目的港，尽可能将同一目的港的箱子堆 放在一起，再根据其重量，判断其属于甲板箱还是舱 内箱，以及 是 否 存 在 与 其 他 船 进 行 交 叉 作 业 ，如 存 在，还要考虑交 叉作业船出口箱的堆放分布 然 后， 选择某一箱区的空闲处 ，按规则进行堆放，如果按规 则没有合适箱位，要么在该处找一个不太合适箱位 堆放，待装船取箱时再进行倒箱 ；要么另选一个有合 适箱位的箱区空闲处进行堆放由此可见，在随机入港策略下，出口箱的箱区选 择已经不能仅采用集卡行驶路径来进行度量 ，而 需 要综合运用集卡行驶路径与集卡重箱载箱率及等待 时间来进行度量，问题则应视为集卡接 运单位 平均运行效率的分配问题 同样，箱位分配问题也需 要考虑对倒箱作业的影响 ，并视为场桥取箱作业成 本最小的箱位分配与取箱顺序的规则设计问题 ，如 图给出的以场桥作业成本最小的甲板箱与舱内箱 重量分配及取箱顺序规则示意图 图中，船舶大小不 同、航线货种不同，甲板箱与舱内箱的重量划分会有上海交通大学学报第 卷（）甲 板箱（）舱 内箱图 箱区内某一贝位甲板与舱内箱重量分布与取箱顺序规则示意图 所不同由于箱区选择与箱位分配相互影响 、相互制约，共同决定着出口箱的最终堆 放结果 因 此，集 装 箱码头出口箱的箱区选择与箱位分配协调调度问题数 ，可构建某一目标船 出口箱的箱区选择模型 如下： 实质上是一个集卡接运单位 平均运行时间最 少与场桥作业成本最小的箱区选择与箱位分配复合式中： （ ）（）同步优化问题 ， （） 箱区选择模型 根据班 轮 航 线 船 舶 抵 港 时 间的确定性和规律 ， ）性，码头通常都为抵港船舶预先指定靠泊位置 、安排 ，（ 靠泊时间，以 及 船 舶 甲 板 和 舱 内 作 业 时 间 假 设 为某时段码头靠泊船的集合，为 目标船， 为与目，（） ，（） （）标船进行交叉作业船 ， ； 为目标船 的靠 泊位置， 为船 的靠泊位置； 和 分别为目标 ， ， （）船进行甲板和舱内作业时与船 的交叉作业量； （）为目标船进行甲板作业时船 岸桥移动的贝位数； ， ， ， ， 为出口箱区空 闲 处 的 集 合，； 为 箱 区 的可堆箱量， ， ，和，分别为 目标船在进行舱内和甲， 板作业时 箱区中与船 交叉作业的箱量； 为场桥大车行驶速度； 为场桥小车取箱和倒 箱 单 ， （），位时间； 为 单 位 贝 位 长 度；和 ，分 别 为 个 （）， 和 （）分别为个场桥在箱区 内第 次贝作业的倒箱次 ， （） 数；（，）和（，）分别 为目标船进口箱区与出口箱区位置坐标 ，（ 和 （ 分 别 为 （ ）， ） ， ） ， 船 进口箱区与出口箱区位置坐标 ； 为 集 卡 在 码 头内安全行驶速度； 和 分 别 为 岸 桥 大 车 移 动 ，（）速度与小车运行速度； 和 分别为目标船甲板和舱内待装箱量；当目标船进行甲板作业时 ，船 参与 交叉装卸船作业， 为 ，否 则为 ；当 目 标 船 进 行 舱内作业时，船 参 与 交 叉 混 合 装 卸 船 作 业 ， 为 ，否则为；当船 参与交叉装卸混合作业时，如 果， （）， （） ， （）， （）目标船的出口箱 区 是， 为 ，否 则 为 ；当 目 标（）船进行舱内作业时，如 果集卡去船舶 的接箱时间（， ， ） 小于等待岸桥小车往返运行时间 ， 为，否则为， ， ， ， ，（） 以集卡接运单位 平均运行时间最少为目标函 ， ， ， 第 期陈超，等：出口箱随机入港下的箱区选择与箱位分配协调调度式 （）为 目 标 函 数，即 最 小 化 集 卡 接 运 单 位 的平均运行时间；式 （）为 集卡在目标船与其 他船对甲板箱进行面作业时行驶与等待岸桥移动的 ， ， （， 总时间；式（）为目标船对舱内箱进行单船装卸混合 作业或与其他船进行交叉装卸混合作业时的集卡行，）（）驶与等待岸桥移动的总时间 ，其中 等待时间取决于 集卡在原送箱船岸桥下的等待时间与去其他船岸桥 下的行驶时间大小；式（）为集卡等待场桥的倒箱时， ， （） （， ，） （）间；式（）为集卡等待场桥大车移动的时间 ；式（）为 目标船进行舱内和甲板作业时 ，可 以与同一条船进 （ ， （ ） ） 行交叉作业；式（）和（）为甲板与舱内作业量约束 ； 式（）保证了至少有一条船舶与目标船舶甲板 、舱内 （ ）（， ） 进行交叉混合装卸作业 ；式 （）和 （）为 可进行交 叉混合装卸作业箱量在各箱区的分布量 ；式 （）和 （， ） （）（）为可进行多船交叉混合装卸作业箱量所对应的（ 堆放箱区；式（）和 （）分别为箱区内待装甲板箱 ， ）（ ） 量和舱内箱量与实际装船作业量相等约束 ；式 （）为各箱区最大可堆箱量约束 ；式 （）为 变量取值约（， ） ）束（， ）（ 箱位分配模型 （）（，）表示堆场 箱区某一贝位的第 列（， ） 层箱子质量， 表示船上某一贝位 的第列 ， ， ， ，（）层箱子质 量，其 中 、，由 车 道 侧 起 算，而、，由 底层起算； 表示箱区 内 总 贝 位 数 量； 为 每 个 贝 位 的 箱 位 数； 和 分别表示装甲板和舱 内的取箱顺序 ； 表示船 舶舱高； 表示箱高； 和 分别表示船舶舱内和 甲板的堆箱宽度，用装箱列数表示 ； 和 分别表 示船舶舱内和甲板堆箱高度 ，用 装箱层数表示； 和 分别为场桥大车单位时间行驶成本和场桥小车单 位时间运行成本，则以场桥作业总 成本为目标函数 ，可构建堆场箱位分配模型如下 ： ， ， ， ， 式中：（，）（，） （，）（，） （，）（，）（，）（，） 式（）为目 标函数，即场桥装船取箱时的大车 行驶成本与小车运行成本之和 ；式 （）和 （）为 甲 板和舱内箱堆放规则约束 ；式 （）和 （）为 甲板和 舱内箱取箱 规 则 约 束 ；式 （）为 场 桥 倒 箱 次 数；式（）为两台场桥 间距约束；式 （）为每个箱区的贝 位数量；式（）为 船舶积载重心高度 满足稳性要求 ， ， 约束；式（）为船舶积载均衡约束，即船舶横倾不得 （）超出安全范围；式（）为变量取值约束（， ） 个阶段启发式算法（ ）， ，（）， ，（） （，）， ，（） ， （，） ， ，（）针对出口箱的箱区选择与箱位分配协调调度决 策内容及关联关系，本文设计了基于遗传算法的双 层启发式算法，算法流程如图所示下层用于求解 箱位分配，将结果反馈到上层，求解箱区选择 编码及染色体描述上层染色体采用字符串对染色体编码 每 条染 色 体表 示种 箱量分配 ，染 色体长度 可用箱区上海交通大学学报第 卷数可参与混合交叉作业的船舶数 ，奇 数位点表示 甲板箱量，偶数位点表示舱内箱量 假设可用箱区数 为，可参与混合交叉作业的船舶数为 ，则 染色体长度为，如图所示图 中，前、中、后 个位点之 和分别是船舶，的交叉作业量下层染色体采用顺序编码方式每 条染色体表示箱区每个贝位的箱位分配 ，染色体长度即为每个 贝位的箱位数，每个位点的值代表箱子重量 假设每 个贝位如图所示有 个箱位，按 从左到右、从 上 到下分别给 个 箱 子 编 号，则 对 应 染 色 体 长 度 为 ，如图所示 适应度函数鉴于本文所求的目标函数是最小值 ，因此，分别 取模型个阶段目标函数的倒数作为适应度函数：（）（）（）图 算法流程图 烄， 第阶段（） 烅图 上层染色体示意图 烆， 第阶段 选择、交叉及变异操作图 下层染色体示意图 数；为最大进化次数； 为，区间的随机数采用轮盘赌法选择个体 ，个体的选中概率设为 （） 终止规则算法进行到预先设定的进化代数时 ，终止（） ， ，（）（）式中： （）为 个 体 适 应 度 值； 为 种 群 个 体数目交叉操作采用实数交叉法 ，第 个染色体 和 第 个染色体 在 位的交叉操作为：算例分析设定目标船舶，作 业贝位为舱内 层高， 列宽；甲板层高，列宽该航次甲 板装箱量 ，舱 内 装 箱 量 ，船 舶 抵 港 和 作 业 时 间 计 划及码头堆场箱区分布平面如图 所示图中，可进 （） （）式中， 为，区间的随机数（）行装卸交叉作业的船舶，其 中 属 于同一条船舶单位泊位长度为 ，箱 区长度与 泊位长度对应，各箱区的街间距 为 ，进 口箱区变异操作通过从种群中随机选择个体的随机点 进行变异，产生更 优个体，以维持种群的多样性 ，第 个个体的第 个基因 的变异方法： （ ）（）， 前排街距泊位岸线距离为，船舶，分别 计划靠泊， 号泊位，各船对应的进口箱区编号 分别为，出 口 箱 区 可 用 区 段 编 号 分 别 为： ，各 自的堆存容量分 （ ）（）， （）别 为： ， ，式中：、 分 别 为 基 因 的 上、下 界；（）（）； 为一个随机数； 为 当 前 迭 代 次， ， ， ， ， ， 第 期陈超，等：出口箱随机入港下的箱区选择与箱位分配协调调度， ， 岸 桥 小 车 与 大车 运 行 时 间 分 别 为： ， 集卡 安全行驶速度 场 桥大车行 驶速度 ，场桥 小 车平均取箱时间 ，平 均 倒 箱 时 间 堆 场贝位的箱位数，即，贝 位单位长 度 场桥大 车行驶成本 元，场 桥小车运行成本元图 船舶作业泊位 时 间 箱 区示意图 目标船出口箱的箱区及箱量分配如图 所示 图中，船舶，参与进行交叉作业的箱量分别为 ： ， ， ， ，即 装甲板箱时，船舶仅与船舶发生交叉作业；装舱内箱时，船舶采用独立混合装卸作业 选择的出口 箱箱区区段 为 ，相 应的 堆 放 箱 量 分 别 为 甲 板 箱 ，甲 板 箱 ，舱 内 箱，舱内箱图 各箱区箱量分配结果 同时，求 得 集 卡 行 驶 总 时 间 为 ；等 待时间为 ，单 位 平 均 搬 运 时 间 为 并得集卡行驶路径结果如表 所示表 集卡优化路径 行驶路径集卡行驶 时 间集卡等待 时 间集卡运行 总时 间操作箱 量平均单箱搬运 时 间甲板箱舱内箱出口箱区 船舶 船舶 进口箱区 出口箱区 船舶 船舶 进口箱区 出口箱区 船舶 船舶 进口箱区 出口箱区 船舶 船舶 进口箱区 合计 表给出了出口箱集中入港与随机入港下的箱 区位置不同 获 得 的 单 位 作业效率计算结果可见，随着集中入港的箱区离泊位岸线越远 ，随机入 港相对集中入港的优化效果越明显 因此，出口箱随上海交通大学学报第 卷机入港策略下的优化结果 ，不仅对 不同时间靠泊的 船舶来说可获得同样高的装卸作业效率 ，而 且还可 以使出口箱区的前后方箱区得到均衡利用 ，提 高了 出口箱区整体空间的使用效率 考 虑到采用集中入 港策略，码头还需 要对出口箱按作业顺序单进行再 整理，码头实际上要进行大量的倒箱作业（通常为总 量的），增 加 了 码 头 的 单 箱 作 业 成 本 因 此，对 出口箱随机入港下的箱区选择与箱位分配以及取箱 规则进行优化，可 以明显地降低集装箱码头的单箱 装卸作业成本表 集中入港下的箱区位置变化对优化结果的影响 ： ，： ， ，： 曾庆成，杨忠振，陆靖集装箱码头同贝同步装卸调度模型与算法交 通运输工程学报 ，（）： ， ， 箱区位置 离岸线距 离集中入港 单位 作业时 间随机入港 单位 作业时 间随机与集中 入港作业的 效率 比，（）： ， 平均注 ： 为取最前排箱街距离泊位岸线 结语随着集装箱码头竞争的日益激烈 ，采 用出口箱 随机入港策略，转变生产作业方式 ，已经成为集装箱 码头提升竞争力的必然发展趋势 面对出口箱随机 入港策略下，集装 箱分散堆放和随机选位给集卡行 驶路径与场桥取箱作业带来的复杂影响 ，本 文提出 了出口箱随机入港下箱区选择与箱位分配协调调度 问题，并构建和设计 了相应的 个阶段非线性整数 规划模型和同步优化算法 算例分析结果表明 ：该规 划模型与优化算法可以有效地减少集卡行驶路径、 缩短集卡等待时间，提高集卡运行效率 与出口箱集 中入港下的单船独立边装边卸作业相比 ，随 机入港 下的多船交叉混合装卸作业 ，可以 减少集卡装卸单 位 平均行驶路径 ，降 低 场 桥 作 业 成 本 以 上，提 高了集卡作业效率 同 时，还 可提高码 头前方堆场的均衡利用效率 ，实现 码头设备使用效 率与设