EMU circulation planning for Silesian Railways: case study and a quantum approach

Este artículo presenta un estudio de caso sobre la planificación de la circulación diaria de unidades eléctricas múltiples (EMU) para los Ferrocarriles de Silesia, comparando una solución de programación lineal entera mixta clásica de alta calidad frente a enfoques cuánticos y de inspiración cuántica para demostrar las limitaciones actuales y el potencial de los métodos basados en QUBO para la optimización ferroviaria del mundo real.

Lo esencial

Imagina que eres el director de una enorme y concurrida orquesta, pero en lugar de violines y tambores, tus instrumentos son trenes eléctricos. Tu trabajo es asegurar que cada uno de los trenes tenga un conductor, suficientes asientos para los pasajeros y suficiente espacio para sus bicicletas, todo esto mientras te aseguras de que los trenes terminen de regreso en sus "garajes" (depósitos) listos para el día siguiente.

Este documento es un estudio de caso sobre la resolución de este rompecabezas para los Ferrocarriles de Silesia en Polonia. Los investigadores probaron dos formas diferentes de resolverlo: la forma clásica y confiable (Matemática Clásica) y la forma futurista y experimental (Computación Cuántica).

Aquí está el desglose de su viaje:

1. El Problema: El Rompecabezas de los Trenes

El operador ferroviario necesita planificar el horario diario de cientos de trenes. No es solo elegir un tren para una ruta; es un juego de Tetris complejo con reglas adicionales:

• Acoplamiento: A veces, dos trenes idénticos pueden engancharse (como vagones de tren) para formar un tren más grande para rutas concurridas.
• Bicicletas: Tienen que asegurarse de que haya suficiente espacio para las bicicletas de los pasajeros.
• Conductores: No pueden asignar más trenes de los conductores disponibles en un momento específico.
• Equilibrio de Garajes: Cada día, un cierto número de trenes debe comenzar y terminar en depósitos específicos.

2. La Solución "Vieja Escuela": El Maestro Chef (ILP)

Primero, el equipo construyó un Modelo Matemático Clásico (llamado Programación Lineal Entera o ILP).

• La Analogía: Piensa en esto como un chef súper inteligente y hiperorganizado que tiene un libro de recetas para cada forma posible de organizar los trenes. El chef verifica cada posibilidad contra las reglas (conductores, bicicletas, acoplamiento) para encontrar el horario perfecto y más económico.
• El Resultado: Este método funcionó impecablemente. Incluso con 404 viajes de tren y 11 tipos diferentes de trenes, la computadora resolvió todo el horario del día en menos de 40 minutos. Encontró el mejor plan posible cada vez.

3. La Solución "Futurista": El Lanzamiento de Dados Cuántico (QUBO)

Después, el equipo intentó traducir este problema a un formato que las Computadoras Cuánticas (específicamente las máquinas D-Wave) y el software "inspirado en la cuántica" pudieran entender. Convirtieron las reglas de los trenes en un problema QUBO (Optimización Binaria Cuadrática sin Restricciones).

• La Analogía: Imagina que en lugar de un chef revisando recetas una por una, tienes un lanzador de dados mágico que intenta encontrar la mejor disposición "sintiendo" la energía del sistema. Si la disposición es mala (por ejemplo, no hay suficiente espacio para bicicletas), se siente "caliente" (alta energía). Si es buena, se siente "fría" (baja energía). El objetivo es encontrar el estado más frío.
• El Problema: Para que la computadora cuántica entendiera las reglas, los investigadores tuvieron que añadir pesos de "penalización". Esto hizo que el problema explotara en tamaño.
  • La "Explosión": Mientras que el modelo clásico tenía un número manejable de variables, la versión cuántica tuvo que dar cuenta de millones de interacciones entre ellas. Era como intentar meter un océano entero en una taza de té.

4. El Enfrentamiento: ¿Quién Ganó?

Los investigadores probaron ambos métodos con datos reales del ferrocarril.

• El Chef Clásico (ILP): Ganó fácilmente. Manejó los horarios reales, grandes y desordenados rápidamente y encontró la respuesta perfecta.
• Los Dados Cuánticos (D-Wave): Solo pudo resolver las versiones diminutas del problema (como un ejemplo de juguete con solo 3 trenes). Cuando intentaron alimentarlo con un horario de tamaño medio, la "memoria" (qubits) de la computadora no era lo suficientemente grande para contener el rompecabezas. Era como intentar resolver un rompecabezas de 1,000 piezas con solo 10 piezas de rompecabezas.
• El Solucionador Inspirado en la Cuántica (VeloxQ): Esta es una computadora clásica fingiendo ser cuántica. Funcionó mejor que la computadora cuántica real y pudo resolver problemas ligeramente más grandes, pero aun así chocó contra un muro cuando el problema se volvió demasiado grande. No podía generar el "mapa" del problema lo suficientemente rápido.

5. La Conclusión Final

El documento concluye que para la planificación ferroviaria de hoy:

