Este artículo trata sobre el Problema de Enrutamiento de Vehículos de Múltiples Depósitos Modificado (MDVRP). La modificación consiste en alterar el criterio de optimización. El criterio de optimización del MDVRP estándar es minimizar la suma total de rutas de todos los vehículos, mientras que el criterio del MDVRP modificado (M-MDVRP) es minimizar la ruta más larga de todos los vehículos, es decir, que el tiempo para realizar la operación de enrutamiento sea lo más corto posible. Para este problema, se ha modificado y adaptado un algoritmo metaheurístico basado en la teoría de Optimización de Colonias de Hormigas (ACO) y desarrollado por el autor para resolver instancias clásicas de MDVRP. En este artículo, se propone un proceso adicional de optimización determinística que mejora aún más el algoritmo ACO original. Para la evaluación de los resultados, se utilizan las instancias de prueba de Cordeau.