A polyhedral study of the berth allocation problem with tides

Abstract

The berth allocation problem models the spatial and temporal allocation of ships into berth space in container terminals. In this work we are interested in the discrete version of this problem, in which the container terminal is viewed as a set of atomic berths. We are particularly interested in modeling the existence of tides, in such a way that ships can be moved in/out of the container terminal only in high-tide periods. We introduce a natural extension of the standard formulation for the discrete berth allocation problem that considers this feature, and we perform a polyhedral exploration of this formulation. We present valid inequalities involving the variables that model high-tide periods, we explore conditions ensuring that these inequalities induce facets of the associated polytopes, and we present computational experiments showing that the reinforcement of the formulation with some of these inequalities has a better performance with a general integer programming solver.