Quay Cranes and Yard Trucks Scheduling Problem at Container Terminals

Document Type: Original Article

Authors

Industrial & Systems Engineering Faculty, Tarbiat Modares University, Tehran, Iran

Abstract

A bi-objective mathematical model is developed to simultaneously consider the quay crane and yard truck scheduling problems at container terminals. Main real-world assumptions, such as quay cranes with non-crossing constraints, quay cranes’ safety margins and precedence constraints are considered in this model. This integrated approach leads to better efficiency and productivity at container terminals. Based on numerical experiments, the proposed mathematical model is effective for solving small-sized instances. Two versions of the simulated annealing algorithm are developed to heuristically solve the large-sized instances. Considering the allocation of trucks as a grouping problem, a grouping version of the simulated annealing algorithm is proposed. Effectiveness of the presented algorithms is compared to the optimal results of the mathematical model on small-sized problems. Moreover, the performances of the proposed algorithms on large-sized instances are compared with each other and the numerical results revealed that the grouping version of simulated annealing algorithm outperformed simulated annealing algorithm. Based on numerical investigations, there is a trade-off between the tasks’ completion time and the cost of utilizing more trucks. Moreover increasing the number of YTs leads to better outcomes than increasing the number of QCs. Besides two-cycle strategy and using dynamic assignment of yard truck to quay cranes leads to faster loading and unloading procedure.

Keywords


