An ant colony algorithm for yard truck scheduling and yard location assignment problems with precedence constraints

Abstract

This paper examines the yard truck scheduling, the yard location assignment for discharging containers, and the quay crane scheduling in container terminals. Taking into account the practical situation, we paid special attention to the loading and discharging precedence relationships between containers in the quay crane operations. A Mixed Integer Program (MIP) model is constructed, and a two-stage heuristic algorithm is proposed. In the first stage an Ant Colony Optimization (ACO) algorithm is employed to generate the yard location assignment for discharging containers. In the second stage, the integration of the yard truck scheduling and the quay crane scheduling is a flexible job shop problem, and an efficient greedy algorithm and a local search algorithm are proposed. Extensive numerical experiments are conducted to test the performance of the proposed algorithms.

Keywords

Container terminal / yard truck scheduling / yard location assignment / quay crane scheduling / precedence constraints / ant colony optimization

References

[1] Bish EK. A multiple-crane-constrained scheduling problem in a container terminal. European Journal of Operational Research, 2003, 144(1): 83-107.

[2] Bish EK, Leong TY, Li CL, Ng JWC, Simchi-Levi D. Analysis of a new vehicle scheduling and location problem. Naval Research Logistics, 2001, 48(5): 363-385.

[3] Cao JX, Lee DH, Chen JH, Shi QX. The integrated yard truck and yard crane scheduling problem: Blenders’ decomposition-based methods. Transportation Research Part E: Logistics and Transportation Review, 2010, 46(3): 344-353.

[4] Chen L, Bostel N, Dejax P, Cai JC, Xi LF. A tabu search algorithm for the integrated scheduling problem of container handling systems in a maritime terminal. European Journal of Operational Research, 2007, 181(1): 40-58.

[5] Dorigo M. Optimization, learning and natural algorithms, 1992

[6] Dorigo M, Stützle T. Ant Colony Optimization, 2004, Cambridge, Mass: MIT Press.

[7] Gupta JND. Two-stage, hybrid flowshop scheduling problem. Journal of the Operational Research Society, 1988, 39(4): 359-364.

[8] Lee DH, Cao JX, Shi QX. Integrated quay crane and yard truck schedule for inbound containers. IEEM: International Conference on Industrial Engineering and Engineering Management, 2008, 1–3: 1219-1223.

[9] Lee DH, Cao JX, Shi QX. Synchronization of yard truck scheduling and storage allocation in container terminals. Engineering Optimization, 2009, 41(7): 659-672.

[10] Lee DH, Cao JX, Shi QX, Chen JH. A heuristic algorithm for yard truck scheduling and storage allocation problems. Transportation Research Part E: Logistics and Transportation Review, 2009, 45(5): 810-820.

[11] Lee LH, Chew EP, Tan KC, Wang YA. Vehicle dispatching algorithms for container transshipment hubs. OR Spectrum, 2010, 32(3): 663-685.

[12] Ng WC, Mak KL, Zhang YX. Scheduling trucks in container terminals using a genetic algorithm. Engineering Optimization, 2007, 39(1): 33-47.

[13] Nishimura E, Imai A, Papadimitriou S. Yard trailer routing at a maritime container terminal. Transportation Research Part E: Logistics and Transportation Review, 2005, 41(1): 53-76.