Due to real-life logistics necessities, the vehicle routing problem with time windows (VRPTW) has received substantial attention. In its deterministic version, all the input data are static and previously known. Nevertheless, the travel time may be uncertain in practice. This work focuses on a robust optimization to handle the uncertainty in travel times. We approach the problem using the iterated local search metaheuristic combined with a new evaluation algorithm to enhance the local search phase. Specifically, we introduce a polynomial-time algorithm that allows penalization for infeasible solutions for the robust VRPTW leading the local search to explore the search space wider than other algorithms.