An exact algorithm for the unidirectional quay crane scheduling problem with vessel stability. (English) Zbl 1487.90328
Summary: This paper addresses the quay crane scheduling problem (QCSP) with vessel stability constraints. Vessel stability is essential to improve quay crane operations in container terminals, but it significantly complicates the basic QCSP and the corresponding solutions methods. We describe a novel mathematical formulation for the unidirectional QCSP with vessel stability, and we propose an exact algorithm based on logic-based Benders decomposition to solve the problem efficiently. The problem is decomposed into two subproblems, e.g., a task-assignment master problem without vessel stability constraints, and a time-allocation problem, aimed at determining the operation time of each task under the premise of the vessel stability requirements. The proposed algorithm is tested on benchmark instances derived from the literature, and the effectiveness of the proposed model and solution approach is demonstrated.
MSC:
| 90B35 | Deterministic scheduling theory in operations research |
Keywords:
OR in maritime industry; quay crane scheduling; vessel stability constraints; logic-based Benders decompositionReferences:
| [1] | Al-Dhaheri, N.; Diabat, A., The quay crane scheduling problem, Journal of Manufacturing Systems, 36, 87-94 (2015) |
| [2] | Al-Dhaheri, N.; Diabat, A., A Lagrangian relaxation-based heuristic for the multi-ship quay crane scheduling problem with ship stability constraints, Annals of Operations Research, 248, 1-2, 1-24 (2017) · Zbl 1357.90046 |
| [3] | Al-Dhaheri, N.; Jebali, A.; Diabat, A., The quay crane scheduling problem with nonzero crane repositioning time and vessel stability constraints, Computers & Industrial Engineering, 94, 230-244 (2016) |
| [4] | Benders, J. F., Partitioning procedures for solving mixed-variables programming problems (1962), Springer-Verlag New York, Inc. · Zbl 0109.38302 |
| [5] | Bierwirth, C.; Meisel, F., A fast heuristic for quay crane scheduling with interference constraints, Journal of Scheduling, 12, 4, 345-360 (2009) · Zbl 1185.90140 |
| [6] | Bierwirth, C.; Meisel, F., A survey of berth allocation and quay crane scheduling problems in container terminals, European Journal of Operational Research, 202, 3, 615-627 (2010) · Zbl 1176.90373 |
| [7] | Bierwirth, C.; Meisel, F., A follow-up survey of berth allocation and quay crane scheduling problems in container terminals, European Journal of Operational Research, 244, 3, 675-689 (2015) · Zbl 1346.90326 |
| [8] | Chen, J. H.; Bierlaire, M., The study of the unidirectional quay crane scheduling problem: Complexity and risk-aversion, European Journal of Operational Research, 260, 2, 613-624 (2017) · Zbl 1403.90313 |
| [9] | Chen, J. H.; Lee, D. H.; Goh, M., An effective mathematical formulation for the unidirectional cluster-based quay crane scheduling problem, European Journal of Operational Research, 232, 1, 198-208 (2014) · Zbl 1305.90176 |
| [10] | Codato, G.; Fischetti, M., Combinatorial Benders’ cuts for mixed-integer linear programming, Operations Research, 54, 4, 756-766 (2006) · Zbl 1167.90601 |
| [11] | Daganzo, C. F., The crane scheduling problem, Transportation Research Part B: Methodological, 23, 3, 159-175 (1989) |
| [12] | Guan, Y.; Yang, K.; Zhou, Z., The crane scheduling problem: Models and solution approaches, Annals of Operations Research, 203, 1, 119-139 (2013) · Zbl 1269.90041 |
| [13] | Hooker, J. N., Planning and scheduling by logic-based benders decomposition, Operations Research, 55, 3, 588-602 (2007) · Zbl 1167.90512 |
| [14] | Hooker, J. N., Logic-Based Methods for Optimization: Combining Optimization and Constraint Satisfaction (2000), John Wiley and Sons: John Wiley and Sons New York · Zbl 0974.90001 |
| [15] | Hooker, J. N.; Ottosson, G., Logic-based Benders decomposition, Mathematical Programming, 96, 1, 33-60 (2003) · Zbl 1023.90082 |
| [16] | Kim, K. H.; Park, Y.-M., A crane scheduling method for port container terminals, European Journal of Operational Research, 156, 3, 752-768 (2004) · Zbl 1062.90027 |
| [17] | Lee, D. H.; Wang, H. Q.; Miao, L., Quay crane scheduling with non-interference constraints in port container terminals, Transportation Research Part E Logistics & Transportation Review, 44, 1, 124-135 (2008) |
| [18] | Legato, P.; Trunfio, R.; Meisel, F., Modeling and solving rich quay crane scheduling problems, Computers & Operations Research, 39, 9, 2063-2078 (2012) · Zbl 1251.90163 |
| [19] | Liu, J.; Wan, Y. W.; Wang, L., Quay crane scheduling at container terminals to minimize the maximum relative tardiness of vessel departures, Naval Research Logistics, 53, 1, 60-74 (2006) · Zbl 1112.90031 |
| [20] | Meisel, F.; Bierwirth, C., A unified approach for the evaluation of quay crane scheduling models and algorithms, Computers & Operations Research, 38, 3, 683-693 (2011) |
| [21] | 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, 53, 1, 45-59 (2005) · Zbl 1112.90033 |
| [22] | Msakni, M. K.; Al-Salem, M.; Rabadi, G.; Kotachi, M.; Diabat, A., Quay crane scheduling with vessel stability, Transportation Research Procedia, 30, 60-69 (2018) |
| [23] | Stahlbock, R.; Vo, S., Operations research at container terminals: A literature update, OR Spectrum, 30, 1, 1-52 (2008) · Zbl 1133.90313 |
| [24] | Sun, D.; Meng, Y.; Tang, L.; Liu, J.; Huang, B.; Yang, J., Storage space allocation problem at inland bulk material stockyard, Transportation Research Part E: Logistics and Transportation Review, 134, 101856 (2020) |
| [25] | Sun, D.; Tang, L.; Baldacci, R., A Benders decomposition-based framework for solving quay crane scheduling problems, European Journal of Operational Research, 273, 2, 504-515 (2019) · Zbl 1403.90504 |
| [26] | Tang, L.; Jiang, W.; Liu, J.; Dong, Y., Research into container reshuffling and stacking problems in container terminal yards, IIE Transactions, 47, 751-766 (2015) |
| [27] | Tang, L.; Meng, Y., Data analytics and optimization for smart industry, Frontiers of Engineering Management, published online 26 August 2020. [Epub ahead of print] (2020) |
| [28] | Vis, I. F.A.; Koster, R. D., Transshipment of containers at a container terminal: An overview, European Journal of Operational Research, 147, 1, 1-16 (2003) · Zbl 1011.90005 |
| [29] | Wang, J.; Hu, H.; Song, Y., Optimization of quay crane scheduling constrained by stability of vessels, Transportation Research Record, 2330, 1, 47-54 (2013) |
| [30] | Wu, L.; Ma, W., Quay crane scheduling with draft and trim constraints, Transportation Research Part E: Logistics and Transportation Review, 97, 38-68 (2017) |
| [31] | Zhang, Z.; Ming, L.; Lee, C. Y.; Wang, J., The quay crane scheduling problem with stability constraints, IEEE Transactions on Automation Science & Engineering, PP, 99, 1-14 (2018) |
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.