• Quédate con el Chef Clásico: El método matemático tradicional es rápido, confiable y está listo para el uso en el mundo real.
• Lo Cuántico es todavía un "Juguete": Las computadoras cuánticas actuales son demasiado pequeñas y las matemáticas necesarias para traducir el problema son demasiado pesadas. Solo pueden resolver versiones muy pequeñas y simplificadas del rompecabezas.

La Idea Futura:
Los autores sugieren un Enfoque Híbrido para el futuro. Imagina usar al Chef Clásico para planificar todo el día, pero luego usar los Dados Cuánticos para revisar rápidamente algunos puntos específicos y complicados (como una estación concurrida donde los trenes deben acoplarse y desacoplarse) para ver si hay una forma ligeramente mejor de organizar solo esos pocos trenes.

En resumen: Los investigadores demostaron que, aunque la computación cuántica es emocionante, para la planificación de horarios de trenes en este momento, la matemática de la supercomputadora de la vieja escuela sigue siendo la reina. El enfoque cuántico es un compañero prometedor, pero aún no está listo para tomar el liderazgo.

Resumen técnico

Resumen Técnico: Planificación de la Circulación de EMU para Silesian Railways

Definición del Problema

El artículo aborda el problema de la planificación diaria de la circulación de material rodante para unidades múltiples eléctricas (EMU) en la red de pasajeros regional de Silesian Railways (Koleje Śląskie) en Polonia. El objetivo es asignar las EMU disponibles a un horario fijo de viajes de tren cumpliendo con un complejo conjunto de restricciones operativas.

Las características clave del problema incluyen:

• Composiciones Flexibles: Las EMU del mismo tipo pueden acoplarse en parejas en un subconjunto predefinido de viajes para aumentar la capacidad, mientras que otros viajes deben ser servidos por unidades individuales.
• Capacidad Impulsada por la Demanda: El modelo incorpora explícitamente restricciones tanto para la capacidad de asientos de pasajeros como para la capacidad de almacenamiento de bicicletas, asegurando que los déficits no excedan los límites admisibles.
• Balance de Depósitos: El plan debe respetar los límites inferiores y superiores en el número de EMU de cada tipo que inician y terminan el día en depósitos específicos, manteniendo las reservas operativas.
• Disponibilidad de Tripulación: Las restricciones agregadas limitan el número de EMU operadas simultáneamente basándose en la disponibilidad de conductores adecuados en depósitos y momentos específicos.
• Horizonte Acíclico: El horizonte de planificación es un solo día, lo que resulta en una estructura de circulación acíclica, distinta de los modelos de planificación semanal cíclica.

Metodología

Los autores proponen un enfoque de metodología dual, comparando una formulación clásica de Programación Lineal Entera (ILP) contra una reformulación de Optimización Binaria No Restringida Cuadrática (QUBO).

1. Representación de Grafo/Hipergrafo

El problema se modela utilizando un grafo expandido en el tiempo donde:

• Los Nodos representan viajes de tren y eventos de servicio auxiliares de depósito.
• Las Aristas representan transiciones factibles de una sola EMU entre viajes.
• Las Hiper-aristas representan transiciones que involucran EMUs acopladas (acoplamiento, transferencia acoplada y desacoplamiento).
  Esta formulación de hipergrafo captura naturalmente la complejidad combinatoria de las composiciones de trenes flexibles.

2. Enfoque Clásico ILP

El problema se codifica como un Programa Lineal Entero Mixto (MILP) y se resuelve utilizando el solver SCIP.

• Objetivo: Minimiza una suma ponderada de costos operativos (fijos y dependientes de la distancia) y el número de EMUs despachadas (para preservar las flotas de reserva).
• Restricciones: Incluye cobertura (cada viaje servido exactamente una vez), balance de flujo (continuidad del material rodante), balance de depósito, límites de capacidad (asientos/bicicletas) y disponibilidad de tripulación.
• Escalabilidad: El número de variables binarias escala aproximadamente con $|T| \cdot |T|^2 \cdot |R|$ en el peor de los casos, donde $|T|$ es el número de viajes y $|R|$ es el número de tipos de EMU, aunque las restricciones prácticas reducen significamente este valor.

3. Enfoque Cuántico y Cuántico-Inspirado (QUBO)

El ILP se reformula en un problema QUBO para utilizar el recocido cuántico (quantum annealing) y heurísticas inspiradas en la física.

• Transformación: Las restricciones se convierten en términos de penalización añadidos a la función objetivo. Se introducen variables de holgura para manejar las restricciones de desigualdad (por ejemplo, límites de depósito, disponibilidad de tripulación).
• Solvers:
  • Recocido Cuántico (Quantum Annealing): Ejecutado en sistemas D-Wave Advantage (topologías Pegasus y Zephyr).
  • Cuántico-Inspirado: Ejecutado utilizando VeloxQ, un solver clásico basado en heurísticas inspiradas en la física (bifurcación simulada/minimización de energía) que no requiere hardware cuántico.
