Resolución del problema de múltiples viajeros con caminos cerrados y varios depósitos usando k-means++ de agrupamiento jerárquico y redes neuronales combinatorias

Rutas más inteligentes para muchos conductores

Desde furgonetas de paquetería hasta drones de reparto y convoyes de ayuda en desastres, los planificadores se enfrentan con frecuencia a un rompecabezas: ¿cómo pueden varios vehículos que parten de ubicaciones diferentes repartir el trabajo de visitar cientos o miles de paradas sin malgastar combustible ni tiempo? Este artículo presenta una forma nueva de dividir y conquistar ese acertijo, combinando un truco clásico de agrupamiento con una red neuronal moderna para que los ordenadores puedan diseñar rutas eficientes en segundos en lugar de minutos u horas.

El desafío de muchos depósitos y muchos conductores

El estudio aborda una versión exigente del famoso problema del viajante, donde en lugar de un viajante hay muchos, cada uno comenzando y terminando en su propia base. Juntos deben visitar cada ciudad exactamente una vez manteniendo la distancia total lo más corta posible. Esta configuración reproduce tareas como coordinar flotas de camiones, grupos de robots o drones aéreos que comparten el trabajo en una región. Debido a que el número de combinaciones posibles de rutas se dispara a medida que crecen las ciudades y los conductores, los métodos exactos se vuelven demasiado lentos, y los métodos tradicionales de búsqueda por prueba y error a menudo tienen dificultades o deben sacrificar la calidad de la solución por velocidad.

Límites de la búsqueda clásica y de la división simple

Durante años, los ingenieros han recurrido a “metaheurísticas” como algoritmos genéticos, búsqueda por colonia de hormigas y enjambres de partículas. Estas imitan procesos naturales para explorar muchos candidatos de rutas y mejorarlas gradualmente. Pueden ser flexibles pero tienen dos grandes inconvenientes: no ofrecen garantías firmes sobre la calidad de una solución y pueden ser muy lentas para mapas grandes, especialmente cuando cada nueva tarea requiere reiniciar la búsqueda. Una aceleración popular es agrupar primero las ciudades en regiones usando herramientas como k-means y luego resolver un rompecabezas más pequeño dentro de cada grupo. Aunque esta estrategia de dividir y luego resolver ayuda, la calidad final sigue limitada por el método de búsqueda subyacente, y buscar mejores rutas suele implicar tiempos de ejecución aún mayores.

Enseñar a una red a enrutar y luego ayudarla a escalar

En años recientes ha surgido una idea diferente: entrenar una red neuronal para que genere buenas rutas directamente. Tras aprender con muchos ejemplos de distribuciones de ciudades, esa red puede proponer un recorrido completo en una sola pasada hacia adelante, de forma similar a como un modelo de lenguaje escribe una frase. Estos solucionadores neuronales funcionan de manera impresionante en problemas de un solo conductor y de tamaño moderado, pero flaquean cuando se les pide coordinar muchos conductores o cuando el conjunto de ciudades es mucho mayor que los casos vistos en entrenamiento. La jugada clave de los autores es envolver ese solucionador neuronal dentro de un proceso cuidadoso de dos pasos que reconfigura una tarea enorme y multi-conductor en muchos subproblemas más pequeños y familiares que la red puede manejar con comodidad.

Cómo funciona el método en dos fases

El método propuesto, llamado KHC-NCN, comienza utilizando una versión mejorada de k-means para asignar ciudades a diferentes depósitos y conductores. Si una región resultante contiene demasiadas ciudades para que el solucionador neuronal la gestione con fiabilidad, el método divide automáticamente esa región en piezas más pequeñas, cada una de un tamaño cercano al que la red vio durante el entrenamiento. Las coordenadas de cada pieza se reescalan a un cuadrado estándar para que se parezcan aún más a los datos de entrenamiento. La red neuronal produce entonces una ruta para cada pequeña pieza. Finalmente, un paso de fusión cose estas subrutas en un único bucle para cada conductor, usando reglas geométricas simples para conectar piezas donde hacerlo añade la menor distancia extra.

Velocidad y calidad en mapas de referencia reales

Los autores prueban su método en una amplia colección de mapas estándar de un conjunto de referencia público ampliamente usado en investigación de enrutamiento. Comparan con muchas técnicas de búsqueda establecidas y con un solucionador de alta calidad elaborado a mano y con otro enfoque neuronal. En 44 casos de prueba con distintos tamaños de mapa y número de conductores, su método encuentra recorridos totales más cortos en casi tres cuartas partes de los casos, además de ser dramáticamente más rápido, a menudo por órdenes de magnitud. Se mantiene especialmente bien cuando el número de ciudades sube a cientos o miles, donde muchos enfoques clásicos se ralentizan o entregan rutas de menor calidad.

Qué significa esto para el enrutamiento en el mundo real

En términos sencillos, el estudio muestra que dejar que una red neuronal rápida gestione muchos rompecabezas pequeños y bien formados puede vencer a dedicar mucho tiempo a un único rompecabezas enorme. Agrupando las ciudades de una manera que respete la zona de confort de la red, y luego combinando inteligentemente las respuestas parciales, el método ofrece rutas que son tanto cortas como rápidas de calcular. Para aplicaciones como logística, planificación multi-robot y respuesta a emergencias, esto apunta a una forma práctica de obtener planes de ruta casi en tiempo real que aprovechan mejor los vehículos y la energía que muchas herramientas existentes.

Cita: Zhao, CS., Wong, LP. & Fung, C. Solving multi-depot closed-path multiple traveling salesman problem using k-means++ hierarchical clustering and neural combinatorial networks. Sci Rep 16, 15631 (2026). https://doi.org/10.1038/s41598-026-45824-3

Palabras clave: enrutamiento de vehículos, redes neuronales, agrupamiento, optimización, logística