Integer programming models for the pre-marshalling problem

The performance of shipping companies greatly depends on reduced berthing times. The trend towards bigger ships and shorter berthing times places severe stress on container terminals, which cannot simply increase the available cranes indefinitely. Therefore, the focus is on optimizing existing resources. An effective way of speeding up the loading/unloading operations of ships at the container terminal is to use the idle time before the arrival of a ship for sorting the stored containers in advance. The pre-marshalling problem consists in rearranging the containers placed in a bay in the order in which they will be required later, looking for a sequence with the minimum number of moves. With sorted bays, loading/unloading operations are significantly faster, as there is no longer a need to make unproductive moves in the bays once ships are berthed. In this paper, we address the pre-marshalling problem by developing and testing integer linear programming models. Two alternative families of models are proposed, as well as an iterative solution procedure that does not depend on a difficult to obtain upper bound. An extensive computational analysis has been carried out over several well-known datasets from the literature. This analysis has allowed us to test the performance of the models, and to conclude that the performance of the best proposed model is superior to that of previously published alternatives.