Este documento considera el problema de enrutamiento consistente con servicio mínimo (ConVRPms). ConVRPms tiene como objetivo determinar las rutas de costo mínimo para cada día de un horizonte de planificación. En particular, el objetivo es satisfacer todas las demandas individuales y atender a cada cliente a través de un solo conductor, con tiempos que no difieren en más de unidades de tiempo. Hay una flota de vehículos homogéneos que parten de un solo depósito. En este documento, se propone un algoritmo heurístico para ConVRPms. El algoritmo se basa en heurísticas constructivas clásicas y la metaheurística de búsqueda tabú. El algoritmo propuesto ha sido probado en instancias de referencia de la literatura. Los resultados experimentales muestran que el enfoque propuesto produce soluciones de alta calidad en tiempos de computación considerablemente menores que los observados con CPLEX. El algoritmo propuesto puede resolver de manera óptima instancias con 20 clientes y un horizonte de planificación de tres días, produciendo soluciones más económicas en algunas de las instancias más grandes y aquellas que requieren consistencia horaria.