Pre-processing a container yard under limited available time

To pick up a container from a container terminal, other containers may need to be relocated to other positions. In practice, these relocation moves are usually done when it is busy at a terminal. However, if the crane is idle for some amount of time, it may be more efficient to execute some pre-processing moves to reduce the number of future relocation moves. In this paper, we propose a model for optimal pre-processing moves if the available time is limited. We develop a heuristic to produce fast solutions for this new optimization problem. This heuristic consists out of multiple phases and for each phase, two different approaches are possible, and thus, the heuristic produces multiple solutions. Besides that, an optimal branch-and-bound algorithm is presented. Third, we propose another heuristic in which the remaining relocation moves are estimated in a sub-optimal way in the branch-and-bound method. This algorithm is not guaranteed to find the optimal solution, but its running time is faster than the optimal branch-and-bound method. Finally, we give an integer linear program that can be used to extend these solutions for a single bay of containers to a complete yard of containers.