Transit facility allocation: Hybrid quantum-classical optimization

Resumo Técnico: Alocação de Instalações de Trânsito via Otimização Híbrida Quântico-Clássica

Definição do Problema
O planejamento do trânsito urbano enfrenta um compromisso fundamental entre acessibilidade de serviço (o quão facilmente os nós de demanda, como áreas urbanas, podem alcançar as instalações) e eficiência (a distância que uma rota pode cobrir dentro de uma janela de tempo específica). Aumentar o número de instalações geralmente melhora a acessibilidade, mas reduz a eficiência devido ao aumento dos tempos de parada e das distâncias de viagem. Inversamente, reduzir as instalações melhora a eficiência, mas coloca em risco a acessibilidade. O artigo aborda o Problema da Redundância de Instalações de Trânsito: determinar a alocação ideal de um número limitado de instalações ($p$) ao longo de uma rota para maximizar a acessibilidade e minimizar a redundância sem comprometer a cobertura do serviço. O estudo foca na rota de ônibus B20 norte de Vancouver, Colúmbia Britânica, utilizando dados de Sistemas de Informação Geográfica (SIG/GIS).

Metodologia
Os autores propõem uma estrutura de otimização de ponta a ponta que integra dados de SIG, tomada de decisão multicritério e computação híbrida quântico-clássica.

1. Formulação Matemática:

   • O problema é modelado usando uma abordagem inovadora de Interação Espacial de Cobertura (SIC), capturando interações não lineares entre instalações e nós de demanda, decaimento por distância e competição entre instalações.
   • O modelo é formulado como um problema de Otimização Binária Quadrática Não Restrita (QUBO). A função objetivo maximiza uma soma ponderada da demanda populacional atenuada pela distância, enquanto penaliza a seleção de instalações que estejam muito próximas umas das outras (competição).
   • Uma restrição que exige exatamente $p$ instalações ativas é incorporada como um termo de penalidade quadrática. Para reduzir a complexidade, os autores particionam essa restrição global em restrições locais menores, transformando o grafo do problema de um grafo completo denso para uma rede esparsa.

2. Estimativa de Pesos (TOPSIS):

   • Para determinar a importância (pesos) de cada instalação, os autores empregam o TOPSIS (Technique for Order Preference by Similarity to Ideal Solution), um método de tomada de decisão multicritério.
   • Três atributos são avaliados para cada instalação: demanda mensal, conectividade com outros serviços e proximidade de pontos de referência (ex: hospitais, escolas). O TOPSIS sintetiza esses dados em um ranking usado para ponderar as instalações no modelo QUBO.

3. Solucionador Híbrido:

   • A otimização é resolvida usando um solucionador híbrido quântico-clássico construído sobre o framework de código aberto dwave-hybrid.
   • O solucionador executa três ramos paralelos:
     • Heurísticas Clássicas: Simulated Annealing (SA) e Tabu Search (TS) realizam o hill-climbing no problema completo.
     • Recozimento Quântico (QA): Opera em subproblemas menores contendo variáveis de "alto impacto energético", utilizando o tunelamento quântico para escapar de mínimos locais que prendem os métodos de hill-climbing clássicos.
   • O sistema combina iterativamente as melhores soluções de todos os ramos.

4. Propriedades Teóricas:

   • Os autores demonstram que, sob condições moderadas (especificamente quando a razão de instalações retidas em relação ao total de instalações é $>0,5$ e a competição é limitada), a matriz que governa o problema QUBO é definida positiva.
   • Isso implica que, mesmo se as restrições de integridade forem relaxadas (permitindo variáveis contínuas $x_j \in [0, 1]$), a solução ótima converge naturalmente para valores binários ($0$ ou $1$).
   • Um limite superior teórico para o valor objetivo ótimo é derivado usando o teorema de Schur-Horn, calculado como a soma dos $p$ maiores autovalores da matriz de interação.

Principais Contribuições

• Modelo Matemático Inovador: Um modelo baseado em QUBO que produz naturalmente soluções integrais sem restrições inteiras explícitas e captura fatores não lineares complexos, como decaimento por distância e competição de instalações.
• Formulação Pronta para Computação Quântica: O modelo é explicitamente desenhado para aproveitar efeitos quânticos (superposição e tunelamento) via equivalência de Ising spin glass, tornando-o solucionável em recozedores quânticos, recozedores digitais e computadores quânticos baseados em portas lógicas.
• Implementação de Solucionador Híbrido: Um solucionador robusto que combina hill-climbing clássico com tunelamento quântico para navegar em paisagens de otimização complexas.
• Limites Teóricos: A derivação de um limite superior apertado, computável em tempo polinomial, para avaliar a qualidade da solução.
• Integração com SIG: Um fluxo de trabalho flexível integrando dados de censo e TOPSIS para a ponderação de dados de instalações.

Resultos
A estrutura foi aplicada à rota de ônibus B20 de Vancouver (49 paradas):

• Redução de Instalações: O modelo reduziu com sucesso o número de paradas de ônibus em 40% (de 49 para aproximadamente 30) mantendo a cobertura completa de todas as áreas de disseminação (nós de demanda).
• Ganhos de Eficiência: A redução nas paradas resultou em uma redução estimada de 7 minutos no tempo de viagem (aproximadamente 13% do tempo de viagem original) durante o horário de trabalho.
• Qualidade da Solução: Os melhores valores da função objetivo encontrados ficaram dentro de 95% do limite superior teórico (especificamente em $p=45$).
• Desempenho Comparativo: Em experimentos em 30 conjuntos de dados sintéticos, o solucionador híbrido proposto superou estatisticamente um modelo SIC padrão resolvido com o solucionador clássico APOPT em termos de cobertura de demanda através de vários níveis de retenção de instalações.
• Análise de Redundância: O estudo identificou que até 40% das paradas eram redundantes (múltiplas paradas dentro da distância de caminhada dos mesmos nós de demanda) sem impactar significativamente a acessibilidade.

Significância e Alegações
O artigo afirma que esta estrutura oferece um avanço significativo no planejamento de trânsito ao fornecer um método de baixo custo para melhorar a qualidade do serviço através da consolidação estratégica de instalações. Sua principal significância reside em:

1. Ponte entre Computação Clássica e Quântica: Fornece uma aplicação prática e do mundo real para o hardware quântico emergente, demonstrando como planejadores de transporte podem utilizar efeitos quânticos junto com ferramentas clássicas.
2. Robustez do Modelo: A capacidade de gerar soluções naturalmente binárias e calcular limites superiores apertados oferece um nível de garantia teórica e flexibilidade não presente em modelos tradicionais como LSCP ou p-mediana.
3. Escalabilidade: A abordagem híbrida aborda as limitações do hardware quântico atual (ruído e taxas de erro) ao usar solucionadores clássicos para redundância e busca global, enquanto aproveita o tunelamento quântico para otimização local.

Os autores concluem que, embora a abordagem apresente limitações quanto a variáveis inteiras não binárias e restrições de desigualdade, ela demonstra com sucesso que a otimização inspirada em computação quântica pode equilibrar efetivamente os objetivos conflitantes de acessibilidade e eficiência em redes de trânsito urbano complexas.