A Lagrangian relaxation-based algorithm for the allocation of yard cranes for yard activities with different priorities

Abstract

This paper proposes a mixed integer programming model for the allocation of rail mounted gantry cranes for four basic yard activities with different priorities. The model pays special attention to the typical features of this kind of gantry cranes, such as a restricted traveling range and a limited number of adjustments during loading and discharging operations. In contrast to most of the literature dealing with these four yard activities individually, this paper models them into an integrated problem, whose computational complexity is proved to be NP-hard. We are therefore motivated to develop a Lagrangian relaxation-based heuristic to solve the problem. We compare the proposed heuristic with the branch-and-bound method that uses commercial software packages. Extensive computational results show that the proposed heuristic achieves competitive solution qualities for solving the tested problems.

Keywords

Crane allocation / container terminal / Lagrangian relaxation / sub-gradient / yard crane

References

[1] Bierwirth C, Meisel F. A survey of berth allocation and quay crane scheduling problems in container terminals. European Journal of Operational Research, 2010, 202(3): 615-627.

[2] Cheung RK, Li C, Lin W. Interblock crane deployment in container terminals. Transportation Science, 2002, 36(1): 79-93.

[3] Cormen TH, Leiserson CE, Rivest RL, Stein C. Introduction to Algorithms, 2001, Second Edition Boston: The MIT Press.

[4] Dorndorf U, Schneider F. Scheduling automated triple cross-over stacking cranes in a container yard. OR Spectrum, 2010, 32(3): 617-632.

[5] Geoffrion AM. Lagrangean relaxation for integer programming. Mathematical Programming Study, 1974, 2: 82-114.

[6] Han Y, Lee L, Chew E, Tan K. A yard storage strategy for minimizing traffic congestion in a marine container transshipment hub. OR Spectrum, 2008, 30(4): 697-720.

[7] Kim KH, Kim HB. The optimal sizing of the storage space and handling facilities for import containers. Transportation Research Part B, 2002, 36(9): 821-835.

[8] Kim KH, Kim KY. An optimal routing algorithm for a transfer crane in port container terminals. Transportation Science, 1999, 33(1): 17-33.

[9] Kim KY, Kim KH. A routing algorithm for a single transfer crane to load export containers onto a containership. Computers & Industrial Engineering, 1997, 33(3–4): 673-676.

[10] Kim KY, Kim KH. A routing algorithm for a single straddle carrier to load export containers onto a containership. International Journal of Production Economics, 1999, 59(1–3): 425-433.

[11] Ku LP, Lee LH, Chew EP, Tan KC. An optimisation framework for yard planning in a container terminal: case with automated rail-mounted gantry cranes. OR Spectrum, 2010, 32(3): 519-541.

[12] Lee D, Cao Z, Meng Q. Scheduling of two-transtainer systems for loading outbound containers in port container terminals with simulated annealing algorithm. International Journal of Production Economics, 2007, 107(1): 115-124.

[13] Lee L, Chew E, Tan K, Han Y. An optimization model for storage yard management in transshipment hubs. OR Spectrum, 2006, 28(4): 539-561.

[14] Linn RJ, Zhang C. A heuristic for dynamic yard crane deployment in a container terminal. IIE Transactions, 2003, 35(2): 161-174.

[15] Murty KG, Liu J, Wan Y, Linn R. A decision support system for operations in a container terminal. Decision Support Systems, 2005, 39(3): 309-332.

[16] Murty KG, Wan Y, Liu J, Tseng MM, Leung E, Lai K, Chiu HWC. Hongkong international terminals gains elastic capacity using a data-intensive decision-support system. Interfaces, 2005, 35(1): 61-75.

[17] Ng WC. Crane scheduling in container yards with inter-crane interference. European Journal of Operational Research, 2005, 164(1): 64-78.

[18] Stahlbock R, VoB S. Operations research at container terminals: a literature update. OR Spectrum, 2008, 30(1): 1-52.

[19] Steenken D, VoB S, Stahlbock R. Container terminal operation and operations research — a classiffication and literature review. OR Spectrum, 2004, 26(1): 3-49.

[20] Vis IFA, Koster R. Transshipment of containers at a container terminal: an overview. European Journal of Operational Research, 2003, 147(1): 1-16.

[21] Zhang C, Wan Y, Liu J, Linn RJ. Dynamic crane deployment in container storage yards. Transportation Research Part B, 2002, 36(6): 537-555.

[22] Zhang C, Zhang Z, Zheng L, Miao L. A decision support system for the allocation of yard cranes and blocks in container terminals. Asia-Pacificc Journal of Operational Research, 2011, 28(6): 803-829.

[23] Zhou W, Wu X. An efficient optimal solution of a two-crane scheduling problem. Asia-Pacific Journal of Operational Research, 2009, 26(1): 31-58.