En este documento se propone un nuevo modelo de grafo para resolver el Problema del Viajante Múltiple sin Colisiones (CFMTSP). En este problema, un grupo de vehículos parte de nodos diferentes en un grafo no dirigido y debe visitar cada nodo en el grafo, siguiendo el conocido problema del Viajante (TSP) sin ninguna colisión. El objetivo principal de este documento es obtener rutas libres de colisiones para cada vehículo, minimizando el tiempo de viaje del vehículo más lento. Este problema puede abordarse aplicando velocidad a cada vehículo, y un nuevo modelo de grafo aumentado puede llevarlo a cabo. Este enfoque no solo tiene en cuenta la posición de los nodos y las distancias entre nodos, sino que también propone la velocidad de todos los vehículos. El grafo aumentado propuesto debería poder utilizarse para obtener trayectorias óptimas, es decir, rutas y velocidades, para todos los vehículos. Se utiliza un algoritmo de optimización de colonia de hormigas (ACO) en el grafo aumentado propuesto. Las simulaciones muestran que el algoritmo puede cumplir con el objetivo principal. También se discuten factores considerados, como la limitación del éxito de la misión, es decir, el tiempo de llegada entre vehículos en un nodo, el número de vehículos y los números de vehículos y aristas del grafo.