Los Vehículos Aéreos No Tripulados (VANT) están ganando impulso en muchos sectores civiles y militares. Un ejemplo se representa en el sector logístico, donde se ha demostrado que los VANT pueden mejorar la eficiencia del propio proceso, ya que su cooperación con camiones puede disminuir el tiempo de entrega y reducir el consumo de combustible. En este artículo, primero presentamos una formulación matemática del Problema del Viajante de Comercio (PVC) aplicado a la ruta logística, donde un camión coopera de manera sincrónica con múltiples VANT para la entrega de paquetes. Luego, proponemos, implementamos y comparamos diferentes enfoques de enrutamiento subóptimos para el mFSTSP formulado (Problema del Viajante de Comercio con Múltiples Compañeros Voladores), ya que la complejidad computacional combinatoria inherente al problema lo hace poco atractivo para los solucionadores comerciales de Programación Lineal Entera Mixta (PLEM). Se evalúan un algoritmo de búsqueda local, dos algoritmos genéticos híbridos que permutan soluciones factibles y no factibles, y un método codicioso alternativo ad-hoc en términos del tiempo total de entrega del cronograma de salida. Con el fin de la evaluación, se investigan los ahorros en términos de tiempo de entrega sobre la solución bien documentada del PVC solo para camiones para cada solución de enrutamiento propuesta, y esto se repite para dos escenarios diferentes. Las simulaciones de Monte Carlo corroboran los resultados.