The berth allocation problem: A strong formulation solved by a Lagrangean approach

The berth allocation problem is one of the most relevant logistics problems arising in the management of container ports. Depending on assumptions made on the berthing location policy, two classes of the berth allocation problem have been considered in literature: the discrete case and the continuous case. In this paper, the properties of the discrete berth allocation problem, formulated as a dynamic scheduling problem, are analyzed. A new formulation of the problem is proposed, which is shown to be more compact and stronger than another one from the literature; a Lagrangean heuristic algorithm is developed; and computational results are presented.