Extra re-handles may occur when lifting containers up for loading onto ships. One way to improve loading efficiency is to pre-marshal the containers in such an order that it fits the loading sequence. Therefore, a two-stage algorithm composed of a neighborhood search algorithm and an integer programming model is proposed to develop a pre-marshalling plan to improve the layout of containers in a bay. In the first stage, the final layout state space is compressed by using heuristic rules; in the second stage, the length of pre-marshalling sequence is shortened by integer programming. Two stages execute alternately to get optimal pre-marshalling sequence quickly. Several sets of experimental results demonstrate the effectiveness and practicability of the hybrid optimization algorithm.