Este documento presenta un nuevo algoritmo heurístico diseñado para resolver grandes instancias de una variante NP-difícil del problema de la ruta más corta, denominado problema de la ruta equilibrada en costos, propuesto recientemente en la literatura. El problema consiste en encontrar la ruta origen-destino en un grafo directo, con pesos negativos y positivos asociados a los arcos, de manera que la suma total de los pesos de los arcos seleccionados sea lo más cercana posible a cero. Hasta donde saben los autores, no existen algoritmos de solución para enfrentar este problema. El algoritmo propuesto integra un procedimiento constructivo y un procedimiento de mejora, y se valida gracias a la implementación de un procedimiento de búsqueda de vecindario iterado. La experimentación numérica reportada muestra que el algoritmo propuesto es computacionalmente muy eficiente. En particular, el algoritmo propuesto es más adecuado en el caso de grandes instancias donde es posible demostrar la existencia de una ruta perfectamente equilibrada y, por lo tanto, la optimalidad de la solución al encontrar un buen porcentaje de soluciones óptimas en un tiempo computacional despreciable.