An exact method for scheduling a yard crane.

*(English)*Zbl 1305.90182Summary: This paper studies an operational problem arising at a container terminal, consisting of scheduling a yard crane to carry out a set of container storage and retrieval requests in a single container block. The objective is to minimize the total travel time of the crane to carry out all requests. The block has multiple input and output (I/O) points located at both the seaside and the landside. The crane must move retrieval containers from the block to the I/O points, and must move storage containers from the I/O points to the block. The problem is modeled as a continuous time integer programming model and the complexity is proven. We use intrinsic properties of the problem to propose a two-phase solution method to optimally solve the problem. In the first phase, we develop a merging algorithm which tries to patch subtours of an optimal solution of an assignment problem relaxation of the problem and obtain a complete crane tour without adding extra travel time to the optimal objective value of the relaxed problem. The algorithm requires common I/O points to patch subtours. This is efficient and often results in obtaining an optimal solution of the problem. If an optimal solution has not been obtained, the solution of the first phase is embedded in the second phase where a branch-and-bound algorithm is used to find an optimal solution. The numerical results show that the proposed method can quickly obtain an optimal solution of the problem. Compared to the random and Nearest Neighbor heuristics, the total travel time is on average reduced by more than 30% and 14%, respectively. We also validate the solution method at a terminal.

##### MSC:

90B35 | Deterministic scheduling theory in operations research |

90B06 | Transportation, logistics and supply chain management |

##### Keywords:

container storage and retrieval; sequencing; multiple I/O points; travel time; traveling salesman problem
PDF
BibTeX
XML
Cite

\textit{A. H. Gharehgozli} et al., Eur. J. Oper. Res. 235, No. 2, 431--447 (2014; Zbl 1305.90182)

Full Text:
DOI

##### References:

[1] | Bellmore, M.; Nemhauser, G. L., The traveling salesman problem: A survey, Operations Research, 16, 3, 538-558, (1968) · Zbl 0213.44604 |

[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] | Böse, J. W., Handbook of terminal planning, (2011), Springer New York |

[4] | Burkard, R. E.; Deineko, V. G.; Van Dal, R.; Van der Veen, J. A.A.; Woeginger, G. J., Well-solvable special cases of the traveling salesman problem: A survey, SIAM Review, 40, 3, 496-546, (1998) · Zbl 1052.90597 |

[5] | Carpaneto, G.; Dell’Amico, M.; Toth, P., Exact solution of large-scale, asymmetric traveling salesman problems, ACM Transaction on Mathematical Software, 21, 4, 394-409, (1995) · Zbl 0887.65058 |

[6] | Carpaneto, G.; Toth, P., Some new branching and bounding criteria for the asymmetric travelling salesman problem, Management Science, 26, 7, 736-743, (1980) · Zbl 0445.90089 |

[7] | Cheung, R. K.; Li, C. L.; Lin, W., Interblock crane deployment in container terminals, Transportation Science, 36, 1, 79-93, (2002) · Zbl 1065.90514 |

[8] | Clausen, J. (2003). Branch and bound algorithms - Principles and examples. Department of Computer Science, University of Copenhagen. |

[9] | De Castillo, B.; Daganzo, C. F., Handling strategies for import containers at marine terminals, Transportation Research Part B: Methodological, 27, 2, 151-166, (1993) |

[10] | De Koster, R.; Balk, B. M.; Van Nus, W. T.I., On using dea for benchmarking container terminals, International Journal of Operations and Production Management, 29, 11, 1140-1155, (2009) |

[11] | De Koster, R.; Van der Poort, E., Routing orderpickers in a warehouse: a comparison between optimal and heuristic solutions, IIE Transactions, 30, 469-480, (1998) |

[12] | Dorndorf, U.; Schneider, F., Scheduling automated triple cross-over stacking cranes in a container yard, OR Spectrum, 32, 3, 617-632, (2010) · Zbl 1200.90072 |

[13] | Drewry, Container forecaster, (2011), Drewery Publications London |

[14] | Eastman, W. L. (1958). Linear programming with pattern constraints. Dissertation, Harvard University. |

[15] | Gharehgozli, A. H., Laporte, G., Yu, Y., & De Koster, R. (2013). Scheduling two yard cranes handling requests with precedences in a container block with multiple open locations. Tech. rep., Rotterdam. |

[16] | Gilmore, P. C.; Gomory, R. E., Sequencing a one state-variable machine: A solvable case of the traveling salesman problem, Operations Research, 12, 5, 655-679, (1964) · Zbl 0126.36006 |

[17] | Itai, A.; Papadimitriou, C. H.; Swarcfiter, J. L., Hamilton paths in grid graphs, SIAM Journal on Computing, 11, 676-686, (1982) · Zbl 0506.05043 |

[18] | Karp, R. M., Reducibility among combinatorial problems, (Miller, R. E.; Thatcher, J. W., Complexity of computer computations, (1972), Plenum Press), 85-103 |

[19] | Kim, K. H.; Kim, K. Y., An optimal routing algorithm for a transfer crane in port container terminals, Transportation Science, 33, 1, 17-33, (1999) · Zbl 1002.90508 |

