Resumo Técnico: Planejamento de Circulação de EMUs para a Ferrovia da Silésia

Definição do Problema

O artigo aborda o problema diário de planejamento da circulação de material rodante para unidades múltiplas elétricas (EMUs) na rede de passageiros regional da Ferrovia da Silésia (Koleje Śląskie) na Polônia. O objetivo é atribuir EMUs disponíveis a um quadro de horários fixo de viagens de trem, satisfazendo um conjunto complexo de restrições operacionais.

As principais características do problema incluem:

• Composições Flexíveis: EMUs do mesmo tipo podem ser acoplados em pares em um subconjunto predefinido de viagens para aumentar a capacidade, enquanto outras viagens devem ser atendidas por unidades individuais.
• Capacidade Impulsionada pela Demanda: O modelo incorpora explicitamente restrições tanto para a capacidade de assentos de passageiros quanto para a capacidade de armazenamento de bicicletas, garantindo que as faltas não excedam os limites admissíveis.
• Balanço de Depósito: O plano deve respeitar limites inferiores e superiores no número de EMUs de cada tipo iniciando e terminando o dia em depósitos específicos, mantendo reservas operacionais.
• Disponibilidade de Tripulação: Restrições agregadas limitam o número de EMUs operadas simultaneamente com base na disponibilidade de condutores adequados em depósitos e horários específicos.
• Horizonte Acíclico: O horizonte de planejamento é um único dia, resultando em uma estrutura de circulação acíclica, distinta dos modelos de planejamento semanal cíclico.

Metodologia

Os autores propõem uma abordagem de dupla metodologia, comparando uma formulação clássica de Programação Linear Inteira (ILP) contra uma reformulação de Otimização Binária Quadrática Não Restrita (QUBO).

1. Representação de Grafo/Hipergrafo

O problema é modelado usando um grafo expandido no tempo onde:

• Nós representam viagens de trem e eventos auxiliares de serviço de depósito.
• Arcos representam transições viáveis de uma única EMU entre viagens.
• Hiper-arcos representam transições envolvendo EMUs acopladas (acoplamento, transferência acoplada e desacoplamento).
  Esta formulação de hipergrafo captura naturalmente a complexidade combinatória das composições flexíveis de trens.

2. Abordagem Clássica ILP

O problema é codificado como um Programa Linear Inteiro Misto (MILP) e resolvido usando o solver SCIP.

• Objetivo: Minimiza uma soma ponderada de custos operacionais (fixos e dependentes de distância) e o número de EMUs despachadas (para preservar frotas de reserva).
• Restrições: Inclui cobertura (cada viagem servida exatamente uma vez), balanço de fluxo (continuidade do material rodante), balanço de depósito, limites de capacidade (assentos/bicicletas) e disponibilidade de tripulação.
• Escalabilidade: O número de variáveis binárias escala aproximadamente com $|T| \cdot |T|^2 \cdot |R|$ no pior caso, onde $|T|$ é o número de viagens e $|R|$ é o número de tipos de EMU, embora restrições práticas reduzam significativamente este valor.

3. Abordagem Quântica e Quântica Inspirada (QUBO)

O ILP é reformulado em um problema QUBO para utilizar recozimento quântico (quantum annealing) e heurísticas inspiradas na física.

• Transformação: As restrições são convertidas em termos de penalidade adicionados à função objetivo. Variáveis de folga (slack variables) são introduzidas para lidar com restrições de desigualdade (ex: limites de depósito, disponibilidade de tripulação).
• Solvers:
  • Recozimento Quântico (Quantum Annealing): Executado em sistemas D-Wave Advantage (topologias Pegasus e Zephyr).
  • Quântico-Inspirado: Executado usando o VeloxQ, um solver clássico baseado em heurísticas inspiradas na física (bifurcação simulada/minimização de energia) que não requer hardware quântico.
• Escalabilidade: A formulação QUBO introduz um overhead significativo no número de termos quadráticos, escalando como $|T|^5$ no pior caso, o que cria um gargalo para a geração e armazenamento do modelo antes mesmo da resolução.

Principais Contribuições

