Resumen: La planificación del itinerario a gran escala es una variante del problema del vendedor ambulante, con el objetivo de determinar una ruta óptima que maximice los puntajes de los puntos de interés recolectados (POI) al tiempo que minimiza el tiempo y el costo de viaje, sujeto a las limitaciones de duración del viaje. Este artículo analiza la descomposición de la planificación del itinerario a gran escala, lo que demuestra que la descomposición estricta es difícil de satisfacer e introduce una definición de descomposición débil basada en una condición necesaria, derivando las estructuras gráficas correspondientes que cumplen esta propiedad. Con la descomposición garantizada, proponemos un nuevo algoritmo cooperativo cooperativo de objetivos múltiples para la planificación del itinerario a gran escala, que aborda los desafíos del desequilibrio de los componentes y las interacciones. Específicamente, diseñamos una estrategia de descomposición dinámica basada en la aptitud normalizada dentro de cada componente, definimos el potencial de optimización considerando la escala y la contribución de los componentes, y desarrollamos una estrategia de asignación de recursos computacionales. Finalmente, evaluamos el algoritmo propuesto en un conjunto de conjuntos de datos del mundo real. Los experimentos comparativos con algoritmos de planificación de itinerario múltiple de última generación demuestran la superioridad de nuestro enfoque, con ventajas de rendimiento que aumentan a medida que crece la escala de problemas.
Publicado Originalme en rss.arxiv.org El 8 de junio de 2025.
Ver Fuente Original
