Rolling Stock Planning Using the Quantum Approximate Optimization Algorithm

Este artículo presenta un marco híbrido de divide y vencerás que reformula la planificación de material rodante como un problema de Conjunto Independiente de Peso Máximo y evalúa el Algoritmo de Optimización Aproximada Cuántica (QAOA) tanto en simuladores clásicos como en el dispositivo cuántico IQM Emerald, demostrando que el aumento del tamaño de los subgrafos dentro de este enfoque cierra eficazmente la brecha entre los métodos de solución aproximados y exactos.

Lo esencial

Imagina que eres el conductor de una empresa ferroviaria masiva. Tienes un horario con 190 viajes de tren específicos que deben realizarse a lo largo de dos días. Tu trabajo es determinar qué tren físico realiza cada viaje.

Pero hay reglas:

1. Mantenimiento: Cada tren debe detenerse en una estación específica (como Hamburgo) para una revisión de 2 horas cada pocos miles de kilómetros.
2. Continuidad: Un tren no puede teletransportarse mágicamente; tiene que terminar un viaje y comenzar el siguiente desde la misma estación.
3. Costo: Si un tren tiene que moverse sin pasajeros (un "viaje vacío") para llegar a su siguiente trabajo, eso cuesta dinero (combustible, desgaste). Quieres minimizar estos kilómetros vacíos.

Este es el problema de la Planificación de Material Rodante. Es un rompecabezas gigante donde tienes que encajar todos los viajes en bucles (llamados "ciclos") que comiencen y terminen en el mismo lugar, respetando las reglas de mantenimiento y minimizando los costos.

El Problema: Demasiadas Posibilidades

El número de formas en que puedes organizar estos trenes es astronómicamente grande. Es como intentar resolver un Sudoku donde la cuadrícula tiene el tamaño de un campo de fútbol y las reglas cambian constantemente. Incluso las supercomputadoras más rápidas luchan por encontrar una disposición perfecta.

La Solución: Una Estrategia Híbrida de "Divide y Vencerás"

Los autores proponen un truco ingenioso. En lugar de intentar resolver todo el rompecabezas gigante a la vez, lo dividen en trozos más pequeños y manejables.

Piensa en organizar una biblioteca masiva. En lugar de intentar colocar cada libro del mundo a la vez, tú:

1. Eliges una pequeña sección de la biblioteca.
2. Ordenas esos libros perfectamente.
3. Los colocas en el estante.
4. Pasas a la siguiente sección.

A esto lo llaman un algoritmo de Divide y Vencerás. Toman el gran problema, extraen una pieza pequeña (un "subgrafo"), resuelven esa pieza y luego continúan.

El Arma Secreta: Computadoras Cuánticas

Aquí es donde entra la ciencia ficción. Para resolver esas pequeñas piezas, utilizan una mezcla de computadoras tradicionales y un nuevo tipo de computadora llamada Computadora Cuántica.

• La Computadora Clásica: Es como un bibliotecario muy rápido y lógico. Puede resolver acertijos pequeños rápidamente, pero se queda estancada ante los enormes.
• La Computadora Cuántica (QAOA): Piensa en esto como un bibliotecario "superintuitivo". No solo busca un camino a la vez; explora muchas posibilidades simultáneamente. Utiliza un método llamado Algoritmo de Optimización Aproximada Cuántica (QAOA).

Los investigadores probaron este bibliotecario cuántico en una máquina cuántica real (llamada IQM Emerald) y también lo simularon en una computadora clásica.

Cómo lo Probaron

Los investigadores compararon tres formas de resolver esas pequeñas piezas del rompecabezas:

1. El Enfoque Codicioso (Greedy): Un método simple y rápido que elige la opción que parece "mejor" en ese momento sin mirar hacia adelante. (Como elegir el libro más cercano sin comprobar si encaja en el género).
2. El Solucionador Exacto: Un método lento y perfecto que comprueba todas las posibilidades para encontrar la respuesta absolutamente mejor.
3. El Solucionador Cuántico (QAOA): El enfoque "intuitivo" que intenta encontrar una respuesta muy buena rápidamente.

Lo Que Encontraron

