THIS PAPER CONSIDERS THE PROBLEM OF CONSISTENT ROUTING WITH MINIMUM SERVICE (CONVRPMS). CONVRPMS AIMS TO DETERMINE THE MINIMUM COST ROUTES FOR EACH DAY OF A PLANNING HORIZON. IN PARTICULAR, THE GOAL IS TO SATISFY ALL INDIVIDUAL DEMANDS AND SERVE EVERY CUSTOMER VIA A SINGLE DRIVER, WITH TIMES THAT DO NOT DIFFER BY MORE THAN ? TIME UNITS. THERE IS A FLEET OF HOMOGENEOUS VEHICLES THAT START FROM A SINGLE DEPOT. IN THIS PAPER, A HEURISTIC ALGORITHM FOR CONVRPMS IS PROPOSED. THE ALGORITHM IS BASED ON CLASSICAL CONSTRUCTIVE HEURISTICS AND THE TABU SEARCH METAHEURISTIC. THE PROPOSED ALGORITHM HAS BEEN TESTED ON BENCHMARK INSTANCES FROM THE LITERATURE. THE EXPERIMENTAL RESULTS SHOW THAT THE PROPOSED APPROACH PRODUCES HIGH-QUALITY SOLUTIONS WITHIN COMPUTING TIMES CONSIDERABLY LESS THAN THOSE OBSERVED WITH CPLEX. THE PROPOSED ALGORITHM CAN OPTIMALLY SOLVE INSTANCES WITH 20 CUSTOMERS AND A PLANNING HORIZON OF THREE DAYS, PRODUCING MORE ECONOMICAL SOLUTIONS IN SOME OF THE LARGER INSTANCES AND THOSE REQUIRING HOURLY CONSISTENCY (?=1 H).