El presente articulo aborda la segunda fase del trabajo de investigacion sobre ruteo de vehiculos realizado en la empresa Cerromatoso S.A y presentado en esta revista en el Volumen 8 No. 21 del ano 2009 el cual llevaba por titulo: “Programacion matematica aplicada a sistemas de rutas de recoleccion de residuos”. En esta fase de la investigacion, se considera el problema original pero derogando las condiciones iniciales (convirtiendo el problema en un OVRP capacitado con grafo incompleto y asimetrico) y la utilizacion ademas de metodos heuristicos propios del ruteo de vehiculos, dentro de las que se mencionan algunas heuristicas constructivas y de insercion, y la aplicacion de la tecnica metaheuristica: Busqueda Tabu