1. Trozos más grandes son mejores: Cuando hicieron que las "piezas pequeñas" del rompecabezas fueran más grandes, la solución general mejoró. Es como si organizaras un pasillo entero de libros a la vez en lugar de solo un estante; puedes ver el panorama general y tomar decisiones más inteligentes.
2. Lo Cuántico es prometedor: El solucionador cuántico (QAOA) funcionó casi tan bien como el "Solucionador Exacto" (que es lento y perfecto), pero mucho más rápido. Aunque la computadora cuántica era pequeña y aún no es perfecta, demostró que podía encontrar soluciones de alta calidad que estaban muy cerca de las mejores posibles.
3. El paso de "Poda" (Pruning): A veces, la computadora cuántica da una respuesta desordenada (como sugerir que dos trenes vayan al mismo lugar al mismo tiempo). Los autores utilizan una herramienta de "poda" para limpiar estos errores, eliminando los conflictos para que la solución sea válida.

La Conclusión

Este artículo no afirma que las computadoras cuánticas hayan resuelto ya los problemas ferroviarios del mundo. En cambio, muestra una hoja de ruta.

Demostraron que, al dividir un problema masivo e imposible en piezas más pequeñas y usar una computadora cuántica para resolver esas piezas, se pueden obtener muy buenos resultados. Es un puente entre los métodos lentos y perfectos del pasado y los métodos rápidos y poderosos del futuro.

En resumen: tomaron un horario ferroviario gigante y desordenado, lo trocearon, usaron una computadora cuántica para ordenar las piezas pequeñas y demostraron que este enfoque híbrido funciona mejor que simplemente adivinar o usar solo computadoras tradicionales.

Resumen técnico

Resumen Técnico: Planificación de Material Rodante mediante el Algoritmo de Optimización Aproximada Cuántica

Definición del Problema
El artículo aborda el problema de la Planificación de Material Rodante, un complejo desafío de optimización en la gestión ferroviaria. El objetivo es asignar trenes físicos a un horario de viajes programado, minimizando los costes operativos, definidos específicamente como "kilómetros vacíos" (distancia recorrida sin pasajeros). La instancia del problema considerada involucra 190 viajes durante dos días en cinco estaciones, sujetos a restricciones estrictas:

• Operación Cíclica: Cada tren debe completar un ciclo que regrese a su estación de origen.
• Mantenimiento: Cada ciclo debe incluir una parada de mantenimiento obligatoria en una estación designada durante una duración fija.
• Límites de Distancia: Los ciclos no pueden exceder una distancia máxima ($l_{max}$) antes de que se requiera mantenimiento.
• Viajes Vacíos: Los trenes pueden realizar "viajes vacíos" (movimientos no programados) para conectar viajes programados o alcanzar estaciones de mantenimiento, lo que incurre en costes pero garantiza la viabilidad.

Los autores señalan que, si bien el problema está restringido, no modelan las restricciones de capacidad de la red (por ejemplo, límites de estacionamiento en estaciones o congestión de rutas), asumiendo una capacidad ilimitada para el alcance de este estudio.

Metodología
Los autores proponen un algoritmo híbrido cuántico-clásico de divide y vencerás para abordar la complejidad computacional del problema, la cual escala exponencialmente con el número de viajes.

1. Mapeo al Conjunto Independiente de Peso Máximo (MWIS):
   El problema se reformula primero como un problema de MWIS en un grafo.

   • Nodos: Representan ciclos de tren factibles generados a partir del horario.
   • Aristas: Conectan nodos si los ciclos correspondientes son mutuamente incompatibles (es decir, ambos prestan servicio al mismo viaje programado).
   • Pesos: Se asignan a los nodos basándose en una función objetivo heurística ($w_i = 2d_{full} - d_{empty}$), priorizando la cobertura de los viajes de pasajeros sobre la pura reducción de costes.
   • Objetivo: Encontrar un conjunto independiente (un conjunto de ciclos no conflictivos) con el peso total máximo.

2. Estrategia de Generación de Ciclos:
   Para gestionar la explosión de posibles ciclos, los autores emplean un proceso de generación de dos modos:

   • Modo 1: Genera ciclos utilizando únicamente viajes programados (sin viajes vacíos).
   • Modo 2: Se activa cuando el número de viajes no servidos cae por debajo de un umbral (40 viajes) o cuando no se pueden formar más ciclos del Modo 1. Este modo permite viajes vacíos, expandiendo significativamente el espacio de soluciones para asegurar que todos los viajes restantes puedan ser cubiertos.

