Handling arrival time uncertainties in yard crane dispatching to minimize job tardiness in container terminals

• Main Author: Seah, Sheng Kiat
• Other Authors: Huang Shell Ying
• Format: Final Year Project
• Language: English
• Published: 2015
• Subjects: DRNTU::Engineering::Computer science and engineering::Mathematics of computing::Numerical analysis
• Online Access: http://hdl.handle.net/10356/62804
• Institution: Nanyang Technological University

It is important to optimize the performance of the yard crane to increase the productivity of the entire container terminal. The objective of yard crane dispatching is usually to minimize makespan of yard crane operations to improve yard crane performance or to minimize vehicle waiting time to improve the vehicle performance. Minimizing total weighted maximum tardiness has recently been proved to minimize total weighted vessel turnaround time. Total weighted vessel turnabout time is the most objective of container terminal operations. Algorithm MTWMT-RBA, finds a yard crane’s optimal job sequence using the estimated job arrival time. However, in real operations, actual arrival time may differ from the estimated arrival time for some jobs. This project proposes three algorithms to handle uncertainties in arrival times for planning yard crane jobs. 1. MTWMT-Replan is provable to find the optimal job sequence by using recursive backtracking with A* algorithm to replan the jobs that have not been started. However the algorithm suffers an exponentially long computation time when replanning a long job sequence. Computation time cannot take too long as replan has to be done in real time. 2. MTWMT-Localsearch moves the affected jobs forward or backward depending on the new arrival time of the affected job. The new sequence produced by the localsearch algorithm will try to find the best sequence to minimize the total weighted maximum tardiness. 3. Section replan determines an affected section in the job sequence, that is, the subset of jobs affected by the change of arrival time of the affected job. The affected section is replanned using MTWMT-RBA. The shorter sequence can be computed by MTWMT-RBA in a shorter computation time. Experiments to evaluate the proposed algorithms are controlled by two ways: percentage of the difference of actual job arrival time and affected job expected arrival time, and percentage of inter arrival time. The results of the experiments show that while MTWMT-RePlan will generate the optimal job sequence, runtime suffers when the job sequence to replan is long. Local search performs better when there is only one job affected. Section replan performs better when there is more than one job affected.