基于集装箱港口的空箱调运流程优化.pdf

第5卷 第10期 2010 年 10 月 813 基于集装箱港口的空箱调运流程优化 靳志宏 1 徐 奇1 兰 辉1 2 1 大连海事大学交通运输管理学院 辽宁大连 116026 2 大连港集团公司 辽宁大连 116004 摘 要 以集装箱空箱调运成本最低为优化目标 在分析现行集装箱空箱周转流程的基础上 提出一种新的空箱调运 流程 进而建立了集装箱空箱调度解析模型 设计了基于免疫遗传算法的优化解法 并基于实际调查及预测的数据进 行仿真对比实验 以青岛港为对象进行的实证研究表明 所提出的空箱调运方案很大程度上减少了空箱调运成本 而 且有助于缓解港口交通拥挤 显示了新流程及其调度方法的有效性 关键词 空箱周转 空箱调度 免疫遗传算法 实证分析 中图分类号 U169 65 文献标志码 A 文章编号 1673 7180 2010 10 0813 7 Optimization on empty container repositioning process at container terminals Jin Zhihong1 Xiu Qi1 Lan Hui1 2 1 College of Transportation Management Dalian Maritime University Dalian Liaoning 116026 China 2 Dalian Port Co Ltd Dalian Liaoning 116004 China Abstract An improved empty container allocation process is proposed in an effort to reduce the allocation cost by analyzing the current empty container allocation process Then the empty container dispatch problem is formulated as nonlinear integer programming and an immune genetic algorithm IGA is developed to optimize empty container scheduling Finally an empirical analysis for Qingdao port was conducted to simulate and evaluate the proposed allocation process which demonstrated that significant cost and congestion reductions can be achieved Key words empty container turnover repositioning immune genetic algorithm empirical analysis 集装箱作为货物运输的媒介在完成货物运输 给客 户带来方便的同时成为空箱 空箱的再利用需要不会产 生任何效益的空箱调运 空箱调运成为长期以来困扰航 运企业的老大难问题 集装箱的周转必须经过拆与装的 过程 而拆箱和装箱通常发生在不同的时间 不同的地 点 货主为了装运货物产生空箱需求 附近的港口 堆 场和中转站将空箱运到货主所在地 如果上述地点缺少 空箱 就需要从其他地点调运 或从系统外的租箱点租 借 当货主的空箱需求满足后 空箱装入货物成为重箱 经公路 铁路 内河运输到目的地港 重箱卸下后再经 公路 铁路或内河运输到客户所在地 重箱卸完货物 后成为空箱 空箱将被运往附近的港 场 站再次使 用 或还给租箱点 上述流向与流程取决于空箱 重箱 的需求与供给分布以及海运与内陆集疏运体系的运行 模式等 分析上述空箱流程 造成空箱调运的客观原因是港 口进出箱量的不平衡 进出箱型的不平衡和港口集疏运 能力低等 另一方面 人为因素形成的货流不平衡所引 收稿日期 2010 09 25 基金项目 国家自然科学基金资助项目 70572104 高等学校博士学科点专项科研基金资助项目 20070151002 辽宁省自然科学 基金资助项目 20082141 作者简介 靳志宏 1963 男 教授 主要研究方向 物流系统优化与仿真 jinzhihong 中国科技论文在线 SCIENCEPAPER ONLINE 第5卷 第10期 2010 年 10 月 814 中国科技论文在线 SCIENCEPAPER ONLINE 发的集装箱的供需矛盾也是另一重要原因 主要体现在 集装箱空箱管理的组织与调度水平方面 对于空箱调度问题 国内外的学者进行了广泛研 究 Choong 等 1 提出以减少空箱调运总成本为目标的整 数规划模型 并基于计算机技术分析计划工作时段长度 计划期跨度 对多式联运空箱管理的影响 Shen 等 2 建立了航运企业解决大范围 多阶段空箱分配问题的决 策支持系统 Jula 等 3 建立动态空箱调运解析模型 并 提出了优化解法 与国外相关研究相比较 国内绝大 部分研究多为定性分析 政策建议等 刘恒江 4 和徐剑 华 5 6 分析空箱调运的现状 提出解决空箱调运的新思 路 聂俊等 7 分析了集装箱空箱产生的原因 给出了空 箱调运的策略 沈一平 8 分析了空箱调运与租箱决策的 关系 施欣 9 结合对集装箱海运空箱调运过程的剖析 建立了相应的系统优化模型 通过数字仿真 揭示了成 本 收入等经济参数以及船舶装载能力对集装箱空箱调 运策略的影响机制 施欣 10 构造了集装箱空箱保存量优 化决策的基本模型 并通过相应的数字仿真验证了模型 的合理性 国内对上述现存问题的研究大多是以定性分析为 主 少数定量研究也缺乏实证研究辅佐 笔者以青岛港 为例 对空箱调运问题进行实证研究 试图从定量的角 度分析空箱周转流程 优化空箱调度方案 为空箱的调 运决策提供理论支持 1 集装箱空箱周转流程分析 1 1 现行集装箱空箱周转流程 1 1 1 进口集装箱流 进口的空箱流如图 1 所示 图 1 进口空箱流 Fig 1 Import empty container flow 一辆集卡车从车队出发 到集装箱场站装运重箱 箭头1 这辆集卡车在集装箱场站装上重箱 运往 指定的托运人 收货人 处 箭头2 此时如果托运 人 收货人 处有空箱则将其运回集装箱场站 虚箭头 5 接下来这辆车返回车队或者派给其他任务 箭头6 如果托运人 收货人 处没有空箱 这辆集卡车返回车 队或者被派给其他任务 箭头3 当托运人 收货人 处有空箱时 指派一辆集卡车去托运人 收货人 处将 空箱取回 箭头4 1 1 2 出口集装箱流 出口的空箱流如图 2 所示 图 2 出口空箱流 Fig 2 Export empty container flow 一辆集卡车从车队出发 到集装箱场站装运空 箱 箭头 1 这辆集卡车在集装箱场站装上空箱 运往指定的承运人处 虚箭头 2 此时如果承运人 处有重箱则将其运回集装箱场站 箭头 5 接下来 这辆车返回车队或者派给其他任务 箭头 6 如果 承运人处没有重箱 这辆集卡车返回车队或者被派 给其他任务 箭头 3 当承运人处有重箱时 指派 一辆集卡车去承运人处将重箱取回 箭头 4 1 2 改进的集装箱空箱流程 一般来说 空箱调运主要有2 种方式 直接调运和 场站转运 直接调运方式 此方式就是将空箱直接从托运人 收货人 运到承运人处 而不是先运回集装箱码头场 站再运给承运人 该方式的优势很明显 主要包括 减 少集卡车的运行路程及进出集装箱码头场站的驾驶时 间 从而减少交通拥挤 港区噪音等负面影响 场站转运方式 此方式是在内陆新增设集装箱场 站 用于空箱的储存 维护和交易等操作 这样做的主 要好处是 建立了一个内陆的集装箱调运供应点 当码 头场站处交通拥挤或者大门关闭时可以在这个内陆场 站装卸空箱 从而增加了码头场站的缓冲能力 改进后港区的集装箱流动情况见图 3 为了简化 省去了空车的运行路线 正如图 3 所示 通过直接将 空箱从托运人 收货人 运往承运人 省去了 2 个进 出港口码头的空箱调运过程 也就是图 1 中的箭头 5 和图 2 中的箭头 2 但同时也增加了 1 个港外的空箱 调运过程 3 第5卷 第10期 2010 年 10 月 815 图 3 改进后的集装箱流 Fig 3 Improved container flow 2 建模与优化 2 1 建模假设与符号说明 为了使问题简化 作如下现实假设 1 所有的空箱调运过程都发生在计划期间 T 内 换句话说 就是没有空箱调运在k 1 前开始 也没有空 箱调运在k T 后才进行 2 所有的内陆集装箱场站和码头场站在时段 T 内 都能够拆箱 装箱以及运送空箱 3 每个托运人 收货人 每天产生的空箱 以及 每个承运人每天需求的空箱已知 为了建立空箱调运模型 定义了下面的参数 T 为 计划工作时段长度 I 为在时间段 T 内能够供给空箱的 托运人 收货人 的集合 J 为在时间段T 内需要空箱 的承运人的集合 P 为内陆场站和码头场站的集合 kk ij x 为k 时刻从托运人 收货人 i I 运往承运人j J 并 在 k 时刻到达的空箱数 kk ij c 为 k 时刻从托运人 收货 人 i I 运1 个空箱到承运人j J 在k 时刻到达的成 本 k ij t 为k 时刻从托运人 收货人 i I 运1 个空箱到 承运人 j J 所需要的时间 包括装卸时间 k ip x为 k 时 刻从托运人 收货人 i I 运往内陆场站 p P 的空箱 数 k pj x 为从内陆场站 p P 运往承运人 j J 并在 k 时刻到达的空箱数 k i s为k 时刻托运人 收货人 i I 可以供给的空箱数 k j d 为k 时刻承运人j J 需要的空 箱数 此外 还定义了下面2 个时间序列发生器 kxU kk ij 1 kxD kk ij 2 式中 U 的返回值是 kk ij x的最早装车时间 D 的返回值 是 kk ij x的最迟卸车时间 2 2 数学模型 minZ 3 s t Ii Tk 1L 4 Jj Tk 1 L 5 kk ij xU ij kk IJ kk ij xDtxUx kk ij 0 TkkJjIi 1 L 6 k pj k ip kk ij xxx 0 and integer TkkPpJjIi 1 L 7 目标函数式 3 是在满足约束条件的所有可行解中 找到需求与供给的最优匹配 即空箱调运成本的最小 化 约束式 4 确保k 时刻托运人 收货人 提供空箱数 与此时的总供给数相等 约束式 5 确保k 时刻承运人收 到的空箱数与总需求数相等 约束式 6 是确保时间上的 可行性 约束式 7 是整数限制 3 2 3 优化解法 Jula 等 3 运用两阶段优化方法将上述模型的非线 性约束式 6 松弛 将原模型化为线性规划问题 然后利 用线性规划解法求解模型 所得到的解是对原问题的一 种近似 虽然利用了线性规划这一精确解法求解 但是 由于是在前期近似的基础上做出的 所以解的精确度并 不高 而且 优化过程中对约束的松弛方法很烦琐 不 基于集装箱港口的空箱调运流程优化 第5卷 第10期 2010 年 10 月 816 中国科技论文在线 SCIENCEPAPER ONLINE 易实现 所以求解效果并不理想 鉴于上述模型是非线性整数规划模型 涉及的变量 多 维数高 解空间大 以及针对文献 3 解法存在的问 题 笔者提出运用免疫遗传算法 11 14 解决该问题 免疫 遗传算法克服了简单遗传算法的缺点 对解决非线性 高维 多变量的复杂系统问题有很好的效果 在编程过程中运用分级的优化思想 其基本思路如 下 首先解决托运人 收货人 与承运人间有无空箱调 运的问题 针对其特点 采用二进制编码方式 该编码 方式搜索能力较强 也可以很好地解决解空间较大的问 题 然后解决托运人 收货人 与承运人间调运量多少 的问题 为了增加子代解的利用效率 将约束条件式 4 和式 5 融入到编码过程中 产生的子代解只需要代入约 束条件式 6 检验即可判断是否为可行解 例如 研究对象选取 A 个托运人 收货人 B 个 承运人 C 个内陆集装箱场站 1 个码头集装箱场站 编码时产生 A C B C 的0 1 矩阵 每个矩阵元素代 表1 个匹配 第一步 扫描矩阵元素 判断其 0 1 值 若该矩 阵元素为1 代表此处有空箱运输 若为0 表示没有空箱 运输 第二步 对于矩阵元素为1 的匹配 再根据约束式 4 和式 5 的限制具体分配空箱数值 第三步 将免疫遗传算法产生的子代解代入约束式 6 中检验 满足条件的子代解将作为一个可行解 而不 满足条件的子代解则直接被淘汰 3 模拟仿真实验 3 1 仿真对象选取 为了验证模型和解法的有效性 对青岛港进行实证 研究 用实际调查和预测的数据进行模拟仿真 并与现 行方案进行比较 进而得出相关结论 青岛港附近有众多的托运人 收货人 和承运人 为了不失一般 又能达到对比的目的 选取了8 个具有 代表性的托运人 收货人 和6 个承运人以及1 个内陆 集装箱场站和1 个码头集装箱场站 各个节点之间的距 离采用其间的实际数据 3 2 仿真方案 3 2 1 现行方案 现行操作复制当前青岛港的操作实际 也就是托运 人 收货人 直接把进口的空箱运回到集装箱码头场站 当接到调箱申请时 再从集装箱码头场站把空箱运到承 运人处 根据前面定义的变量 现行操作中的空箱调运 总成本可以表示为 11 k j T kJj k pj k i T kIi k ip dcsc 8 假设调运 1 个空箱到集装箱场站的成本与运输 距离成正比 而且这个成本与调运的起始时间无关 更准确地说 我们假设 ip k ip cc 和 pj k pj cc 在这里成 本 cip与托运人 收货人 i 到码头的最短距离成正 比 cpj是码头与承运人之间的最短路距离 3 2 2 新调运方案 根据前面已经定义过的变量 供给与需求之间 的空箱调运成本可以表示如下 kkcc ij kk ij JjIi ip k ip cc PpIi pj k pj cc PpJj 9 式中 cij是托运人 收货人 i 和承运人j 之间的运输距 离 cip是托运人 收货人 i 与场站 包括码头集装箱 场站 p 之间的运输距离 cpj是承运人 j 与场站 包括 码头集装箱场站 p 之间的运输距离 设计参数 主要 作用是避免空箱在一个地方停滞过长的时间 它可以促 使空箱在供给与需求节点之间的尽早流动 式 9 中第1 行包括 cij和 k k 2 部分 其中 后者表示无法满足需 求 时间上 时所产生的附加成本 当 0 时 不用考 虑时间差 k k 产生的附加成本 这时算法将会找到供给 与需求在空间上的最近匹配 这就是说 一些空箱在运 走前将会在一个地方停滞很长时间 随着 的增加 时 间差 k k 的权重增加 算法将求得一个使空箱在时间上 尽快运出的方案 假设起点 i 和终点 j 之间的运输时间 为tij tij与开始时间是独立的 且 ij ij d t 其中dij是供 给点 i 和需求点 j 之间的距离 是青岛港附近的集卡 车运行平均速度 在这里取值为25 km h 3 3 实证分析 青岛港是我国北方最大的集装箱港口 2008 年集装 箱吞吐量首次超过1000 万TEU 伴随着青岛港集装箱 运输的迅猛发展 进出港口的空箱量也迅速攀升 造成 了港区内交通拥挤 环境污染 运输成本增加 道路维 护成本增加和运输效率低等问题 3 3 1 2008 年港口空箱实际情形 2008 年通过青岛港大门的集卡车大约 40 都是用 第5卷 第10期 2010 年 10 月 817 来装卸空箱的 运往青岛港的空箱中45 是用集卡车从 托运人 收货人 处运来的 同时 从集装箱码头运出 的空箱中21 是运往承运人 这些数据用来提出下面的 3 个案例以仿真当前的情形 1 闲暇时的情况 2008 年青岛港闲暇的一天大约有 150 辆集卡车通 过码头大门 包括进出大门的车 也就是说 承运人 需要23 个空箱 托运人 收货人 提供27 个空箱 用 1 A 表示 2 一般情况 2008 年青岛港平常的一天每个集装箱场站大约有 91 个空箱要运往承运人 同时有 109 个空箱从托运人 收货人 处运回集装箱场站 用 1 B 表示 3 繁忙时的情况 2008 年青岛港繁忙的一天大约有 500 辆集卡车通 过码头大门 包括进出大门的车 也就是说 承运人 需要255 个空箱 托运人 收货人 提供297 个空箱 用 1 C 表示 3 3 2 2010 年港口空箱预测情形 基于近年来的吞吐量增长以及金融危机带来的影 响 我们预测了2010 年的供给需求数据 根据预测2010 年每天空箱需求数为414 个 供给数为485 个 用 1 D 表示 3 3 3 2015 年港口空箱预测情形 我们预测了 2015 年的供给需求数据 根据预测 2015 年每天空箱需求数为622 个 供给数为725 个 用 1 E 表示 4 仿真结果分析 算法利用 Visual Basic 6 0 程序实现 并在 PC 机 运行 取群体规模 N 20 进化代数 G 500 交叉概 率 Pc 0 9 变异概率 pm 0 1 A 0 8 B 0 8 亲和度 为 0 9 4 1 现行调度方案与新调度方案的比较 假设设计参数 为 0 1 计划工作时段为 8 h 即 T 8 将T 分成8 个阶段 每个阶段代表1 h 平均车速 为25 km h 承运人与托运人 收货人 每天总的空箱 供给与需求数按上面的案例情形计算 其中每个承运人 需要的空箱和每个托运人 收货人 可提供的空箱是随 机分配的 对于每一种案例情形 程序运行 10 次 取其最优 结果如表1 所示 从模型可以看出 现行调度方案的成本是由空箱数 与运输距离的乘积构成的 而新调度方案的成本由两部 分构成 即空箱数与运输距离的乘积 以及为了使空箱 尽早与及时运到而引入的惩罚成本 根据表1 中的数据 即使这样调运的成本仍然比基 本操作的成本减小了40 左右 可见新调度方案在减小 运输成本方面优势非常明显 从表1 还可以看出 与现行调度方案相比 新调度 方案在港口或场站附近的空箱运送次数明显减少 降低 了调运成本 同时也可以在很大程度上减少港口附近的 交通拥挤 噪声和空气污染 表 1 现行调度方案与新调度方案的比较 Table 1 Comparion of results between the proposed and current schedules 现行方案 新调度方案 案例 收货人供给的 空箱数 个 承运人需求的 空箱数 个 成本 箱 km 总空箱运送次数成本 箱 km 总空箱运送次数 运送 次数 1 A 27 23 600 50 3 939 36 16 1 B 109 91 2 400 200 1 452 8 122 52 1 C 297 255 6 624 552 4 003 6 355 161 1 D 485 414 10 788 899 6 294 4 549 243 1 E 725 622 16 164 1 349 10 433 828 322 4 2 平均运输速度的影响 考虑城市内部平均车速的变化对调运成本的影响 假设设计参数 为0 1 计划工作时段为8 h 即T 8 将T 分成8 个阶段 我们以案例1 C 为研究对象 因为 此情况既反映了现今最差的空箱调运情形又与 2010 年 的情形最为接近 具有代表性 具体操作中选择城市内部的平均车速分别为5 15 25 35 50 km h 对于每一种情形 程序运行10 次 取其最优结果如表2 所示 从表2 可以看出 随着城市内部平均车速的增加 基于集装箱港口的空箱调运流程优化 第5卷 第10期 2010 年 10 月 818 中国科技论文在线 SCIENCEPAPER ONLINE 调运成本减少 去往港口或场站的空箱调运次数也减 少 之所以产生此结果 主要原因是提高平均车速使发 生直接调运的可能性增加 进而减少去往港口和场站的 空箱运送次数 减少了空箱调运的成本 表 2 车速的影响 Table 2 Influence of container car speeds on the scheduling 现行方案 新调度方案 平均速度 km h 1 工作周期 长度 h 成本 箱 km 总空箱运送次数成本 箱 km 总空箱运送次数 运送 次数 5 8 6 624 552 4 640 8 358 208 15 8 6 624 552 4 367 7 352 171 25 8 6 624 552 4 003 6 355 161 35 8 6 624 552 4 003 6 355 161 50 8 6 624 552 4 003 6 355 161 4 3 其他设计参数的影响 考虑设计参数的变化对调运成本的影响 假设计划 工作时段为8 h 即T 8 将T 分成8 个阶段 我们仍 以案例1 C 为研究对象 具体操作中我们改变设计参数 分别为0 01 0 1 0 5 1 5 对于每一种情形 程序运行10 次 其最优 结果如表3 所示 如前所述 空箱调运主要包括直接调运和场站转 运 当设计参数 比较小时 惩罚成本较小 影响总成 本的是空箱运输成本 为了使成本最低 需要直接调运 即如果托运人 收货人 在很早的时刻就能提供空箱 但他们可以不急于将空箱运出 而是当整个计划工作时 段内有最优匹配时再将空箱运出 这样运输成本最小 当设计参数 较大时 惩罚成本较大 影响总成本的是 空箱运输成本和惩罚成本 而且惩罚成本起主要作用 对总成本减小的影响较大 为了使成本最小 则主要进 行场站转运 即如果托运人 收货人 处产生了空箱 就要立即运出 此时如无承运人接受空箱则运往场站 这样运输成本才能最低 从表3 中可以看出 随着设计参数 的增加 调运 成本和去往场站的运送次数都增加 这样的结果正好验 证了我们关于设计参数 影响调运成本的想法 表 3 设计参数的影响 Table 3 Influence of parameters on the scheduling 现行方案 新调度方案 设计参数 工作周期 长度 h 成本 箱 km 总空箱运送次数成本 箱 km 总空箱运送次数 运送 次数 0 01 8 6 624 552 3 951 8 355 161 0 1 8 6 624 552 4 003 6 355 161 0 5 8 6 624 552 4 234 355 161 1 8 6 624 552 4 491 344 179 5 8 6 624 552 5 818 384 278 5 结论及研究展望 以集装箱空箱调运成本最低为优化目标 在分析现 行集装箱空箱周转流程的基础上 提出一种新的空箱调 运流程 进而建立了集装箱空箱调运解析模型 设计了 基于免疫遗传算法的优化解法 并基于实际调查及预测 的数据进行仿真对比实验 以青岛港为对象进行的实证 研究表明 所提出的空箱调运方案很大程度上减少了空 箱调运成本 而且有助于缓解港口交通拥挤 显示了新 流程及其调度方法的有效性 笔者单独研究了空箱调运问题 实际上 空箱与重 箱的联合调度更具现实意义 今后将在考察重箱转化为 空箱的时间规律的基础上 做进一步深入研究 第5卷 第10期 2010 年 10 月 819 参考文献 References 1 Choong S T Michael H C Kutanogul E Empty container management for intermodal transportation networks J Transportation Research Part E 2002 38 11 423 438 2 Shen W S Khoong C M A DSS for empty container distribution planning J Decision Support Systems 1995 15 1 75 82 3 Jula H Chassiakos A Ioannou P Port dynamic empty container reuse J Transportation Research Part E 2006 42 1 43 60 4 刘恒江 集装箱空箱调运分析 J 集装箱化 2001 1 11 13 Liu Hengjiang The analysis on empty container repositioning J Containerization 2001 1 11 13 in Chinese 5 徐剑华 集装箱空箱运输的现状 原因与对策 J 世界海运 1998 21 3 26 28 Xu Jianhua The situation reasons and countermeasure on empty container transportation J World Shipping 1998 21 3 26 28 in Chinese 6 徐剑华 集装箱空箱运输的解决对策 J 集装箱运输 1998 3 1 20 21 Xu Jianhua The countermeasure on empty container transportation J Containerization 1998 3 1 11 13 in Chinese 7 聂俊 高晓建 集装箱空箱调运策略 J 集装箱化 2004 10 35 38 Nie Jun Gao Xiaojian The tactic on empty container repositioning J Containerization 2004 10 35 38 in Chinese 8 沈一平 空箱调运和租箱决策 J 集装箱化 1997 11 15 16 Shen Yiping The decision