Pre-Marshalling Problem: Heuristic solution method and instances generator

The Pre-Marshalling Problem consists in reshuffling containers in a port yard taking into account that a container with high priority cannot be placed below a container with low priority. The objective of the problem is to minimize the number of movements required to arrange all the containers so that further relocations are not necessary. In this work a heuristic solution method to solve the Pre-Marshalling Problem that significantly outperforms other methods from the literature is proposed. Moreover, an instances generator for this problem with which instances with varying degrees of difficulty can be created is developed. In order to obtain instances with degrees of difficulty that range from low difficulty up to high difficulty, two features that consider both the occupancy rate of the bay of containers and the percentage of containers with high priority that are located below containers with low priority are considered. The computational experiments carried out in this work corroborate the good performance of both the heuristic and the instances generator. (c) 2012 Elsevier Ltd. All rights reserved.