One of the major issues of port terminal operators is to reduce inefficiencies in container handling and improve the terminal performance. In such a context, complex strategies and decisions are required to increase terminal efficiency in terms of both operation time and energy consumption. This paper focuses on the block relocation problem (BRP) and proposes an updated heuristic algorithm to introduce the possibility of relocation between bays. A simulation model has been implemented to validate the algorithm and to compare its performance with previous BRP methods. The outputs of the simulation show that the proposed algorithm improves energy efficiency and productivity by up to 8.7 and 10.2% respectively.