The Container Relocation Problem consists in finding the minimum number of moves to load a set of stacked container on a ship according to a given loading sequence. This is crucial problem for every commercial ports in the world. Minimizing the number of container relocation allows to minimize the operational costs (trucks cost and time). In this paper, we propose a Grasp algorithm to solve this problem. We have obtained new near-optimal solutions for this problem.Regular 2015FONDECYTFONDECYT