research-article

A two stage yard crane workload partitioning and job sequencing algorithm for container terminals

Authors:

Shell Ying HuangAuthors Info & Claims

SAC '10: Proceedings of the 2010 ACM Symposium on Applied Computing

Pages 2383 - 2388

https://doi.org/10.1145/1774088.1774583

Published: 22 March 2010 Publication History

Abstract

We propose a new YC workload partitioning scheme which employs dynamic data driven simulations to conduct what-if experiments in container terminals. Both the optimal partition of the workload in a row of yard blocks and the optimal dispatching sequences for individual YCs are achieved. The practical consideration of the safety constraints is included. A dynamic programming (DP) approach is used to avoid re-computation. An efficient two stage workload partition algorithm (TSWP) is proposed which successfully reduces the number of full what-if simulations while maintaining solution optimality. An effective lower bound (LB) generator with adjustable LB accuracy is designed in supporting the TSWP algorithm. Experimental results show that the TSWP algorithm outperforms the pure DP approach in all tested scenarios and takes less than 1 part per thousand computational time of the DP approach.

References

[1]

AXS-Alphaliner. Data on August, 2009.

[2]

Narasimhan, A., and Palekar, U. S. Analysis and algorithm for the transtainer routing problem in container port operation. Transportation Science 36 (1), 63--78. 2002.

Digital Library

[3]

Dechter R., Pearl J. Generalized best-first search strategies and the optimality of A*, JACM 32(3): 505--536. 1985.

Digital Library

[4]

Russell, S., and P. Norvig. Artificial Intelligence: A Modern Approach. 2nd Edition. Pearson Education, Inc., Upper Saddle River, NJ. 2003.

Digital Library

[5]

Guo, X., Huang, S. Y., Hsu, W. J., Low, M. Y. H. A simulation based hybrid algorithm for yard crane dispatching in container terminals. In Proceedings of the Winter Simulation Conference, Dec, 2009.

Digital Library

[6]

Kim, K. H., and Kim, K. Y. An optimal routing algorithm for a transfer crane in port container terminals. Transportation Science 33 (1):17--33. 1999.

Digital Library

[7]

Kim, K. Y., Kim, K. H. Heuristic algorithms for routing yard-side equipment for minimizing loading times in container terminals. Naval Research Logistics 50, 498--514. 2003.

[8]

Ng, W. C. Crane scheduling in container yards with intercrane interference. European Journal of Operational Research 164, 64--78. 2005.

[9]

Lee, D-H., Cao, Z., Meng, Q. Scheduling of two-transtainer systems for loading outbound containers in port container terminals with simulated annealing algorithm. International Journal of Production Economics 107:115--124. 2007.

[10]

Zhang, C., Wan Y-W., Liu J, Linn RJ. Dynamic crane deployment in container storage yard". Transportation Research Part B: Methodological 36(6):537--555. 2002.

[11]

Cheung, R. K., Li, C-L., Lin, W. Interblock crane deployment at container terminals. Transportation Science 36(1):79--93. 2002.

Digital Library

[12]

Narasimhan, A., Palekar, U. S. Analysis and algorithm for the transtainer routing problem in container port operation. Transportation Science 36 (1), 63--78. 2002.

Digital Library

[13]

Petering, M. E. H., Wu, Y., Li, W., Goh, M., Souza R. D. Development and simulation analysis of real-time yard crane control systems for seaport container transshipment terminals. OR Spectrum 31:801--835. 2009.

[14]

Guo, X., Huang, S. Y. Performing A* search for yard crane dispatching in container terminals. In Proceedings of the International Conference on Tools with Artificial Intelligence, Volume (1): 263--267.2

Digital Library

Cited By

