Discrete time model and algorithms for container yard crane scheduling

被引:100
作者
Li, Wenkai [1 ]
Wu, Yong [1 ]
Petering, M. E. H. [1 ,2 ]
Goh, Mark [1 ]
de Souza, Robert [1 ]
机构
[1] Asia Pacific, Logist Inst, Singapore 117574, Singapore
[2] Univ Wisconsin, Dept Ind & Mfg Engn, Milwaukee, WI 53201 USA
关键词
Scheduling; Rolling-horizon algorithm; Container yard; MILP; OPERATIONS-RESEARCH; ALLOCATION; SEARCH;
D O I
10.1016/j.ejor.2008.08.019
中图分类号
C93 [管理学];
学科分类号
12 ; 1201 ; 1202 ; 120202 ;
摘要
Container terminal (CT) operations are often bottlenecked by slow YC (yard crane) movements. PM (prime mover) queues in front of the YCs are common. Hence, efficient YC scheduling to reduce the PM waiting time is critical in increasing a CT's throughput. We develop an efficient model for YC scheduling by taking into account realistic operational constraints such as inter-crane interference, fixed YC separation distances and simultaneous container storage/retrievals. Among them, only inter-crane interference has ever been considered in the literature. The model requires far fewer integer variables than the literature by using bi-index decision variables. We show how the model can be solved quickly using heuristics and rolling-horizon algorithm, yielding close to optimal solutions in seconds. The solution quality and solution time are both better than the literature even with additional constraints considered. The proposed formulations and algorithms can be extended to other problems with time windows and space constraints. (C) 2008 Elsevier B.V. All rights reserved.
引用
收藏
页码:165 / 172
页数:8
相关论文
共 20 条
[1]   A multiple-crane-constrained scheduling problem in a container terminal [J].
Bish, EK .
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2003, 144 (01) :83-107
[2]   A tabu search algorithm for the integrated scheduling problem of container handling systems in a maritime terminal [J].
Chen, Lu ;
Bostel, Nathalie ;
Dejax, Pierre ;
Cai, Jianguo ;
Xi, Lifeng .
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2007, 181 (01) :40-58
[3]  
Chung RK, 2002, TRANSPORT SCI, V36, P79, DOI 10.1287/trsc.36.1.79.568
[4]   Optimizing the landside operation of a container terminal [J].
Froyland, Gary ;
Koch, Thorsten ;
Megow, Nicole ;
Duane, Emily ;
Wren, Howard .
OR SPECTRUM, 2008, 30 (01) :53-75
[5]  
HENWOOD R, 2006, PRACTITIONERS DEFINI
[6]  
Hopp W.J., 2000, Factory Physics: Foundations of Manufacturing Management
[7]   A crane scheduling method for port container terminals [J].
Kim, KH ;
Park, YM .
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2004, 156 (03) :752-768
[8]   An optimal routing algorithm for a transfer crane in port container terminals [J].
Kim, KH ;
Kim, KY .
TRANSPORTATION SCIENCE, 1999, 33 (01) :17-33
[9]   Heuristic algorithms for routing yard-side equipment for minimizing loading times in container terminals [J].
Kim, KY ;
Kim, KH .
NAVAL RESEARCH LOGISTICS, 2003, 50 (05) :498-514
[10]   Allocation of empty containers between multi-ports [J].
Li, Jing-An ;
Leung, Stephen C. H. ;
Wu, Yue ;
Liu, Ke .
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2007, 182 (01) :400-412