×

Combining mixed integer programming and constraint programming to solve the integrated scheduling problem of container handling operations of a single vessel. (English) Zbl 1443.90191

Summary: In the container terminals of seaports, the container handling system consists of a variety of container handling machines such as quay cranes, internal yard trucks, and yard cranes. This study applies a holistic approach to the integrated scheduling of these machines for the container handling operations of a single vessel. We formulate this special hybrid flow shop scheduling problem through both mixed integer programming (MIP) and constraint programming (CP) techniques. Then we develop an easily-implemented approach that combines the strengths of MIP and CP. First, the MIP model, which only considers quay crane scheduling, is solved by an MIP solver, and a quay crane allocation plan is retrieved from the MIP solution. Then, this quay crane allocation plan is fed to the CP model, warm-starting the branch-and-prune algorithm built in a CP optimizer. Our numerical experiments reveal that this hybrid MIP/CP approach can solve the large-sized instances with up to 1000 containers, 6 quay cranes, 36 yard trucks, and 15 yard cranes to optimality with a gap of less than 3.31%, within a solution time of 2 minutes. If we increase the solution time to 5 minutes, this hybrid approach solves larger instances with up to 1400 containers to optimality with a gap of less than 1.41%. The state-of-the-art dedicated algorithms reported in the literature (which address an easier version of the same problem by ignoring non-crossing constraints and safety margins between quay cranes) are only able to find solutions for real-life instances with up to 500 containers within the solution time of 2930 or 5221 seconds, leaving a 4% or an unknown optimality gap. Thus, this study improves the solution of this integrated scheduling problem in terms of the instance size, solution efficiency, and solution optimality.

MSC:

90B35 Deterministic scheduling theory in operations research
90C11 Mixed integer programming

Software:

COMET
Full Text: DOI

References:

[1] 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
[2] 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
[3] 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
[4] Boysen, N.; Briskorn, D.; Meisel, F., A generalized classification scheme for crane scheduling with interference, European Journal of Operational Research, 258, 1, 343-357 (2017) · Zbl 1380.90108
[5] Carlo, H.; Vis, I.; Roodbergen, K., Storage yard operations in container terminals: Literature overview, trends, and research directions, European Journal of Operational Research, 235, 2, 412-430 (2014) · Zbl 1305.90007
[6] Carlo, H.; Vis, I.; Roodbergen, K., Transport operations in container terminals: Literature overview, trends, research directions and classification scheme, European Journal of Operational Research, 236, 1, 1-13 (2014) · Zbl 1338.90003
[7] Carlo, H.; Vis, I.; Roodbergen, K., Seaside operations in container terminals: literature overview, trends, and research directions, Flexible Services and Manufacturing Journal, 27, 2-3, 224-262 (2015)
[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] 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, 181, 1, 40-58 (2007) · Zbl 1121.90054
[11] Chen, L.; Langevin, A.; Lu, Z., Integrated scheduling of crane handling and truck transportation in a maritime container terminal, European Journal of Operational Research, 225, 1, 142-152 (2013) · Zbl 1292.90184
[12] Daganzo, C. F., The crane scheduling problem, Transportation Research Part B: Methodological, 23, 3, 159-175 (1989)
[13] Homayouni, S.; Fontes, D., Metaheuristics for maritime operations (2018), Wiley
[14] 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
[15] Laborie, P.; Rogerie, J., Reasoning with conditional time-intervals, Proceedings of the FLAIRS conference, 555-560 (2008)
[16] Lee, D. H.; Chen, J. H., An improved approach for quay crane scheduling with non-crossing constraints, Engineering Optimization, 42, 1, 1-15 (2010)
[17] Legato, P.; Trunfio, R., A local branching-based algorithm for the quay crane scheduling problem under unidirectional schedules, 4OR, 1-34 (2013)
[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] Li, C.-L.; Vairaktarakis, G. L., Loading and unloading operations in container terminals, IIE Transactions, 36, 4, 287-297 (2004)
[20] Lim, A.; Rodrigues, B.; Xu, Z., A m-parallel crane scheduling problem with a non-crossing constraint, Naval Research Logistics (NRL), 54, 2, 115-127 (2007) · Zbl 1126.90025
[21] 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
[22] Meisel, F., The quay crane scheduling problem with time windows, Naval Research Logistics (NRL), 58, 7, 619-636 (2011) · Zbl 1241.90052
[23] 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)
[24] 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 (NRL), 53, 1, 45-59 (2006) · Zbl 1112.90033
[25] Ruiz, R.; Vázquez-Rodríguez, J. A., The hybrid flow shop scheduling problem, European Journal of Operational Research, 205, 1, 1-18 (2010) · Zbl 1188.90110
[26] Sammarra, M.; Cordeau, J.-F.; Laporte, G.; Monaco, M. F., A tabu search heuristic for the quay crane scheduling problem, Journal of Scheduling, 10, 4-5, 327-336 (2007) · Zbl 1168.90468
[27] Steenken, D.; Vob, S.; Stahlbock, R., Container terminal operation and operations research a classification and literature review, OR Spectrum, 26, 3-49 (2004) · Zbl 1160.90322
[28] Tang, L.; Zhao, J.; Liu, J., Modeling and solution of the joint quay crane and truck scheduling problem, European Journal of Operational Research, 236, 3, 978-990 (2014) · Zbl 1304.90103
[29] Unsal, O.; Oguz, C., Constraint programming approach to quay crane scheduling problem, Transportation Research Part E: Logistics and Transportation Review, 59, 108-122 (2013)
[30] Unsal, O.; Oguz, C., An exact algorithm for integrated planning of operations in dry bulk terminals, Transportation Research Part E: Logistics and Transportation Review, 126, 103-121 (2019)
[31] Van Hentenryck, P.; Michel, L., Constraint-based local search (2009), The MIT press
[32] Yi, D. W.; Kim, S. H.; Choi, H. R.; Park, N.-K.; Lee, T. W., Developing a conceptual model for sharing container terminal resources: a case study of the Gamman container terminal, Maritime Policy & Management, 27, 2, 155-167 (2000)
[33] Zeng, Q.; Yang, Z., Integrating simulation and optimization to schedule loading operations in container terminals, Computers and Operations Research, 36, 6, 1935-1944 (2009) · Zbl 1179.90169
[34] Zhen, L.; Yu, S.; Wang, S.; Sun, Z., Scheduling quay cranes and yard trucks for unloading operations in container ports, Annals of Operations Research (2016) · Zbl 1410.90101
[35] Zhu, Y.; Lim, A., Crane scheduling with non-crossing constraint, Journal of the Operational Research Society, 57, 12, 1464-1471 (2006) · Zbl 1123.90042
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.