1. Modelo ILP Prático: Desenvolvimento de um modelo ILP flexível e diretamente solúvel que integra requisitos específicos do operador: acoplamento de pares restrito a viagens predefinidas, restrição explícita de capacidade de bicicletas e limites agregados de tripulação.
2. Mapeamento QUBO: Uma reformulação específica do problema de circulação de material rodante para QUBO, incluindo uma análise da escala de variáveis e termos, destacando o crescimento rápido das interações quadráticas.
3. Benchmarking Empírico: Um estudo comparativo com dados reais da Ferrovia da Silésia (até 404 viagens e 11 tipos de EMU) avaliando:
   • ILP Clássico (SCIP).
   • Recozimento Quântico (hardware D-Wave).
   • Heurísticas Quânticas-Inspiradas (VeloxQ).
4. Análise de Viabilidade: Identificação da atual fronteira prática para métodos baseados em QUBO no planejamento ferroviário, especificamente em relação ao equilíbrio entre expressividade do modelo e tratabilidade computacional.

Resultados Experimentais

Desempenho do ILP Clássico

• Escalabilidade: O solver SCIP resolveu com sucesso todas as instâncias, incluindo a maior com ~404 viagens e ~380.000 variáveis binárias.
• Tempo de Execução: Soluções ótimas ou de alta qualidade foram obtidas em segundos para instâncias médias e em até aproximadamente 40 minutos para as maiores instâncias.
• Qualidade: O modelo produziu planos de circulação viáveis e práticos que respeitaram todas as restrições, incluindo cenários complexos de acoplamento e limites de capacidade.

Desempenho Quântico e Quântico-Inspirado

• Limitações de Hardware: Os recozedores quânticos D-Wave foram restritos às menores instâncias (até ~50 viagens) devido às limitações de incorporação (embedding) e ao número de qubits disponíveis. O novo sistema Advantage2 (topologia Zephyr) resolveu subinstâncias ligeiramente maiores que o sistema baseado em Pegasus, mas não conseguiu lidar com instâncias além do tamanho 2a.
• Gargalo de Construção QUBO: A barreira principal não foi o tempo de resolução, mas a geração da matriz QUBO. Para instâncias de tamanho médio (ex: 78 viagens), o número de termos quadráticos atingiu ~1,8 milhão e, para instâncias maiores, excedeu $10^8$, tornando a construção do modelo inviável dentro da RAM disponível (62 GB).
• Comparação de Solvers:
  • VeloxQ: Superou o D-Wave em instâncias pequenas, encontrando soluções ótimas rapidamente. No entanto, enfrentou a mesma limitação quanto à geração do modelo QUBO para instâncias maiores.
  • Viabilidade: Tanto os solvers quânticos quanto os quânticos-inspirados exigiram pós-processamento para filtrar soluções que violavam restrições suaves (variáveis de folga), pois o método de penalidade não garante a viabilidade por construção.

Significância e Alegações

O artigo alega que, para o problema específico de circulação diária de EMU com as restrições descritas:

• O ILP Clássico é atualmente superior: A abordagem clássica (SCIP) é o único método capaz de lidar com a escala total de instâncias ferroviárias regionais reais (centenas de viagens) dentro de prazos práticos e garantindo a viabilidade.
• Estado Atual dos Métodos Quânticos: As abordagens baseadas em QUBO (tanto quânticas quanto quânticas-inspiradas) estão atualmente limitadas a subproblemas pequenos ou instâncias altamente restritas devido à expansão quadrática de termos e ao overhead de incorporação. Elas ainda não superam os solvers clássicos para o planejamento diário de ponta a ponta.
• Direção Futura: Os resultados sugerem que uma arquitetura híbrida clássico-quântica é o caminho mais viável a curto prazo. Nesse framework, o solver clássico lidaria com o problema global, enquanto os métodos baseados em QUBO poderiam ser aplicados a subproblemas localizados de alta complexidade (ex: "pontos críticos" de acoplamento ou janelas de reprogramação de curto prazo) onde o tamanho do problema é reduzido.
• Utilidade Prática: O estudo demonstra que restringir a janela de tempo de transferência ($\Delta$) serve como uma heurística eficaz para reduzir a complexidade do modelo para solvers clássicos sem degradar significativamente a qualidade da solução, uma característica que também poderia auxiliar na esparsificação de formulações QUBO.

Os autores concluem que, embora os métodos quânticos mostrem promessa na amostragem de estados de baixa energia e no fornecimento de soluções viáveis alternativas, sua aplicação ao planejamento de circulação ferroviária de grande escala permanece limitada pelas limitações de hardware e pelo overhead matemático da reformulação QUBO.