1.     Zegordi, S. H., and Nahavandi, N., “Measuring productivity indexes and efficiency in the container terminal at port Rajaei”, Scientia Iranica, Vol 9, No. 3, (2002), 248-254.
2.     UNCTAD, “Review of maritime transport 2018”. United Nations Conference on Trade and Development, (2018). https://doi.org/10.18356/cd4440fc-en
3.     Daganzo, C. F., "The crane scheduling problem", Transportation Research Part B: Methodological, Vol. 23, No. 3, (1989), 159-175. https://doi.org/10.1016/0191-2615(89)90001-5
4.     Kim, K. H., Park, Y. M., "A crane scheduling method for port container terminals", European Journal of Operational Research, Vol 156, No. 3 (2004), 752-768. https://doi.org/10.1016/s0377-2217 (03)00133-4
5.     Moccia, L., Cordeau, J. F., Gaudioso, M., Laporte, G. "A branch‐and‐cut algorithm for the quay crane scheduling problem in a container terminal", Naval Research Logistics, Vol 53, No. 1 (2006), 45-59. https://doi.org/10.1002/nav.20121
6.     Nguyen, S., Zhang, M., Johnston, M., Tan, K. C. "Hybrid evolutionary computation methods for quay crane scheduling problems." Computers and Operations Research, Vol. 40, No. 8 (2013), 2083-2093. https://doi.org/10.1016/j.cor.2013.03.007
7.     Kaveshgar, N., Huynh, N., Rahimian, S. K., "An efficient genetic algorithm for solving the quay crane scheduling problem", Expert Systems with Applications, Vol. 39, No. 18, (2012), 13108-13117. https://doi.org/10.1016/j.eswa.2012.05.091
8.     Tavakkoli-Moghaddam, R., Makui, A., Salahi, S., Bazzazi, M., Taheri, F., "An efficient algorithm for solving a new mathematical model for a quay crane scheduling problem in container ports", Computers and Industrial Engineering, Vol. 56, No. 1 (2009), 241-248. https://doi.org/10.1016/j.cie.2008.05.011
9.     Emde, S. "Optimally scheduling interfering and non‐interfering cranes", Naval Research Logistics, Vol. 64, No. 6, (2017), 476-489. https://doi.org/10.1002/nav.21768
10.   Sammarra, M., Cordeau, J. F., Laporte, G., Monaco, M. F., "A tabu search heuristic for the quay crane scheduling problem", Journal of Scheduling, Vol 10, No. 4-5 (2007), 327-336. https://doi.org/10.1007/s10951-007-0029-5
11.   Legato, P., Trunfio, R., & Meisel, F. “Modeling and solving rich quay crane scheduling problems” Computers and Operations Research, Vol. 39, No. 9, (2012), 2063-2078. https://doi.org/10.1016/j.cor.2011.09.025
12.   Chen, J. H., Bierlaire, M., “The study of the unidirectional quay crane scheduling problem: complexity and risk-aversion. European”, Journal of Operational Research, Vol. 260, No. 2, (2017), 613-624. https://doi.org/10.1016/j.ejor.2017.01.007
13.   Bierwirth, C., Meisel, F., "A survey of berth allocation and quay crane scheduling problems in container terminals", European Journal of Operational Research, Vol 202, No. 3 (2010), 615-627. https://doi.org/10.1016/j.ejor.2009.05.031
14.   Bierwirth, C., Meisel, F., "A follow-up survey of berth allocation and quay crane scheduling problems in container terminals", European Journal of Operational Research, Vol. 244, No. 3 (2015), 675-689. https://doi.org/10.1016/j.ejor.2014.12.030
15.   Chen, L., Bostel, N., Dejax, P., Cai, J., & Xi, L. "A tabu search algorithm for the integrated scheduling problem of container handling systems in a maritime terminal", European Journal of Operational Research, Vol 181, No. 1 (2007), 40-58. https://doi.org/10.1016/j.ejor.2006.06.033
16.   Tang, L., Zhao, J., & Liu, J. "Modeling and solution of the joint quay crane and truck scheduling problem." European Journal of Operational Research, Vol 236, No. 3, (2014), 978-990. https://doi.org/10.1016/j.ejor.2013.08.050
17.   Kaveshgar, N., & Huynh, N. "Integrated quay crane and yard truck scheduling for unloading inbound containers." International Journal of Production Economics, Vol 159 (2015), 168-177. https://doi.org/10.1016/j.ijpe.2014.09.028
18.   Vahdani, B., Mansour, F., Soltani, M., & Veysmoradi, D. "Bi-objective optimization for integrating quay crane and internal truck assignment with challenges of trucks sharing." Knowledge-Based Systems, Vol 163, (2019), 675-692. https://doi.org/10.1016/j.knosys.2018.09.025
19.   Fazli, M., Fathollahi-Fard, A. M., Tian, G., “Addressing a Coordinated Quay Crane Scheduling and Assignment Problem by Red Deer Algorithm”, International Journal of Engineering, Transactions B: Applications, Vol. 32, No. 8, (2019), 1186-1191.
https://doi.org/10.5829/ije.2019.32.08b.15
20.   Behjat, S., & Nahavandi, N. “A Mathematical Model and Grouping Imperialist Competitive Algorithm for Integrated Quay Crane and Yard Truck Scheduling Problem with Non-crossing Constraint” International Journal of Engineering, Transcation A: Basics, Vol. 32, No. 10, (2019), 1464-1479. https://doi.org/10.5829/ije.2019.32.10a.16
21.   Pinedo, M. Scheduling. New York: Springer, 2012. https://doi.org/10.1007/978-1-4614-2361-4
22.   Kirkpatrick, S., Gelatt, C. D., Vecchi, M. P. “Optimization by simulated annealing”, Science, Vol. 220, No. 4598, (1983), 671-680. https://doi.org/10.1126/science.220.4598.671
23.   Nikabadi, M., & Naderi, R. “A hybrid algorithm for unrelated parallel machines scheduling.” International Journal of Industrial Engineering Computations, Vol. 7, No. 4, (2016), 681-702. https://doi.org/10.5267/j.ijiec.2016.2.004
24.   Kashan, A. H., Kashan, M. H., Karimiyan, S. "A particle swarm optimizer for grouping problems." Information Sciences, Vol. 252, (2013), 81-95. https://doi.org/10.1016/j.ins.2012.10.036