Quay crane scheduling with time windows, one-way, and spatial constraints

Quay cranes are the most important and expensive machines among the equipment in a maritime container terminal. They can be considered as an interface between land and sea operations in an intermodal transportation system. For this reason, the quay crane productivity, i.e. the number of operations performed in a given time lag, is the most meaningful indicator of the terminal performance. The ideal value of this indicator is around 30 movements per hour: terminals are considered to be efficient when, on average, quay cranes can handle 23]25 containers per hour. When the productivity is less than 23, the terminal becomes poorly competitive and this reflects on the logistic chain. In this paper we address the efficient management of quay cranes, aimed at determining a sequence of loading/unloading operations, that is a working schedule, for each crane assigned to a vessel, in order to minimize the vessel handling time. We assume to be given a set of cranes assigned to a containership and a stowage plan, showing both the containership layout (number of bays, decks, and holds) and the position of the containers to load/discharge within the containership. Cranes are railmounted and therefore they cannot cross each other. Moreover cranes are not allowed to span all over the vessel and can work only in predefined time windows. As regards containers, precedence relationships are defined on container groups. These precedence relationships results from the position and the operation type associated to the containers: unloading always precedes loading and the deck is unloaded before the hold. The hold is then loaded, and then the deck. Other precedence constraints can be imposed to take into account vessel load balance during the operations. In order to avoid clashes, a safety distance must be observed between adjacent cranes which translates into additional constraints on container handling (non simultaneity constraints). Finally we consider one]way constraints on the crane movements, either from the bow to the stern or vice]versa, since crane movements in opposite directions should be forbidden, although they could lead to better working schedule. The outline of the paper is as follows. In Section 1 we state the problem and provide a literature review. In Section 2 we give a mathematical model for the problem, while in Section 3 we present a solution methodology. Numerical experiments are discussed in Section 4. Finally, in Section 5 we draw some conclusions.