En un escenario donde la señal GNSS está bloqueada debido a interferencias u oclusiones, es de considerable valor establecer un sistema de navegación regional que proporcione servicios de emergencia para usuarios en tierra utilizando Vehículos Aéreos No Tripulados (VANT) de ala fija con larga duración y largo alcance. El trabajo principal de este artículo consta de dos partes. Primero, diseñamos un conjunto de arquitectura de sistema de navegación pseudolito basado en VANT (UAV-PNS) basado en VANT de ala fija. Luego, considerando el costo de vuelo del enjambre de VANT, se estudió la optimización de la trayectoria de vuelo del enjambre de VANT con el objetivo de mejorar el rendimiento de navegación regional. En este artículo, se proponen las funciones de aptitud para la optimización de la trayectoria de vuelo de los VANT, teniendo en cuenta el rendimiento de navegación y posicionamiento, la tasa de utilización de los VANT bajo restricciones de vuelo y la velocidad de respuesta del sistema a la misión de emergencia. Con base en esto, se propone un algoritmo genético de clasificación no dominada mutada de aceptación-rechazo III (ARMNSGA-III) para la optimización de la trayectoria de vuelo de los VANT. Los resultados de la investigación muestran que la trayectoria de vuelo garantiza fuertemente el rendimiento del servicio de navegación con restricciones sobre el costo operativo. El ARMNSGA-III propuesto en este artículo puede proporcionar una mejora del 44.01% en la puntualidad del algoritmo en comparación con el NSGA-III en la optimización de la trayectoria de vuelo, apoyando el establecimiento rápido y el servicio continuo del UAV-PNS en escenarios de emergencia.