Transit facility allocation: Hybrid quantum-classical optimization

Resumen Técnico: Asignación de Instalaciones de Tránsito mediante Optimización Híbrida Cuántico-Clásica

Planteamiento del Problema
La planificación del tránsito urbano enfrenta un compromiso fundamental entre la accesibilidad del servicio (qué tan fácilmente los nodos de demanda, como las zonas urbanas, pueden alcanzar las instalaciones) y la eficiencia (la distancia que una ruta puede cubrir dentro de una ventana de tiempo específica). Aumentar el número de instalaciones generalmente mejora la accesibilidad pero reduce la eficiencia debido al incremento en los tiempos de parada y las distancias de viaje. Por el contrario, reducir las instalaciones mejora la eficiencia pero pone en riesgo la accesibilidad. El artículo aborda el Problema de Redundancia de Instalaciones de Tránsito: determinar la asignación óptima de un número limitado de instalaciones ($p$) a lo largo de una ruta para maximizar la accesibilidad y minimizar la redundancia sin comprometer la cobertura del servicio. El estudio se centra en la ruta de autobús B20 norte de Vancouver, Columbia Británica, utilizando datos de Sistemas de Información Geográfica (SIG).

Metodología
Los autores proponen un marco de optimización de extremo a extremo que integra datos de SIG, toma de decisiones multicriterio y computación híbrida cuántica-clásica.

1. Formulación Matemática:

   • El problema se modela mediante un novedoso enfoque de Cobertura de Interacción Espacial (SIC, por sus siglas en inglés), que captura interacciones no lineales entre las instalaciones y los nodos de demanda, el decaimiento por distancia y la competencia entre instalaciones.
   • El modelo se formula como un problema de Optimización Binaria Cuadrática Sin Restricciones (QUBO). La función objetivo maximiza una suma ponderada de la demanda de población atenuada por la distancia, penalizando la selección de instalaciones que estén demasiado cerca unas de otras (competencia).
   • Se incorpora una restricción que requiere que exactamente $p$ instalaciones estén activas como un término de penalización cuadrática. Para reducir la complejidad, los autores particionan esta restricción global en restricciones locales más pequeñas, transformando el grafo del problema de un grafo completo denso a una red dispersa.

2. Estimación de Pesos (TOPSIS):

   • Para determinar la importancia (pesos) de cada instalación, los autores emplean TOPSIS (Technique for Order Preference by Similarity to Ideal Solution), un método de toma de decisiones multicriterio.
   • Se evalúan tres atributos para cada instalación: demanda mensual, conectividad con otros servicios y proximidad a puntos de interés (ej. hospitales, escuelas). TOPSIS sintetiza estos elementos en una clasificación utilizada para ponderar las instalaciones en el modelo QUBO.

3. Solucionador Híbrido:

   • La optimización se resuelve utilizando un solucionador híbrido cuántico-clásico construido sobre el marco de código abierto dwave-hybrid.
   • El solucionador ejecuta tres ramas paralelas:
     • Heurísticas Clásicas: El Recocido Simulado (SA) y la Búsqueda Tabú (TS) realizan un ascenso de colinas (hill-climbing) sobre el problema completo.
     • Recocido Cuántico (QA): Opera sobre subproblemas más pequeños que contienen variables de "alto impacto energético", utilizando el túnel cuántico para escapar de los mínimos locales que atrapan a los métodos de ascenso de colinas clásicos.
   • El sistema combina iterativamente las mejores soluciones de todas las ramas.

4. Propiedades Teóricas:

   • Los autores demuestran que, bajo condiciones moderadas (específicamente cuando la relación de instalaciones retenidas respecto al total de instalaciones es $>0.5$ y la competencia es limitada), la matriz que gobierna el problema QUBO es definida positiva.
   • Esto implica que, incluso si se relajan las restricciones de integridad (permitiendo variables continuas $x_j \in [0, 1]$), la solución óptima converge naturalmente a valores binarios ($0$o$1$).
   • Se deriva un límite superior teórico para el valor objetivo óptimo utilizando el teorema de Schur-Horn, calculado como la suma de los $p$ autovalores más grandes de la matriz de interacción.

Contribuciones Clave

• Modelo Matemático Novedoso: Un modelo basado en QUBO que genera naturalmente soluciones integrales sin restricciones de enteros explícitas y captura factores no lineales complejos como el decaimiento por distancia y la competencia de las instalaciones.
• Formulación Lista para Computación Cuántica: El modelo está diseñado explícitamente para aprovechar los efectos cuánticos (superposición y túnel) mediante la equivalencia de vidrio de espín de Ising, lo que lo hace resoluble en recocedores cuánticos, recocedores digitales y computadoras cuánticas de puertas lógicas.
• Implementación de Solucionador Híbrido: Un robusto solucionador que combina el ascenso de colinas clásico con el túnel cuántico para navegar paisajes de optimización complejos.
• Límites Teóricos: La derivación de un límite superior ajustado y computable en tiempo polinómico para evaluar la calidad de la solución.
• Integración de SIG: Un flujo de trabajo flexible que integra datos censales y TOPSIS para la ponderación de datos de las instalaciones.

Resultados
El marco fue aplicado a la ruta de autobús B20 de Vancouver (49 paradas):

• Reducción de Instalaciones: El modelo logró reducir el número de paradas de autobús en un 40% (de 49 a aproximadamente 30) manteniendo la cobertura completa de todas las áreas de diseminación (nodos de demanda).
• Ganancias de Eficiencia: La reducción de paradas resultó en una reducción estimada de 7 minutos en el tiempo de viaje (aproximadamente el 13% del tiempo de viaje original) durante las horas de trabajo.
• Calidad de la Solución: Los mejores valores de la función objetivo encontrados estuvieron dentro del 95% del límite superior teórico (específicamente en $p=45$).
• Desempeño Comparativo: En experimentos con 30 conjuntos de datos sintéticos, el solucionador híbrico propuesto superó estadísticamente a un modelo SIC estándar resuelto con el solucionador clásico APOPT en términos de cobertura de demanda a través de varios niveles de retención de instalaciones.
• Análisis de Redundancia: El estudio identificó que hasta el 40% de las paradas eran redundantes (múltiples paradas a distancia de caminata de los mismos nodos de demanda) sin impactar significativamente la accesibilidad.

Significancia y Reivindicaciones
El artículo afirma que este marco ofrece un avance significativo en la planificación del tránsito al proporcionar un método rentable para mejorar la calidad del servicio mediante la consolidación estratégica de instalaciones. Su principal significancia radica en:

1. Puente entre la Computación Clásica y la Cuántica: Proporciona una aplicación práctica y del mundo real para el hardware cuántico emergente, demostrando cómo los planificadores de transporte pueden utilizar efectos cuánticos junto con herramientas clásicas.
2. Robustez del Modelo: La capacidad de generar soluciones naturalmente binarias y calcular límites superiores ajustados ofrece un nivel de garantía teórica y flexibilidad no presente en modelos tradicionales como LSCP o p-mediana.
3. Escalabilidad: El enfoque híbrido aborda las limitaciones del hardware cuántico actual (ruido y tasas de error) al utilizar solucionadores clásicos para la redundancia y la búsqueda global, mientras aprovecha el túnel cuántico para la optimización local.

Los autores concluyen que, si bien el enfoque tiene limitaciones respecto a las variables enteras no binarias y las restricciones de desigualdad, demuestra con éxito que la optimización de inspiración cuántica puede equilibrar eficazmente los objetivos contrapuestos de accesibilidad y eficiencia en redes de tránsito urbano complejas.