Yard Crane Scheduling for container storage, retrieval, and relocation

This paper introduces a novel optimization problem resulting from the combination of two major existing problems arising at storage yards in container terminals. The Yard Crane Scheduling Problem is typically concerned with routing the crane given a sequence of storage and retrieval requests to perform, while the Container Relocation Problem tackles the minimization of relocations when retrieving containers in a simpler setting. This paper is the first to consider a model that integrates these two problems by scheduling storage, retrieval and relocations requests and deciding on storage and relocation positions. We formulate this problem as an integer program that jointly optimizes current crane travel time and future relocations. Based on the structure of the proposed formulation and the linear programming relaxation of subproblems, we propose a heuristic local search scheme. Finally, we show the value of our solutions on both simulated instances as well as real data from a port terminal. (C) 2018 Elsevier B.V. All rights reserved.