Resumen: Este estudio aborda el problema de vendedores de viajes múltiples Min-Max ($ M^3 $ -TSP), cuyo objetivo es coordinar las giras para múltiples vendedores de modo que se minimice la duración del recorrido más largo. Debido a su naturaleza difícil, los solucionadores exactos se vuelven poco prácticos bajo el supuesto de que $ p ne np $. Como resultado, los enfoques basados en el aprendizaje han ganado tracción por su capacidad para generar rápidamente soluciones aproximadas de alta calidad. Entre estos, los métodos de dos etapas combinan componentes basados en el aprendizaje con solucionadores clásicos, simplificando el objetivo de aprendizaje. Sin embargo, este desacoplamiento a menudo interrumpe la optimización consistente, potencialmente degradante la calidad de la solución. Para abordar este problema, proponemos un nuevo marco de dos etapas llamado textbf {generar y dividir} (gas), que integra el aprendizaje de refuerzo (RL) con un algoritmo de división óptimo en un proceso de capacitación conjunta. El algoritmo de división ofrece escalabilidad casi lineal con respecto al número de ciudades y garantiza una división óptima en el espacio euclidiano para cualquier ruta dada. Para facilitar la optimización conjunta del componente RL con el algoritmo, adoptamos una arquitectura de modelo mejorada con LSTM para abordar la observabilidad parcial. Extensos experimentos muestran que el marco de gas propuesto supera significativamente los enfoques existentes basados en el aprendizaje tanto en calidad de solución como en transferibilidad.
Publicado Originalme en export.arxiv.org El 25 de agosto de 2025.
Ver Fuente Original
