A 15 Minute-Based Approach for Berth Allocation and Quay Crane Assignment

Authors: Hoi-Lam Ma, Sai-Ho Chung

Abstract:

In traditional integrated berth allocation with quay crane assignment models, time dimension is usually assumed in hourly based. However, nowadays, transshipment becomes the main business to many container terminals, especially in Southeast Asia (e.g. Hong Kong and Singapore). In these terminals, vessel arrivals are usually very frequent with small handling volume and very short staying time. Therefore, the traditional hourly-based modeling approach may cause significant berth and quay crane idling, and consequently cannot meet their practical needs. In this connection, a 15-minute-based modeling approach is requested by industrial practitioners. Accordingly, a Three-level Genetic Algorithm (3LGA) with Quay Crane (QC) shifting heuristics is designed to fulfill the research gap. The objective function here is to minimize the total service time. Preliminary numerical results show that the proposed 15-minute-based approach can reduce the berth and QC idling significantly.

Keywords: Transshipment, integrated berth allocation, variable-in-time quay crane assignment, quay crane assignment.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1340438

References:

[1] Queensland Government, Vessel at berth, http://www.qships.transport.qld.gov.au/Public/VesselsAtBerth.aspx, Accessed May, 2014.
[2] F. Meisel, C. Biewirth, “Heuristics for the integration of crane productivity in the berth allocation problem”, Transportation Part E, vol. 45, no. 1, pp. 196-209, 2009.
[3] G. Giallombardo, L. Moccia, M. Salani, I. Vacca, Modeling and solving the Tactical Berth Allocation Problem, Transportation Research Part B, vol. 44, no. 2, pp. 232-245, 2010.
[4] D. Steenken, S. Vob, R. Stahlbock. “Conatiner terminal operation and operations research - a classification and literature review”, OR spectrum, vol. 26, no. 1, pp. 3-49, 2004.
[5] C. Bierwirth, F. Meisel. F., “A survey of berth allocation and quay crane scheduling problems in container terminals”, European Journal of Operational Research, vol. 202, no. 3, pp. 615-627, 2010.
[6] A. Imai, E. Nishimura, S. Papadimitriou, “The dynamic berth allocation problem for a container port”, Transportation Research Part B, vol. 41, no. 2, pp. 265-280, 2001.
[7] A. Imai, E. Nishimura, S. Papadimitriou, “Berth allocation with service priority”, Transportation Research Part B, vol. 37, no. 5, pp. 437-457, 2003.
[8] A. Imai, J. T. Zhang, E. Nishimura, S. Papadimitriou, “The berth allocation problem with service time and delay time objectives”, Maritime Economics & Logistics, vol. 9, pp. 269-290, 2007.
[9] G. R. Mauri, A. C. M. Oliveira, L. A. N. Lorena, A Hybrid Column Generation Approach for the Berth Allocation Problem, Computer Science, vol. 4972, pp. 110-112, 2008.
[10] R. M. Mario, A. S. Miguel, B. Federico, “A GRASP-based metaheuristic for the Berth Allocation Problem and the Quay Crane Assignment Problem by managing vessel cargo holds”, Applied Intelligence, vol. 40, no. 2, pp. 273-290, 2013.
[11] G. K. D. Saharidis, M. M. Golias, M. Boile, S. Theofanis, M. G. Ierapetritou, “The berth scheduling problem with customer differentiation: a new methodological approach based on hierarchical optimization”, International Journal of Advanced Manufacturing Technology, vol. 46, no. 1-4, pp. 377-393, 2010.
[12] M. K. Li, T. L. Yip, “Joint planning for yard storage space and home berths in container terminals”, International Journal of Production Research, vol. 51, no. 10, pp. 3143-3155, 2013.
[13] M. K. Li, “A method for effective yard template design in container terminals”, European Journal of Industrial Engineering, vol. 8, no. 1, pp. 1–21, 2014.
[14] M. M. Golias, “A bi-objective berth allocation formulation to account for vessel handling time uncertainty”, Journal of Maritime Economics and Logistics, vol. 13, pp. 419–441, 2011.
[15] Y. Guan, R. K. Cheung, “The berth allocation problem: models and solution methods”, OR Spectrum, vol. 26, pp. 75-92, 2004.
[16] F. Wang, A. Lim, “A stochastic beam search for the berth allocation problem”, Decision Support Systems, vol. 42, no. 4, pp. 2186-2196, 2007.
[17] E. Nishimura, A. Imai, S. Papadimitriou, “Berth allocation planning in the public berth system by genetic algorithms”, European Journal of Operational Research, vol. 131, no. 2, pp. 282-292, 2001.
[18] A. Imai, E. Nishimura, S. Papadimitriou, “Berthing ships at a multi-user conatiner terminal with a limited quay capacity”, Transportation Research Part E, vol. 44, no. 1, pp. 136-151, 2008.
[19] P. Zhou, H. Kang, L. Lin, “A Dynamic Berth Allocation Model Based on Stochastic Consideration”, Proceedings of the 6th World Conference on Intelligent Control and Automation, Dalian China: IEEE, 7297–7301, 2006.
[20] P. Zhou, H. Kang, “Study on berth and quay-crane allocation under stochastic environments in container terminal”, Systems Engineering-Theory & Practice, vol. 28, no. 1, pp. 161–169, 2008.
[21] S. Theofanis, M. Boilé, M. M. Golias, “Container terminal berth planning: critical review of research approaches and practical challenges”, Transportation Research Record, pp. 22-28, 2010.
[22] Golias, M. M., Haralambides, H. E. (2011). Berth scheduling with variable cost functions. Journal of Maritime Economics and Logistics, 13, 174-189.
[23] B. Raa, W. Dullaert, R. V. Schaeren. “An enriched model for the integrated berth allocation and quay crane assignment problem”, Expert Systems with Application, vol. 38, no. 11, pp. 14136-14147, 2011.
[24] F. Meisel, C. Biewirth, “A Framework for Integrated Berth Allocation and Crane Operations Planning in Seaport Container Terminals”, Transportation Science, vol. 47, no. 2, pp. 131-147, 2013.
[25] C. Zhang, L. Zheng, Z. Zhang, L. Shi, A.L. Armstrong, “The allocation of berths and quay crane by using a sub-gradient optimization technique”, Computers and Industrial Engineering, vol. 58, no. 1, pp. 40-50, 2010.
[26] C. Liang, J. Guo, Y. Yang, “Multi-objective hybrid genetic algorithm for quay crane dynamic assignment in berth allocation planning”, Journal of Intelligent Manufacturing, vol. 22, no. 3, pp. 471-479, 2011.
[27] C. Liang, Y. Huang, M. Gen., “A berth allocation planning problem with direct transshipment consideration”, Journal of Intelligence Manufacturing, vol. 23, no. 6, pp. 2207-2214, 2012.
[28] D. Chang, Z. Jiang, W. Yan, J. He, “Integrating berth allocation and quay crane assignments”, Transportation Research Part E, vol. 46, no. 6, pp. 975-990, 2010.
[29] C. Liang, Y. Huang, Y. Yang, “A quay crane dynamic scheduling problem by hybrid evolutionary algorithm for berth allocation planning”, Computer and Industrial Engineering, vol. 56, no. 3, pp. 1021-1028, 2009.
[30] K. T. Park, K. H. Kim, “A scheduling method for berth and quay cranes”, OR spectrum, vol. 25, no. 1, pp. 1-23, 2003.
[31] I. Vacca, M. Salani, M. Bierlaire, “An Exact Algorithm for the Integrated Planning of Berth Allocation and Quay Crane Assignment”, Transportation Science, vol. 47, no. 2, pp. 148-161, 2013.
[32] J. F. Cordeau, G. Laporte, P. Legato, L. Moccia, “Models and tabu search heuristics for the berth-allocation problem”, Transportation Science, vol. 39, no. 4, pp. 526-538, 2005.
[33] P. Hansen, C. Oğuz, “Variable neighborhood search for minimum cost berth allocation”, European Journal of Operational Research, vol. 191, no. 3, pp. 636-649, 2008.
[34] F. Meisel, C. Bierwirth, “Integration of berth allocation and crane assignment to improve the resource utilization at a seaport container terminal”, In: Operations Research Proceedings 2006, Springer, 105–110.
[35] S. H. Chung, F. T. S. Chan, “A workload balancing genetic algorithm for the quay crane scheduling problem”, International Journal of Production Research, vol. 51, no. 16, pp. 4820-4834, 2013.