[20] | Kim, K. H.; Park, Y. M.; Ryu, K. R., Deriving decision rules to locate export containers in container yards, European Journal of Operational Research, 124, 1, 89-101, (2000) · Zbl 0960.90002 |

[21] | Kuhn, H. W., The Hungarian method for the assignment problem, Naval Research Logistic Quarterly, 2, 83-97, (1955) · Zbl 0143.41905 |

[22] | Laporte, G., The traveling salesman problem: an overview of exact and approximate algorithms, European Journal of Operational Research, 59, 2, 231-247, (1992) · Zbl 0760.90089 |

[23] | Law, A. M.; Kelton, D. M., Simulation modeling and analysis, (1999), McGraw-Hill Higher Education Boston, Massachusetts |

[24] | Lawler, E. L.; Lenstra, J. K.; Rinnooy Kan, A. H.G.; Shmoys, D. B., The traveling salesman problem, a guided tour of combinatorial optimization, (1985), John Wiley & Sons Chichester, UK · Zbl 0562.00014 |

[25] | Li, W.; Goh, M.; Wu, Y.; Petering, M. E.H.; De Souza, R.; Wu, Y. C., A continuous time model for multiple yard crane scheduling with last minute job arrivals, International Journal of Production Economics, 136, 2, 332-343, (2012) |

[26] | Linn, R. J.; Zhang, C. Q., A heuristic for dynamic yard crane deployment in a container terminal, IIE Transactions, 35, 2, 161-174, (2003) |

[27] | Li, W.; Wu, Y.; Petering, M. E.H.; Goh, M.; de Souza, R., Discrete time model and algorithms for container yard crane scheduling, European Journal of Operational Research, 198, 1, 165-172, (2009) · Zbl 1163.90496 |

[28] | Miller, D. L.; Pekny, J. F., Exact solution of large asymmetric traveling salesman problems, Science, 251, 4995, 754-761, (1991) |

[29] | Murty, K. G., Yard crane pools and optimum layouts for storage yards of container terminals, Journal of Industrial and Systems Engineering, 1, 190-199, (2007) |

[30] | Narasimhan, A.; Palekar, U. S., Analysis and algorithms for the transtainer routing problem in container port operations, Transportation Science, 36, 1, 63-78, (2002) · Zbl 1065.90511 |

[31] | Ng, W. C., Crane scheduling in container yards with inter-crane interference, European Journal of Operational Research, 164, 1, 64-78, (2005) · Zbl 1132.90331 |

[32] | Port of Rotterdam Authority (Ed.). (2010). Port statistics. Port of Rotterdam Authority, Rotterdam. |

[33] | Ratliff, H. D.; Rosenthal, A. S., Order-picking in a rectangular warehouse: A solvable case of the traveling salesman problem, Operations Research, 31, 3, 507-521, (1983) · Zbl 0523.90060 |

[34] | Stahlbock, R.; Voß, S., Operations research at container terminals: A literature update, OR Spectrum, 30, 1, 1-52, (2008) · Zbl 1133.90313 |

[35] | Steenken, D.; Voß, S.; Stahlbock, R., Container terminal operation and operations research - A classification and literature review, OR Spectrum, 26, 3-49, (2004) · Zbl 1160.90322 |

[36] | Ultimate (2013). Ultimate: Efficient multimodal. <http://www.dinalog.nl/en/projects/r_d_projects/ultimate__efficient_multimodal/> Retrieved 03.01.13. |

[37] | United Nations: ESCAP (2007). Regional shipping and port development: Container traffic forecast 2007 update. United Nations: Economic and Social Comission for Asia and the Pacific (ESCAP), New York. |

[38] | Van den Berg, J. P.; Gademann, A. J.R. M., Optimal routing in an automated storage/retrieval system with dedicated storage, IIE Transactions, 31, 5, 407, (1999) |

[39] | Vis, I. F.A.; Carlo, H. J., Sequencing two cooperating automated stacking cranes in a container terminal, Transportation Science, 44, 2, 169-182, (2010) |

[40] | Vis, I. F.A.; Roodbergen, K. J., Scheduling of container storage and retrieval, Operations Research, 57, 2, 456-467, (2009) · Zbl 1181.90129 |

[41] | Wan, Y. W.; Liu, J.; Tsai, P. C., The assignment of storage locations to containers for a container stack, Naval Research Logistics (NRL), 56, 8, 699-713, (2009) · Zbl 1177.90256 |

[42] | Wiese, J.; Suhl, L.; Kliewer, N., Mathematical models and solution methods for optimal container terminal yard layouts, OR Spectrum, 32, 3, 427-452, (2010) · Zbl 1200.90025 |

[43] | Zhang, C.; Wan, Y. W.; Liu, J.; Linn, R. J., Dynamic crane deployment in container storage yards, Transportation Research Part B: Methodological, 36, 6, 537-555, (2002) |

[44] | Zrnić, N., & Vujičić (2012). Evaluation of environmental benefits of CHE emerging technology by using LCA. In Proceedings of IMHRC 2012. |

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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.