Reducing simulation costs of embedded simulation in yard crane dispatching in container terminals

ABSTRACT

Embedding simulation in optimization algorithms will incur computational costs. For NP-hard problems the computational costs of the embedded simulation in the optimization algorithm are likely to be substantial. YC dispatching is NP-hard. So it is very important to be able to minimize simulation costs in YC dispatching algorithms. In the optimization algorithm for yard crane dispatching published, simulation of YC operations of the entire (partial) sequence of YC jobs are carried out each time the tardiness of a (partial) sequence needs to be evaluated. In this paper we study two approaches to reduce simulation costs in these embedded simulations in the optimization algorithm. Experimental results show that one approach significantly reduces the computational time of the optimization algorithm. We also analyze the reasons for the other approach which fails to reduce the computational time.

References

1. Cao, Z., D. H. Lee, and Q. Meng. 2008. Deployment strategies of double-rail-mounted gantry crane systems for loading outbound containers in container terminals, International Journal of Production Economics, 115, 221--228.
2. Chu, C. 1992. A branch-and-bound algorithm to minimize total tardiness with different release dates, In Naval Research Logistics, 39(2), 265--283.
3. Guo, X., S. Y. Huang, W. J. Hsu, M. Y. H. Low. 2011. Dynamic Yard Crane Dispatching in Container Terminals with Predicted Vehicle Arrival Information, Advanced Engineering Informatics, 25(3), 472--484.
4. Huang S. Y., X. Guo, W. J. Hsu and W. L. Lim. 2012. Yard Crane Dispatching to Minimize Job Tardiness in Container Terminals, The 2012 International Conference on Logistics and Maritime Systems.
5. Huang S. Y., X. Guo, W. J. Hsu and W. L. Lim. 2012. Embedding Simulation in Yard Crane Dispatching to Minimize Job Tardiness in Container Terminals, Proceedings of the 2012 Winter Simulation Conference.
6. Huang S. Y., Z. C. Tay and W. J. Hsu. A Framework for Automated Real Time Management of Container Handling Equipment. To be submitted to The 2013 International Conference on Logistics and Maritime Systems.
7. Jung, S. H., and K. H. Kim. 2006. Load scheduling for multiple quay cranes in port container terminals, Journal of Intelligent Manufacturing, 17, 479--492.
8. Kim, K. H., J. S. Kang, and K. R. Ryu. 2004. A beam search algorithm for the load sequencing of outbound containers in port container terminals, OR Spectrum, 26, 93--116.
9. Kim, K. M., and K. Y. Kim. 1999. An optimal routing algorithm for a transfer crane in port container terminals, Transportation Science, 33(1), 17--33.
10. Kim, K. Y., and K. H. Kim. 2003. Heuristic algorithms for routing yard-side equipment for minimizing loading times in container terminals, Naval Research Logistics, 50, 498--514.
11. Lee, L. H., E. P. Chew, K. C. Tan, and Y.B. Han. 2006. An optimization model for storage yard management in transshipment hubs, OR Spectrum, 28, 539--561.
12. Li, W., Y. Wu, M. Petering, M. Goh, and R. d. Souza. 2009. Discrete time model and algorithms for container yard crane scheduling, European Journal of Operational Research, 198, 165--172.
13. Narasimhan A. and U.S. Palekar. 2002. Analysis and Algorithm for the Transtainer Routing Problem in Container Port Operation, Transportation Science 36(1), 63--78.
14. Ng, W. C. and K. L. Mak. 2005. An effective heuristic for scheduling a yard crane to handle jobs with different ready times, Engineering Optimization, 37(8), 867--877.
15. Steenken, D., S. Vo², and R. Stahlbock. 2004. Container terminal operation and operations research -- a classification and literature review, OR Spectrum, 26, 3--49.
16. Zeng, Q. and Z. Yang. 2009. Integrating simulation and optimization to schedule loading operations in container terminals, Computers & Operations Research, 36(6), 1935--1944.

Index Terms

• Theory of computation

  • Design and analysis of algorithms

    • Approximation algorithms analysis

      • Scheduling algorithms

    • Online algorithms

      • Online learning algorithms

        • Scheduling algorithms

  • Theory and algorithms for application domains

    • Machine learning theory

      • Reinforcement learning

        • Sequential decision making