Resumen: El problema del vendedor ambulante (TSP) es un problema de optimización combinatoria bien conocido con amplias aplicaciones del mundo real. Los avances recientes en los solucionadores de TSP basados en redes neuronales han mostrado resultados prometedores. No obstante, estos modelos a menudo luchan para resolver eficientemente los TSP de pequeña y gran escala utilizando el mismo conjunto de parámetros del modelo previamente capacitados, lo que limita su utilidad práctica. Para abordar este problema, presentamos un nuevo solucionador de TSP neural llamado Geld, basado en nuestra evaluación global amplia propuesta y un marco de selección local refinado. Específicamente, Geld integra un codificador liviano (GE) de visión global con un decodificador de visión local (LD) de peso pesado para enriquecer la representación de incrustación mientras acelera el proceso de toma de decisiones. Además, GE incorpora un nuevo mecanismo de atención de baja complejidad, lo que permite que Geld alcance la latencia de baja inferencia y la escalabilidad a los TSP a gran escala. Además, proponemos una estrategia de entrenamiento de dos etapas que utiliza casos de entrenamiento de diferentes tamaños para reforzar la capacidad de generalización de Geld. Experimentos extensos realizados en conjuntos de datos sintéticos y del mundo real demuestran que Geld supera a siete modelos de última generación considerando tanto la calidad de la solución como la velocidad de inferencia. Además, GELD se puede emplear como un método de postprocesamiento para elevar significativamente la calidad de las soluciones derivadas por los solucionadores neuronales de TSP existentes mediante el gasto de tiempo de computación adicional asequible. En particular, Geld se muestra como capaz de resolver TSP con hasta 744,710 nodos, el primero de su tipo para resolver este TSP de gran tamaño sin depender de estrategias divididas y conquistar a nuestro mejor conocimiento.
Publicado Originalme en rss.arxiv.org El 9 de junio de 2025.
Ver Fuente Original
