An Efficient Approach for Solving Yard Crane Scheduling in a Container Terminal

doi:10.1007/s12204-013-1441-y

上海交通大学学报（英文版） ›› 2013, Vol. 18 ›› Issue (5): 606-619.doi: 10.1007/s12204-013-1441-y

An Efficient Approach for Solving Yard Crane Scheduling in a Container Terminal

HE Jun-liang1,2* (何军良), ZHANG Wei-min1 (张为民), HUANG You-fang2 (黄有方), YAN Wei2 (严伟)

(1. School of Mechanical Engineering, Tongji University, Shanghai 201804, China; 2. Engineering Research Center of Container Supply Chain Technology, Ministry of Education, Shanghai Maritime University, Shanghai 201306, China)

出版日期:2013-10-31 发布日期:2013-12-05
通讯作者: HE Jun-liang(何军良) E-mail:jlhe@shmtu.edu.cn

An Efficient Approach for Solving Yard Crane Scheduling in a Container Terminal

HE Jun-liang1,2* (何军良), ZHANG Wei-min1 (张为民), HUANG You-fang2 (黄有方), YAN Wei2 (严伟)

(1. School of Mechanical Engineering, Tongji University, Shanghai 201804, China; 2. Engineering Research Center of Container Supply Chain Technology, Ministry of Education, Shanghai Maritime University, Shanghai 201306, China)

Online:2013-10-31 Published:2013-12-05
Contact: HE Jun-liang(何军良) E-mail:jlhe@shmtu.edu.cn

摘要/Abstract

摘要： An efficient approach for yard crane (YC) scheduling is proposed in this paper. The definition of task group for YC scheduling is proposed. A mixed integer programming (MIP) model is developed. In the model, objective functions are subject to the minimization of the total delay of complete time for all task groups and the minimization of block-to-block movements of YCs. Due to the computational scale of the non-deterministic polynomial (NP) complete problem regarding YC scheduling, a rolling-horizon decision-making strategy is employed to solve this problem, by converting the MIP model into another MIP model in the scheduling of each rolling period. Afterwards, a heuristic algorithm based on modified A* search is developed to solve the converted model and obtain near optimal solution. Finally, the computational experiments are used to examine the performance of the proposed approach for YC scheduling.

关键词: container terminal, yard crane scheduling, mixed integer programming, heuristic algorithm

Abstract: An efficient approach for yard crane (YC) scheduling is proposed in this paper. The definition of task group for YC scheduling is proposed. A mixed integer programming (MIP) model is developed. In the model, objective functions are subject to the minimization of the total delay of complete time for all task groups and the minimization of block-to-block movements of YCs. Due to the computational scale of the non-deterministic polynomial (NP) complete problem regarding YC scheduling, a rolling-horizon decision-making strategy is employed to solve this problem, by converting the MIP model into another MIP model in the scheduling of each rolling period. Afterwards, a heuristic algorithm based on modified A* search is developed to solve the converted model and obtain near optimal solution. Finally, the computational experiments are used to examine the performance of the proposed approach for YC scheduling.

Key words: container terminal, yard crane scheduling, mixed integer programming, heuristic algorithm

中图分类号:

U 656.135

HE Jun-liang1,2* (何军良), ZHANG Wei-min1 (张为民), HUANG You-fang2 (黄有方), YAN Wei2 (严. An Efficient Approach for Solving Yard Crane Scheduling in a Container Terminal[J]. 上海交通大学学报（英文版）, 2013, 18(5): 606-619.

HE Jun-liang1,2* (何军良), ZHANG Wei-min1 (张为民), HUANG You-fang2 (黄有方), YAN Wei2 (严伟). An Efficient Approach for Solving Yard Crane Scheduling in a Container Terminal[J]. Journal of shanghai Jiaotong University (Science), 2013, 18(5): 606-619.

参考文献

[1] Vob S, Stahlbock R. Operations research at container terminals: A literature update [J]. OR Spectrum, 2008, 30(1): 1-52.
[2] Imai A, Nishimura E, Papadimitriou S. Berthing ships at a multi-user container terminal with a limited quay capacity [J]. Transportation Research. Part E. Logistics and Transportation Review, 2008, 44(1): 136-151.
[3] Chang D F, Jiang Z H, Yan W, et al. Integrating berth allocation and quay crane assignments [J].Transportation Research. Part E. Logistics and Transportation Review, 2010, 46(6): 975-990.
[4] Mi W J, Yan W, He J L, et al. An investigation into yard allocation for outbound containers [J]. COMPEL: The International Journal for Computation and Mathematics in Electrical and Electronic Engineering, 2009, 28(6): 1442-1457.
[5] Shabayek A A, Yeung W W. A simulation model for the Kwai Chung container terminals in Hong Kong [J]. European Journal of Operational Research, 2002, 140(1): 1-11.
[6] Bielli M, Boulmakoul A, Mohamed R. Object oriented model for container terminal distributed simulation [J]. European Journal of Operational Research, 2006, 175(3): 1731-1751.
[7] Canonaco P, Legato P, Mazza R M, et al. A queuing network model for the management of berth crane operations [J]. Computers & Operations Research, 2008, 35(8): 2432-2446.
[8] Zeng Q C, Yang Z Z. Integrating simulation and optimization to schedule loading operations in container terminals [J]. Computers & Operations Research, 2009, 36(6): 1935-1944.
[9] Li W, Wu Y, Petering M E H, et al. Discrete time model and algorithms for container yard crane scheduling [J]. European Journal of Operational Research, 2009, 198(1): 165-172.
[10] Zhang C Q,Wan YW, Liu J Y, et al. Dynamic crane deployment in container storage yards [J]. Transportation Research. Part B. Methodological, 2002, 36(6): 537-555.
[11] He J L, Chang D F, Mi, W J, et al. A hybrid parallel genetic algorithm for yard crane scheduling [J]. Transportation Research. Part E. Logistics and Transportation Review, 2010, 46(1): 36-155.
[12] Chang D F, Jiang Z H, Yan W, et al. Developing a dynamic rolling-horizon decision strategy for yard crane scheduling [J]. Advanced Engineering Informatics, 2011, 25(3): 485-494.
[13] Ng W C, Mak K L. Yard crane scheduling in port container terminals [J]. Applied Mathematical Modeling, 2005, 29(3): 263-276.
[14] Cao J X, Lee D H, Chen J H, et al. The integrated yard truck and yard crane scheduling problem: Benders’decomposition-based methods [J]. Transportation Research. Part E. Logistics and Transportation Review, 2010, 46(3): 344-353.
[15] Yan W, Huang Y F, Chang D F, et al. An investigation into knowledge-based yard crane scheduling for container terminals [J]. Advanced Engineering Informatics, 2011, 25(3): 462-471.

An Efficient Approach for Solving Yard Crane Scheduling in a Container Terminal

An Efficient Approach for Solving Yard Crane Scheduling in a Container Terminal

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 0

编辑推荐

Metrics

本文评价