Huang SGuo XLau M(2011)A three-level hierarchical workload management scheme for yard cranes in container terminalsProceedings of the Second international conference on Computational logistics10.5555/2045723.2045743(221-232)Online publication date: 19-Sep-2011
https://dl.acm.org/doi/10.5555/2045723.2045743
Huang SGuo X(2011)An improved Least Cost Heuristic for dynamic yard crane deployment in container terminals2011 IEEE International Conference on Automation Science and Engineering10.1109/CASE.2011.6042520(84-89)Online publication date: Aug-2011
https://doi.org/10.1109/CASE.2011.6042520
Huang SGuo XLau M(2011)A Three-Level Hierarchical Workload Management Scheme for Yard Cranes in Container TerminalsComputational Logistics10.1007/978-3-642-24264-9_17(221-232)Online publication date: 2011
https://doi.org/10.1007/978-3-642-24264-9_17

Index Terms

A two stage yard crane workload partitioning and job sequencing algorithm for container terminals
1. Computing methodologies
  1. Artificial intelligence
    1. Planning and scheduling
  2. Modeling and simulation
    1. Simulation support systems

Recommendations

Dynamic Space and Time Partitioning for Yard Crane Workload Management in Container Terminals

We propose a new hierarchical scheme for yard crane (YC) workload management in container terminals. We also propose a time partitioning algorithm and a space partitioning algorithm for deploying YCs to handle changing job arrival patterns in a row of ...
Dynamic yard crane dispatching in container terminals with predicted vehicle arrival information

The performance of a container terminal depends on many aspects of operations. This paper focuses on the optimal sequencing of a yard crane (or YC for short) for serving a fleet of vehicles for delivery and pickup jobs. The objective is to minimize the ...
Yard crane deployment in container terminals
WSC '14: Proceedings of the 2014 Winter Simulation Conference

A three-level, hierarchical system for yard crane (YC) management in container terminals and the algorithms for the bottom two levels were proposed in previous studies. The bottom two levels are responsible for YC job sequencing and intra-row YC ...

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences

SAC '10: Proceedings of the 2010 ACM Symposium on Applied Computing

March 2010

2712 pages

ISBN:9781605586397

DOI:10.1145/1774088

Conference Chairs:
Sung Y. Shin
South Dakota State University
,
Sascha Ossowski
University Rey Juan Carlos, Spain
,
Michael Schumacher
University of Applied Sciences Western Switzerland, Switzerland
,
Program Chairs:
Mathew J. Palakal
Indiana University Purdue University
,
Chih-Cheng Hung
Southern Polytechnic State University

Copyright © 2010 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGAPP: ACM Special Interest Group on Applied Computing

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 22 March 2010

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

SAC'10

Sponsor:

SIGAPP

SAC'10: The 2010 ACM Symposium on Applied Computing

March 22 - 26, 2010

Sierre, Switzerland

Acceptance Rates

SAC '10 Paper Acceptance Rate 364 of 1,353 submissions, 27%;

Overall Acceptance Rate 1,650 of 6,669 submissions, 25%

Upcoming Conference

SAC '25

Sponsor:
sigapp

The 40th ACM/SIGAPP Symposium on Applied Computing

March 31 - April 4, 2025

Catania , Italy

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

3
Total Citations
View Citations
118
Total Downloads

Downloads (Last 12 months)8
Downloads (Last 6 weeks)0

Reflects downloads up to 14 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Huang SGuo XLau M(2011)A three-level hierarchical workload management scheme for yard cranes in container terminalsProceedings of the Second international conference on Computational logistics10.5555/2045723.2045743(221-232)Online publication date: 19-Sep-2011
https://dl.acm.org/doi/10.5555/2045723.2045743
Huang SGuo X(2011)An improved Least Cost Heuristic for dynamic yard crane deployment in container terminals2011 IEEE International Conference on Automation Science and Engineering10.1109/CASE.2011.6042520(84-89)Online publication date: Aug-2011
https://doi.org/10.1109/CASE.2011.6042520
Huang SGuo XLau M(2011)A Three-Level Hierarchical Workload Management Scheme for Yard Cranes in Container TerminalsComputational Logistics10.1007/978-3-642-24264-9_17(221-232)Online publication date: 2011
https://doi.org/10.1007/978-3-642-24264-9_17

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents