Consideramos un problema de planificación de rutas en el que se requiere que dos vehículos no tripulados completen un conjunto de tareas presentes en ubicaciones distintas, denominadas objetivos, con un consumo mínimo de energía. El entorno de la misión es peligroso, y para garantizar una operación segura, se requiere que los vehículos no tripulados se comuniquen entre sí en cada objetivo que visitan. El objetivo del problema es determinar la asignación de las tareas a los vehículos no tripulados y planificar recorridos para que visiten los objetivos de manera que se minimice la suma ponderada de las distancias recorridas por los vehículos y las distancias recorridas por las señales de comunicación entre ellos. Formulamos este problema como un programa entero y mostramos que resolver el problema de manera ingenua utilizando solucionadores comerciales disponibles no es suficiente para determinar soluciones escalables de manera eficiente. Para abordar este desafío computacional, desarrollamos un algoritmo de aproximación y un algoritmo heurístico, y los empleamos para calcular soluciones de alta calidad para un caso especial del problema donde se asignan pesos iguales a las distancias recorridas por los vehículos y las señales de comunicación. Para este caso especial, mostramos que el algoritmo de aproximación tiene una relación de aproximación fija de 3.75. También desarrollamos límites inferiores al costo óptimo del problema para evaluar el rendimiento de estos algoritmos en instancias a gran escala. Demostramos el rendimiento de estos algoritmos en 500 instancias generadas aleatoriamente con un número de objetivos que varía de 6 a 100, y mostramos que los algoritmos proporcionan soluciones de alta calidad al problema rápidamente; el tiempo promedio de cálculo de las soluciones algorítmicas es de una fracción de segundo para instancias con un máximo de 100 objetivos. Finalmente, mostramos que la relación de aproximación tiene una relación variable para el caso ponderado del problema. Específicamente, si denota la relación de los pesos asignados a las distancias que representan los costos de comunicación y viaje, el algoritmo tiene una relación a posteriori de 3+34 cuando >=1, y 3+34 cuando.