• Escalabilidad: La formulación QUBO introduce una sobrecarga significativa en el número de términos cuadráticos, escalando como $|T|^5$ en el peor de los casos, lo que crea un cuello de botella para la generación y el almacenamiento del modelo incluso antes de la resolución.

Contribuciones Clave

1. Modelo ILP Práctico: Desarrollo de un modelo ILP flexible y directamente resoluble que integra requisitos específicos del operador: acoplamiento por pares restringido a viajes predefinidos, capacidad explícita de bicicletas y límites agregados de tripulación.
2. Mapeo QUBO: Una reformulación específica del problema de circulación de material rodante en QUBO, incluyendo un análisis de la escalabilidad de variables y términos, resaltando el rápido crecimiento de las interacciones cuadráticas.
3. Benchmarking Empírico: Un estudio comparativo con datos reales de Silesian Railways (hasta 404 viajes y 11 tipos de EMU) evaluando:
   • ILP Clásico (SCIP).
   • Recocido Cuántico (Hardware D-Wave).
   • Heurísticas Cuántico-Inspiradas (VeloxQ).
4. Análisis de Factibilidad: Identificación de la frontera práctica actual para los métodos basados en QUBO en la planificación ferroviaria, específicamente respecto al compromiso entre la expresividad del modelo y la tractabilidad computacional.

Resultados Experimentales

Rendimiento del ILP Clásico

• Escalabilidad: El solver SCIP resolvió con éxito todas las instancias, incluyendo la más grande con ~404 viajes y ~380,000 variables binarias.
• Tiempo de Ejecución: Se obtuvieron soluciones óptimas o de alta calidad en segundos para instancias medianas y hasta aproximadamente 40 minutos para las instancias más grandes.
• Calidad: El modelo produjo planes de circulación factibles y prácticos que respetaban todas las restricciones, incluyendo escenarios complejos de acoplamiento y límites de capacidad.

Rendimiento Cuántico y Cuántico-Inspirado

• Limitaciones de Hardware: Los recocedores cuánticos D-Wave se vieron restringidos a las instancias más pequeñas (hasta ~50 viajes) debido a las limitaciones de embebido y al número de qubits disponibles. El sistema Advantage2 más reciente (topología Zephyr) resolvió sub-instancias ligeramente mayores que el sistema basado en Pegasus, pero no pudo manejar instancias más allá del tamaño 2a.
• Cuello de Botella en la Construcción de QUBO: La barrera principal no fue el tiempo de resolución, sino la generación de la matriz QUBO. Para instancias de tamaño medio (ej. 78 viajes), el número de términos cuadráticos alcanzó ~1.8 millones, y para instancias más grandes, superó los $10^8$, haciendo que la construcción del modelo fuera infactible dentro de la RAM disponible (62 GB).
• Comparación de Solvers:
  • VeloxQ: Superó a D-Wave en instancias pequeñas, encontrando soluciones óptimas rápidamente. Sin embargo, enfrentó la misma limitación respecto a la generación del modelo QUBO para instancias más grandes.
  • Factibilidad: Tanto los solvers cuánticos como los cuánticos-inspirados requirieron post-procesamiento para filtrar soluciones que violaban las restricciones blandas (variables de holgura), ya que el método de penalización no garantiza la factibilidad por construcción.

Significado y Reivindicaciones

El artículo sostiene que para el problema específico de la circulación diaria de EMU con las restricciones descritas:

• El ILP Clásico es actualmente superior: El enfoque clásico (SCIP) es el único método capaz de manejar la escala completa de instancias ferroviarias regionales reales (cientos de viajes) dentro de marcos de tiempo prácticos y garantizando la factibilidad.
• Estado Actual de los Métodos Cuánticos: Los enfoques basados en QUBO (tanto cuánticos como cuánticos-inspirados) están actualmente limitados a subproblemas pequeños o instancias altamente restringidas debido a la expansión cuadrática de términos y la sobrecarga de embebido. No superan aún a los solvers clásicos para la planificación diaria de extremo a extremo.
• Dirección Futura: Los resultados sugieren que una arquitectura híbrida clásico-cuántica es el camino más viable a corto plazo. En este marco, el solver clásico manejaría el problema global, mientras que los métodos basados en QUBO podrían aplicarse a subproblemas localizados de alta complejidad (por ejemplo, "puntos calientes" de acoplamiento específicos o ventanas de reprogramación de corto plazo) donde el tamaño del problema se reduce.
• Utilidad Práctica: El estudio demuestra que restringir la ventana de tiempo de transferencia ($\Delta$) sirve como una heurística efectiva para reducir la complejidad del modelo para los solvers clásicos sin degradar significativamente la calidad de la solución, una característica que también podría ayudar a esparcir las formulaciones QUBO.

Los autores concluyen que, si bien los métodos cuánticos muestran promesa para el muestreo de estados de baja energía y la provisión de soluciones factibles alternativas, su aplicación a la planificación de circulación de material rodante a gran escala sigue estando limitada por las limitaciones del hardware y la sobrecarga matemática de la reformulación QUBO.