×
Rodrigues, Filipe; Agra, Agostinho

Handling uncertainty in the quay crane scheduling problem: a unified distributionally robust decision model. (English) Zbl 07797294

Int. Trans. Oper. Res. 31, No. 2, 721-748 (2024).
Summary: Quay cranes are among the most important resources in port terminals, and their efficient use is crucial for port terminals to remain competitive in the market. The problem of determining the sequence of tasks performed by the quay cranes that minimizes the turnaround time of a vessel is an NP-hard problem known as the quay crane scheduling problem (QCSP). In this paper, we consider the unidirectional QCSP under uncertain processing times, where the cranes are only allowed to move in a specific direction. We start by presenting the first distributionally robust optimization (DRO) model for this problem and an exact decomposition algorithm to solve it. The proposed DRO model makes it possible to derive a stochastic programming model and a robust optimization model for the unidirectional QCSP by an appropriate choice of the risk-averse parameter of the model. Through extensive numerical results, we compare these three approaches – stochastic programming, robust optimization, and DRO – to investigate whether significant differences among the solutions obtained exist. Finally, we propose a new method for helping practitioners to determine a representative set of different DRO solutions.
© 2023 The Authors. International Transactions in Operational Research published by John Wiley & Sons Ltd on behalf of International Federation of Operational Research Societies

Cited in 4 Documents

MSC:

90-XX Operations research, mathematical programming

Keywords:

quay crane scheduling; distributionally robust optimization; Wasserstein distance; uncertainty; unidirectional
Cite Review PDF
Full Text: DOI
OA License

References:

