Iterated greedy for the yard crane scheduling problem with input/output assignment

The yard crane scheduling problem (YCSP) consists of optimizing container loading for storage and retrieval requests from yard cranes at port terminals. This paper studies a realistic generalization of the YCSP that incorporates the assignments of input/output (I/O) points during the optimization stage. I/O points serve as buffers between the different transportation modes in the port terminal. These are limited in number and unproductive idle times might result if a container schedule exhausts I/O point availability. The resulting problem entails not only scheduling container storage and retrieval requests, but also the assignment of the I/O points. We introduce a series of simple, yet powerful, Iterated Greedy (IG) methods. These include variations of the destruction and reconstruction operators, coordination with novel local search procedures and problem-specific knowledge speed-ups. The proposed IG methods are carefully calibrated and evaluated using comprehensive computational experiments. The results indicate that small changes in the features of the algorithm have a profound impact on performance. Comparisons against the state-of-the-art approaches for this particular problem result in a strong, and statistically significant performance advantage for the proposed IG procedures.