El Problema del Viajante Múltiple es una extensión del famoso Problema del Viajante. Encontrar una solución óptima al Problema del Viajante Múltiple (mTSP) es una tarea difícil ya que pertenece a la clase de problemas NP-difíciles. El problema se vuelve más complicado cuando la matriz de costos no es simétrica. En tales casos, encontrar incluso una solución factible al problema se convierte en una tarea desafiante. En este documento, se presenta un algoritmo que utiliza Redes de Petri de Colores (CPN) -un lenguaje de modelado matemático- para representar el Problema del Viajante Múltiple. El algoritmo propuesto mapea cualquier mTSP dado en un CPN. El modelo transformado en CPN garantiza una solución factible al mTSP con matriz de costos asimétrica. El modelo se simula en CPNTools para medir dos objetivos de optimización: el tiempo máximo que un vendedor tarda en una solución factible y el tiempo colectivo tomado por todos los vendedores. El modelo transformado también se verifica formalmente a través de análisis de alcanzabilidad para asegurar que es correcto y terminante.