考虑翻箱作业时出口箱堆场作业调度优化

上海交通大学学报（自然版） ›› 2014, Vol. 48 ›› Issue (1): 146-153.

考虑翻箱作业时出口箱堆场作业调度优化

边展1，徐奇1，靳志宏1，李向军2

（1．大连海事大学交通运输管理学院，辽宁大连 116026； 2．大连海洋大学信息工程学院，辽宁大连 116023）

收稿日期:2013-01-04
基金资助:
国家自然科学基金（71172108, 71302044）,大连市科技计划（2012A17GX125）,教育部高等学校博士学科点专项科研基金（20122125110009，20132125120009）资助项目

Optimization of Yard Crane Scheduling with Consideration of Export Container Relocation

BIAN Zhan1,XU Qi1,JIN Zhihong1,LI Xiangjun2

（1. College of Transportation Management, Dalian Maritime University, Dalian 116026, Liaoning China;2. College of Information Engineering, Dalian Ocean University, Dalian 116023, Liaoning, China）

Received:2013-01-04

摘要/Abstract

摘要：

基于出口箱的堆场操作实务，考虑堆场起重机取箱作业的现实约束，以作业过程中翻箱次数最少为目标，对堆场作业调度问题进行建模，提出了两阶段混合动态规划算法，将启发式规则嵌入动态规划算法中，以避免出现状态数“组合爆炸”增长的情况.通过仿真算例，并与实际调度规则及现有研究方法所得调度方案进行对比，验证了模型以及优化算法的有效性与实用性.结果表明，所提出的模型和算法可以在较短的求解时间内获得多组装船方案，且其翻箱次数显著降低.

关键词: 取箱作业调度, 翻箱, 启发式规则, 动态规划, 混合优化算法

Abstract:

This paper presented a two-phase hybrid dynamic algorithm aiming at obtaining an optimized container retrieving sequence for a crane to retrieve all the containers from a given yard to the ship. The optimization goal was to minimize the number of container relocation operations. The two phases of the proposed dynamic procedure are as follows: in the first phase, a heuristic algorithm was developed to retrieve the containers which needed no relocation directly onto the ship; in the second phase, a dynamic programming within heuristic rules was used to solve the retrieving sequences problem for the rest of the containers. Computational experiments showed that the model and the hybrid dynamic algorithm could solve the retrieving problem of container terminals efficiently.

Key words: yard crane scheduling, relocation containers, heuristic rules, dynamic programming, hybrid optimization algorithm

中图分类号:

U 169.62

边展1，徐奇1，靳志宏1，李向军2. 考虑翻箱作业时出口箱堆场作业调度优化[J]. 上海交通大学学报（自然版）, 2014, 48(1): 146-153.

BIAN Zhan1,XU Qi1,JIN Zhihong1,LI Xiangjun2. Optimization of Yard Crane Scheduling with Consideration of Export Container Relocation[J]. Journal of Shanghai Jiaotong University, 2014, 48(1): 146-153.

参考文献

［1］Kim K H. Evaluation of the number of rehandles in container yards［J］. Computers and Industrial Engineering, 1997, 32(4): 70111.

［2］Kim K H, Kim H B. Segregating space allocation models for container inventories in port container terminals ［J］. International Journal of Production Economics, 1999, 59(1): 415423.

［3］徐亚, 陈秋双, 龙磊, 等.集装箱倒箱问题的启发式算法研究［J］.系统仿真学报, 2008, 20(14): 36663669.

XU Ya, CHEN Qiushuang, LONG Lei, et al. Heuristics for container relocation problem ［J］. Journal of System Simulation, 2008, 20(14): 36663669.

［4］易正俊, 李保顺, 李新强. 集装箱堆场倒箱博弈启发式优化算法［J］.上海海事大学学报, 2010, 31(3): 4751.

YI Zhengjun, LI Baoshun, LI Xinqiang. Game heuristic optimization algorithm for reshuffle in container yards ［J］. Journal of Shanghai Maritime University, 2010, 31(3): 4751.

［5］易正俊, 江静, 胡勇. 堆场集装箱翻箱的PCNN优化控制算法［J］.自动化学报, 2011, 37(2): 241244.

YI Zhengjun, JIANG Jing, HU Yong. An optimization control algorithm for containers relocation based on PCNN model ［J］. Acta Automatic Sinica, 2011, 37(2): 241244.

［6］Kang J, Oh M S, Ahn E Y, et al. Planning for intrablock remarshalling in a container terminal ［J］. Advances in Applied Artificial Intelligence, 2006, 4031: 12111220.

［7］Caserta M, Voβ S, Sniedovich M. Applying the corridor method to a blocks relocation problem ［J］. European Journal of Operational Research, 2011, 33(4): 915929.

［8］Caserta M, Schwarze S, Voβ S. A mathematical formulation and complexity considerations for the blocks relocation problem ［J］. European Journal of Operational Research, 2012, 219(1): 96104.

［9］Bortfeldt A, Forster F. A tree search procedure for the container premarshalling problem ［J］. European Journal of Operational Research, 2012, 217(3): 531540.

［10］Forster F, Bortfeldt A. A tree search procedure for the container relocation problem ［J］. Computers and Operations Research, 2012, 39(2): 299309.

［11］朱明华, 范秀敏, 程奂翀, 等.集装箱装船顺序问题的启发式算法研究［J］.中国机械工程, 2010, 21(9): 10661070.

ZHU Minghua, FAN Xiumin, CHENG Huanchong, et al. Heuristics for export container loading sequence problem ［J］. China Mechanical Engineering, 2010, 21(9): 10661070.

［12］靳志宏, 兰辉, 边展, 等. 基于现实约束的集装箱装船顺序优化［J］. 大连海事大学学报, 2011, 37(1): 7174.

JIN Zhihong, LAN Hui, BIAN Zhan, et al. Optimization on containership loading scheduling based on actual constraints ［J］. Journal of Dalian Maritime University, 2011, 37(1): 7174.