Los problemas logísticos representan una importante clase de problemas del mundo real donde incluso pequeñas mejoras en la calidad de la solución pueden llevar a disminuciones significativas en los costos operativos. Sin embargo, estos problemas suelen ser NP-duros; por lo tanto, se resuelven principalmente utilizando métodos metaheurísticos. Para mejorar su rendimiento, existe una investigación sustancial en la creación de metaheurísticas nuevas y refinadas para derivar soluciones superiores. Este documento considera un problema de enrutamiento de camiones dentro de un puerto naval, donde el objetivo es minimizar la distancia total recorrida por todos los vehículos para distribuir un conjunto dado de contenedores. Debido al gran volumen de mercancías que se transfieren a través de los puertos, es imperativo mejorar los tiempos de operación en dichos puertos para aumentar el rendimiento. Para lograr este objetivo, se propone y evalúa un nuevo método de búsqueda de vecindario variable que integra una lista tabú, un procedimiento de búsqueda local iterativo y la paralelización de la generación de vecindarios. Los resultados experimentales demuestran que el método propuesto logra resultados similares al estado del arte, pero en un menor tiempo.