3. Marco Híbrido de Divide y Vencerás:
   Dado que el grafo MWIS completo es demasiado grande para los resolvedores actuales, el algoritmo resuelve iterativamente subgrafos más pequeños:

   • Selección de Subgrafo: Una heurística selecciona un subgrafo de tamaño $k$ (por ejemplo, de 20 a 300 nodos). La estrategia de selección prioriza los ciclos que prestan servicio al mayor número de viajes completos, equilibrando la calidad de la solución con la diversidad.
   • Resolución del Subgrafo: El problema MWIS en el subgrafo seleccionado se resuelve mediante varios métodos:
     • Resolvedor Exacto Clásico: Utilizado como línea de base.
     • Algoritmo Greedy (Voraz): Una línea de base clásica que selecciona nodos basados en la relación peso-grado.
     • QAOA (Algoritmo de Optimización Aproximada Cuántica): Implementado con profundidad $p=1$ y $p=5$. El problema se mapea a un Hamiltoniano de vidrio de espín diagonal con un término de penalización para las violaciones de aristas.
     • Muestreo Aleatorio: Utilizado como un punto de referencia de límite inferior.
   • Poda: Dado que QAOA y el muestreo aleatorio pueden producir conjuntos inválidos (que contienen nodos conectados), un procedimiento de poda elimina los nodos con las relaciones peso-grado más bajas hasta que se forma un conjunto independiente válido.
   • Actualización Global: Los ciclos seleccionados se añaden a la solución global y los nodos conflictivos se eliminan del grafo global. El proceso se repite hasta que todos los viajes sean servidos.

Resultos Clave
Los autores evaluaron el algoritmo utilizando simulación clásica y ejecución en el dispositivo cuántico IQM Emerald.

• Comparación de Resolvedores (Tamaño de Subgrafo Fijo): Con un tamaño de subgrafo pequeño ($k=20$), la diferencia de rendimiento entre el algoritmo greedy, los resolvedores clásicos exactos y QAOA ($p=1, p=5$) fue insignificante. Sin embargo, los resultados mostraron que un QAOA de mayor profundidad ($p=5$) tendía a acercarse a la calidad de la solución del resolvedor exacto, a pesar de ser un algoritmo de tiempo polinómico en comparación con el de tiempo exponencial del resolvedor exacto.
• Impacto del Tamaño del Subgrafo: Un hallazgo crítico fue la correlación positiva entre el tamaño del subgrafo y la calidad de la solución. A medida que el tamaño del subgrafo aumentaba (hasta 300 nodos), el número de kilómetros vacíos disminuía significativamente (pendiente negativa con $p \approx 10^{-9}$). Esto sugiere que resolver subproblemas más grandes produce mejores soluciones globales, incluso si el resolvedor del subgrafo es aproximado.
• Ejecución Cuántica: El artículo reporta resultados de la ejecución de QAOA $p=1$ en la computadora cuántica IQM Emerald, demostrando la viabilidad de ejecutar el algoritmo en hardware actual, aunque la calidad de la solución fue comparable a la simulación clásica y al muestreo aleatorio para los parámetros probados.

Significancia y Reivindicaciones
El artículo posiciona su trabajo como una vía práctica para aplicar computadoras cuánticas de corto plazo a problemas de optimización industriales realistas antes de que el hardware sea capaz de resolver el problema completo directamente.

• Cerrar la Brecha: El marco híbrido cierra eficazmente la brecha entre los resolvedores de tiempo polinómico rápidos y aproximados (como los algoritmos greedy) y los métodos exactos lentos de tiempo exponencial.
• Escalabilidad: Los autores argumentan que su enfoque permite que los algoritmos cuánticos se apliquen a subproblemas compatibles con las limitaciones del hardware actual, mientras que un bucle externo clásico orquesta la optimización general.
• Potencial de Ventaja Cuántica: Los resultados sugieren un escenario donde la profundidad del algoritmo QAOA ($p$) solo necesita crecer polinómicamente con el tamaño del subgrafo para lograr soluciones aproximadamente óptimas, ofreciendo una potencial ventaja cuántica sobre los métodos clásicos exactos para instancias a gran escala.
• Modestia: Los autores reconocen las limitaciones, señalando que el paso de generación de ciclos actual es un cuello de botella para horarios más grandes y que la efectividad del procedimiento de poda puede degradarse a medida que aumentan los tamaños de los subgrafos. No afirman que QAOA supere actualmente a los resolvedores clásicos exactos en el problema completo, sino que la arquitectura híbrida permite la exploración de espacios de soluciones más amplios de lo que era posible anteriormente solo con recursos cuánticos.