In recent years, hybrid optimization approaches have been increasingly proposed to solve complex optimization problems across various domains, aiming to combine the advantages of each algorithm. In this paper, we introduce a hybrid metaheuristic to address an optimization problem related to the routing of straddle carriers (SCs) in port operations. The main objective is to ensure the efficient movement of containers between the quay and storage yard by SCs, thereby achieving short turnaround times for vessels while adhering to loading and unloading sequences at quay cranes (QCs). Besides the sequence enforced by precedence relations between containers, the problem also takes into account the limited buffer areas placed within the operational range of QCs. The problem is of particular importance, as the operational efficiency of SC-based terminals is significantly influenced by the routing of SCs. The hybridization includes the incorporation of Variable Neighborhood Descent (VND) into the Greedy Randomized Adaptive Search Procedure (GRASP). The numerical experiments demonstrate the superior performance of the proposed algorithm compared to the exact solver and the results obtained from employing GRASP by itself.