[1] Agra, A., Rodrigues, F., 2022. Distributionally robust optimization for the berth allocation problem under uncertainty. Transportation Research Part B: Methodological164, 1-24.
[2] Al‐Dhaheri, N., Jebali, A., Diabat, A., 2016. A simulation‐based genetic algorithm approach for the quay crane scheduling under uncertainty. Simulation Modelling Practice and Theory66, 122-138.
[3] Atak, U., Kaya, T., Arslanoglu, Y., 2016. Analysing the effects of weather conditions on container terminal operations using machine learning. International Journal of Business Analytics9, 5, 5-17.
[4] Bansal, M., Huang, K.L., Mehrotra, S., 2018. Decomposition algorithms for two‐stage distributionally robust mixed binary programs. SIAM Journal on Optimization28, 3, 2360-2383. · Zbl 1401.90126
[5] Bayraksan, G., Love, D.K., 2015. Data‐driven stochastic programming using phi‐divergences. In Aleman, D.M. (ed.), Thiele, A.C. (ed.) (eds) The Operations Research Revolution. INFORMS TutORials in Operations Research. INFORMS, Catonsville, MD, pp. 1-19.
[6] Bierwirth, C., Meisel, F., 2010. A survey of berth allocation and quay crane scheduling problems in container terminals. European Journal of Operational Research202, 615-627. · Zbl 1176.90373
[7] Bierwirth, C., Meisel, F., 2015. A follow‐up survey of berth allocation and quay crane scheduling problems in container terminals. European Journal of Operational Research224, 3, 675-689. · Zbl 1346.90326
[8] Bruni, M., Khodaparasti, S., Demeulemeester, E., 2020. The distributionally robust machine scheduling problem with job selection and sequence‐dependent setup times. Computers & Operations Research123, 105017. · Zbl 1458.90263
[9] Cao, Y., Zhu, X., Yan, H., 2022. Data‐driven Wasserstein distributionally robust mitigation and recovery against random supply chain disruption. Transportation Research, Part E: Logistics and Transportation Review163, 102751.
[10] Chang, Z., Ding, J.Y., Song, S., 2019. Distributionally robust scheduling on parallel machines under moment uncertainty. European Journal of Operational Research272, 3, 832-846. · Zbl 1403.90382
[11] Chargui, K., Zouadi, T., Sreedharan, V.R., Fallahi, A.E., Reghioui, M., 2022. A novel proactive‐reactive scheduling approach for the quay crane scheduling problem: a VUCA perspective. IEEE Transactions on Engineering Management. https://doi.org/10.1109/TEM.2022.3151842 · doi:10.1109/TEM.2022.3151842
[12] Chen, J.H., Bierlaire, M., 2017. The study of the unidirectional quay crane scheduling problem: complexity and risk‐aversion. European Journal of Operational Research260, 2, 613-624. · Zbl 1403.90313
[13] Chen, J.H., Lee, D.H., Goh, M., 2014. An effective mathematical formulation for the unidirectional cluster‐based quay crane scheduling problem. European Journal of Operational Research232, 1, 198-208. · Zbl 1305.90176
[14] Chhetri, P., Jayatilleke, G.B., Gekara, V.O., Manzoni, A., Corbitt, B., 2016. Container terminal operations simulator (CTOS)—simulating the impact of extreme weather events on port operation. European Journal of Transport and Infrastructure Research16, 1, 195-213.
[15] Choo, S., Klabjan, D., Simchi‐Levi, D., 2010. Multiship crane sequencing with yard congestion constraints. Transportation Science44, 1, 98-115.
[16] Daganzo, C.F., 1989. The crane scheduling problem. Transportation Research Part B: Methodological23, 3, 159-175.
[17] Esfahani, P.M., Kuhn, D., 2018. Data‐driven distributionally robust optimization using the Wasserstein metric: performance guarantees and tractable reformulations. Mathematical Programming171, 1, 115-171. · Zbl 1433.90095
[18] Expósito‐Izquiero, C., Lalla‐Ruiz, E., Lamata, T., Melián‐Batista, B., Moreno‐Vega, J.M., 2016. Fuzzy optimization models for seaside port logistics: berthing and quay crane scheduling. In Madani, K. (ed.), Dourado, A. (ed.), Rosa, A. (ed.), Filipe, J. (ed.), Kacprzyk, J. (ed.) (eds), Computational Intelligence. Studies in Computational Intelligence, Vol. 613. Springer International Publishing, Cham, pp. 323-343.
[19] Faccini, D., Maggioni, F., Potra, F.A., 2022. Robust and distributionally robust optimization models for linear support vector machine. Computers & Operations Research147, 105930. · Zbl 1520.68141
[20] Gao, R., Kleywegt, A.J., 2016. Distributionally robust stochastic optimization with Wasserstein distance. Technical report, arXiv preprint arXiv:1604.02199v2.
[21] Garcia‐Alonso, L., Moura, T., Roibas, D., 2020. The effect of weather conditions on port technical efficiency. Marine Policy113, 103816.
[22] Gharehgozli, A., Roy, D., De Koster, R., 2016. Sea container terminals: new technologies and or models. Maritime Economics and Logistics18, 2, 103-140.
[23] Guo, L., Wang, J., Zheng, J., 2021. Berth allocation problem with uncertain vessel handling times considering weather conditions. Computers & Industrial Engineering158, 107417.
[24] Hu, H., Chen, X., Zhang, S., 2019. Optimisation for quay crane scheduling problem under uncertainty using PSO and OCBA. International Journal of Shipping and Transport Logistics11, 2‐3, 196-215.
[25] Kim, K.H., Park, Y.M., 2004. A crane scheduling method for port container terminals. European Journal of Operational Research156, 3, 752-768. · Zbl 1062.90027
[26] Kizilay, D., Eliiyi, D., 2021. A comprehensive review of quay crane scheduling, yard operations and integrations thereof in container terminals. Flexible Services and Manufacturing Journal33, 1, 1-42.
[27] Lee, C.Y., Liu, M., Chu, C., 2015. Optimal algorithm for the general quay crane double‐cycling problem. Transportation Science49, 4, 957-967.
[28] Lee, D.H., Wang, H.Q., Miao, L., 2008. Quay crane scheduling with non‐interference constraints in port container terminals. Transportation Research Part E: Logistics and Transportation Review44, 1, 124-135.
[29] Legato, P., Trunfio, R., 2014. A local branching‐based algorithm for the quay crane scheduling problem under unidirectional schedules. 4OR12, 2, 123-156. · Zbl 1307.90096
[30] Legato, P., Trunfio, R., Meisel, F., 2012. Modeling and solving rich quay crane scheduling problems. Computers & Operations Research39, 9, 2063-2078. · Zbl 1251.90163
[31] Li, Y., Zhang, C., 2021. Exact algorithms for robust quay crane scheduling problems. In 2021 IEEE International Conference on Industrial Engineering and Engineering Management (IEEM). IEEE, Piscataway, NJ, pp. 1631-1635.
[32] Lim, A., Rodrigues, B., Xiao, F., Zhu, Y., 2004a. Crane scheduling with spatial constraints. Naval Research Logistics51, 3, 386-406. · Zbl 1054.90036
[33] Lim, A., Rodrigues, B., Xu, Z., 2004b. Approximation schemes for the crane scheduling problem. In Hagerup, T. (ed.), Katajainen, J. (ed.) (eds), Algorithm Theory—SWAT 2004, Springer Berlin Heidelberg, Berlin, pp. 323-335. · Zbl 1095.90551
[34] Liu, C., Zheng, L., Zhang, C., 2016. Behavior perception-based disruption models for berth allocation and quay crane assignment problems. Computers & Industrial Engineering97, 258-275.
[35] Liu, J., Wan, Y.w., Wang, L., 2006. Quay crane scheduling at container terminals to minimize the maximum relative tardiness of vessel departures. Naval Research Logistics53, 1, 60-74. · Zbl 1112.90031
[36] Ma, S., Li, H., Zhu, N., Fu, C., 2021. Stochastic programming approach for unidirectional quay crane scheduling problem with uncertainty. Journal of Scheduling24, 2, 137-174.
[37] Meisel, F., Bierwirth, C., 2011. A unified approach for the evaluation of quay crane scheduling models and algorithms. Computers & Operations Research38, 3, 683-693.
[38] Nourmohammadzadeh, A., Voß, S., 2022. A robust multiobjective model for the integrated berth and quay crane scheduling problem at seaside container terminals. Annals of Mathematics and Artificial Intelligence90, 831-853. · Zbl 07570856
[39] Novak, A., Gnatowski, A., Sucha, P., 2022. Distributionally robust scheduling algorithms for total flow time minimization on parallel machines using norm regularizations. European Journal of Operational Research302, 2, 438-455. · Zbl 1507.90066
[40] Qiu, R., Sun, Y., Sun, M., 2021. A distributionally robust optimization approach for multi‐product inventory decisions with budget constraint and demand and yield uncertainties. Computers & Operations Research126, 105081. · Zbl 1510.90018
[41] Rahimian, H., Mehrotra, S., 2019. Distributionally robust optimization: a review. Technical report, arXiv preprint arXiv:1908.05659.
[42] Rodrigues, F., Agra, A., 2021. An exact robust approach for the integrated berth allocation and quay crane assignment problem under uncertain arrival times. European Journal of Operational Research295, 2, 499-516. · Zbl 1487.90316
[43] Rodrigues, F., Agra, A., 2022. Berth allocation and quay crane assignment/scheduling problem under uncertainty: a survey. European Journal of Operational Research303, 2, 501-524. · Zbl 1524.90153
[44] Rouky, N., Abourraja, M., Boukachour, J., Boudebous, D., Alaoui, A., Khoukhi, F., 2019. Simulation optimization based ant colony algorithm for the uncertain quay crane scheduling problem. International Journal of Industrial Engineering Computations10, 1, 111-132.
[45] Shang, X.T., Cao, J.X., Ren, J., 2016. A robust optimization approach to the integrated berth allocation and quay crane assignment problem. Transportation Research Part E: Logistics and Transportation Review94, 44-65.
[46] Shehadeh, K.S., 2022. Data‐driven distributionally robust surgery planning in flexible operating rooms over a Wasserstein ambiguity. Computers & Operations Research146, 105927. · Zbl 1520.90141
[47] Stahlbock, R., Voss, S., 2008. Operations research at container terminals: a literature update. OR Spectrum30, 1-52. · Zbl 1133.90313
[48] Sun, D., Tang, L., Baldacci, R., Lim, A., 2021. An exact algorithm for the unidirectional quay crane scheduling problem with vessel stability. European Journal of Operational Research291, 1, 271-283. · Zbl 1487.90328
[49] Tasoglu, G., Yildiz, G., 2019. Simulated annealing based simulation optimization method for solving integrated berth allocation and quay crane scheduling problems. Simulation Modelling Practice and Theory97, 101948.
[50] UNCTAD, 2021. Review of maritime transport, 2021. Technical report, United Nations, New York.
[51] Vis, I.F., deKoster, R., 2003. Transshipment of containers at a container terminal: An overview. European Journal of Operational Research147, 1, 1-16. · Zbl 1011.90005
[52] Wang, W., Yang, K., Yang, L., Gao, Z., 2021. Two‐stage distributionally robust programming based on worst‐case mean‐CVaR criterion and application to disaster relief management. Transportation Research Part E: Logistics and Transportation Review149, 102332.
[53] Zhang, Z., Liu, M., Lee, C.Y., Wang, J., 2018. The quay crane scheduling problem with stability constraints. IEEE Transactions on Automation Science and Engineering15, 3, 1399-1412.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.