Análisis comparativo de cruces en algoritmos genéticos para la optimización de rutas: estudios de caso en Astana y Shymkent, Kazajistán

Por qué importan rutas de autobús más inteligentes

Cualquiera que haya esperado demasiado en una parada de autobús o haya tenido que hacer varios transbordos sabe que atravesar una ciudad no es solo una cuestión de distancia. Dos lugares pueden parecer cercanos en un mapa y, sin embargo, ser difíciles de alcanzar si no existen las líneas de autobús adecuadas que los conecten. Este artículo examina cómo una clase de métodos de búsqueda inspirados en la evolución —los algoritmos genéticos— puede ajustarse para diseñar rutas de autobús mejores que respeten las redes reales de transporte en ciudades como Astana y Shymkent, en Kazajistán. El trabajo se centra en un ingrediente crucial de estos algoritmos, llamado paso de cruce (crossover), y muestra cómo elegirlo con criterio puede marcar la diferencia entre viajes torpes y circulares y rutas rápidas y realistas.

De mapas urbanos desordenados a búsquedas inteligentes

Los planificadores de rutas tradicionales a menudo tratan las ciudades como si los viajeros pudieran desplazarse libremente entre dos puntos, preocupándose solo por la distancia física. Los sistemas reales de autobuses no funcionan así: solo se puede ir donde realmente circulan las líneas, y cada enlace ausente o desvío forzado cuesta tiempo y dinero. Los autores modelan esta realidad representando ubicaciones importantes de la ciudad como puntos, las vías y enlaces de autobús como conexiones, y un viaje completo como un camino que visita cada punto exactamente una vez. Luego fijan un objetivo en dos partes: primero, evitar pasos “ilegales” donde no existe un autobús directo; segundo, entre las rutas legales, elegir la de menor distancia total. Esto crea un rompecabezas difícil con muchas rutas posibles, en el que comprobar cada opción se vuelve pronto imposible a medida que la ciudad crece.

Cómo la evolución ayuda a encontrar mejores rutas

Los algoritmos genéticos atacan este tipo de rompecabezas imitando la selección natural. En lugar de probar una ruta a la vez, mantienen toda una población de rutas candidatas. En cada generación, las rutas mejores son favorecidas y se crean nuevas combinando y modificando ligeramente las existentes. El paso clave de mezcla —el crossover— decide cómo se combinan piezas de dos rutas progenitoras para formar una nueva ruta hija. Para la planificación de autobuses, este paso es crítico: si se hace bien, transmite patrones útiles de paradas conectadas; si se hace mal, puede romper enlaces y producir rutas que ignoren la red de autobuses. Los autores prueban nueve estilos diferentes de crossover que varían en cómo preservan el orden de las paradas, las posiciones exactas de las paradas o los enlaces reales entre ellas.

Probando muchas maneras de mezclar rutas

Para ver qué estilos de crossover funcionan mejor, el equipo realiza una amplia batería de experimentos con datos reales de transporte de Konya (una ciudad de referencia de trabajos previos) y de Astana y Shymkent. Para cada ciudad seleccionan 14 destinos importantes, los vinculan a paradas cercanas y construyen tres tablas de datos clave: distancias entre ubicaciones, qué pares tienen un autobús directo y penalizaciones por intentar viajar donde no hay servicio. Luego exploran cientos de configuraciones, variando el tamaño de la población, la frecuencia de uso del crossover y la frecuencia de pequeños cambios aleatorios (mutaciones). Para cada configuración repiten el algoritmo muchas veces para tener en cuenta la variabilidad y miden no solo lo cortas que son las rutas finales, sino con qué frecuencia el método encuentra alguna ruta legal y cuán rápido alcanza ese punto.

La estrategia ganadora para viajes realistas

En las tres ciudades destaca un estilo de crossover: la recombinación por aristas (edge recombination). A diferencia de métodos que se centran principalmente en el orden de las paradas, la recombinación por aristas presta atención a qué paradas están directamente vinculadas y esfuerza por preservar esos enlaces al construir nuevas rutas. El estudio muestra que este enfoque centrado en las aristas tiene mucha más probabilidad de producir viajes de autobús factibles, redescubre con mayor frecuencia las rutas conocidas como óptimas y suele hacerlo en solo unas pocas generaciones. Un segundo estilo, llamado crossover basado en el orden, también rinde bien y es más rápido de calcular, ofreciendo un buen equilibrio cuando se necesitan un gran número de ejecuciones. Otros crossovers comunes que reordenan las paradas de forma más agresiva tienden a tener más dificultades, requieren más tiempo y entregan menos rutas de alta calidad.

Qué significa esto para el viaje diario

Para un público no especialista, la conclusión es que la “receta” usada dentro de un algoritmo genético puede tener un gran impacto en lo bien que diseña viajes de autobús reales. Al favorecer reglas de crossover que mantienen los enlaces realistas intactos mientras siguen explorando nuevas combinaciones, los planificadores pueden generar rutas que respetan la red de autobuses existente y a la vez reducen la distancia total de viaje. En pruebas sobre instantáneas urbanas pequeñas pero realistas, el algoritmo genético mejor ajustado no solo igualó rutas encontradas por métodos matemáticos exactos, sino que lo hizo con rapidez y fiabilidad. Esto sugiere que, a medida que las ciudades se vuelven más complejas y ricas en datos, una búsqueda evolutiva bien diseñada puede ayudar a las agencias de transporte a planificar rutas que se perciban como más directas, requieran menos transbordos incómodos y aprovechen mejor vehículos y combustible.

Cita: Kazbek, R., Sergaziyev, M., Kenzhe, D. et al. A comparative analysis of crossovers in genetic algorithms for route optimization: case studies from Astana and Shymkent, Kazakhstan. Sci Rep 16, 13816 (2026). https://doi.org/10.1038/s41598-026-43898-7

Palabras clave: enrutamiento del transporte público, algoritmos genéticos, movilidad urbana, optimización de rutas, planificación de ciudades inteligentes