Coordinated optimization of departure sequencing and section-track allocation in railway short-term concentrated departure scenarios based on qubo and hybrid quantum algorithms

Resumo Técnico: Otimização Coordenada de Sequenciamento de Partida e Alocação de Seção-Via em Cenários de Partida Concentrada de Curto Prazo em Ferrovias

Definição do Problema

O estudo aborda o cenário de partida concentrada de curto prazo em operações ferroviárias, uma situação em que múltiplos trens ficam prontos para partir dentro de uma janela temporal estreita. Diferente do planejamento convencional de tabelas de horários, este cenário é caracterado por alta sensibilidade operacional, restrições de infraestrutura local rigorosas e o acoplamento imediato de prioridade de partida, capacidade de seção e recursos de estações a jusante.

O desafio central é que uma decisão de despacho no estágio de partida se propaga rapidamente pela rede, afetando a liberação de seções, a ocupação de estações intermediárias, conflitos de via e a propagação de atrasos. A literatura existente frequentemente trata o ajuste de tabelas, o roteamento e a alocação de plataformas como subproblemas separados. Este artigo argumenta que a organização de partidas concentradas de curto prazo deve ser tratada como um problema de despacho acoplado, exigindo a otimização coordenada do sequenciamento de partida e da alocação de seção-via dentro de um arcabouço de decisão unificado.

Metodologia

Os autores propõem um arcabouço de otimização em camadas consistindo em dois estágios distintos: uma camada de decisão combinatória e uma camada de avaliação baseada em simulação.

1. Camada de Decisão Combinatória Baseada em QUBO
O problema central de decisão é formulado como um modelo de Otimização Binária Quadrática Não Restrita (QUBO). Esta abordagem codifica decisões discretas de escalonamento em um framework binário unificado:

• Variáveis: O modelo utiliza variáveis binárias para representar duas decisões principais:
  • $x_{i,p}$: Se o trem $i$ parte da posição $p$.
  • $y_{i,\tau,l}$: Se o trem $i$ utiliza a via $l$ na seção $\tau$.
• Restrições e Penalidades: Restrições rígidas (ex: cada trem atribuído a exatamente uma posição, cada via utilizada por no máximo um trem) e preferências operacionais suaves são incorporadas à função objetivo via termos de penalidade:
  • $H_{seq}$: Unicidade do sequenciamento de partida.
  • $H_{track}$: Unicidade da seleção de seção-via.
• $H_{switch}$: Penalidade para trocas frequentes de via entre seções adjacentes.
  • $H_{cong}$: Penalidade para congestionamento (múltiplos trens na mesma via de partida-seção).
• Objetivo: Minimizar $E_{QUBO}(z) = z^T Q z$, onde $z$ é o vetor de decisão binária e $Q$ é a matriz de coeficientes.

2. Camada de Avaliação Baseada em Simulação
Reconhecendo que a viabilidade combinatória estática não garante a viabilidade operacional, uma camada de simulação avalia as soluções decodificadas do QUBO. Esta camada simula o movimento real dos trens, contabilizando:

• Interações Dinâmicas: Tempos de liberação de seção, regras de permanência em estações intermediárias e restrições de capacidade de plataforma.
• Métricas de Custo: A simulação calcula um custo abrangente ($E_{sim}$) composto por:
  • Custo de Atraso: Total de atrasos de partida e de estações intermediárias.
  • Custo de Troca de Via: Número de transições de via.
  • Custo de Flutuação de Seção: Desvio dos tempos de circulação reais em relação à linha de base.
  • Custo de Capacidade de Plataforma: Penalidades por exceder os limiares de permanência na estação.

3. Comparação Algorítmica
O arcabouço serve como um banco de testes comum para comparar vários mecanismos de busca que resolvem o mesmo problema QUBO:

• Heurísticas Convencionais: Algoritmo Genético (GA), Otimização por Enxame de Partículas (PSO), Simulated Annealing (SA).
• Métodos Inspirados em Computação Quântica: Quantum GA (QGA), Quantum PSO (QPSO), Quantum SA (QSA).
• Algoritmos Híbridos: Combinações dos acima com QAOA (Algoritmo de Otimização Aproximada Quântica) para refinamento local (ex: QPSO-QAOA).

Principais Contribuições

1. Formulação QUBO Unificada: O estudo estabelece um único modelo QUBO que codifica conjuntamente o sequenciamento de partida e a alocação de seção-via, permitindo que restrições heterogêneas sejam tratadas dentro de um objetivo binário consistente.
2. Mecanismo de Avaliação em Camadas: Introduz um mecanismo de avaliação baseado em simulação que avalia os esquemas decodificados quanto à viabilidade temporal e desempenho operacional, abordando a lacuna entre soluções combinatórias estáticas e a dinâmica de despacho dependente do tempo.
3. Estrutura de Comparação Comum: O artigo fornece um ambiente padronizado para comparar algoritmos convencionais, inspirados em quântica e híbridos sob condições idênticas de modelagem e avaliação, em vez de comparar diferentes reformulações de problemas.
4. Validação Empírica: Experimentos numéricos são conduzidos sob configurações normais, dinâmicas (perturbadas), de robustez e de expansão de escala para analisar o comportamento algorítmico.

Resultados

O estudo foi testado em uma rede abstrata com 5 estações, 4 seções e 5 trens por direção (2 vias por seção).

• Cenário Normal: Sob condições determinísticas, o QPSO-QAOA alcançou o melhor desempenho com um custo total de 50 e atraso total de 50 minutos. Métodos inspirados em quântica e híbridos geralmente superaram as bases convencionais (GA, PSO, SA).
• Cenário Dinâmico: Quando os tempos de circulação das seções flutuaram em 20%, a qualidade estrutural das soluções divergiu. Métodos com reforço quântico reduziram os custos abrangentes em 4,28%–26,26% e os atrasos totais em 4,37%–24,25% em média comparados aos seus equivalentes convencionais. O QGA-QAOA teve o melhor desempenho neste cenário.
• Robustez: À medida que as taxas de perturbação aumentaram, os esquemas gerados por métodos inspirados em quântica mantiveram custos menores e menos penalidades de ocupação de plataforma em comparação com os métodos convencionais, indicando melhor estabilidade estrutural contra a propagação de atrasos.
• Escalabilidade: Conforme o número de trens aumentou, a lacuna de desempenho entre os métodos se alargou. Métodos inspirados em quântica e híbridos mostraram um crescimento de custo mais moderado em cenários de média a grande escala em comparação com a rápida escalada de custos observada em alguns métodos convencionais.

Significância e Alegações

O artigo afirma que a integração da modelagem baseada em QUBO com a avaliação baseada em simulação fornece um arcabouço metodológico útil para o escalonamento de partidas concentradas de curto prazo em ferrovias.

Os autores declaram explicitamente que o objetivo não é reivindicar a implementação operacional imediata da computação quântica no despacho ferroviário. Em vez disso, o estudo visa avaliar se a modelagem baseada em QUBO, combinada com estratégias de solução quânticas e híbridas, oferece uma direção metodológica útil para esta classe de problemas de escalonamento. Os achados sugerem que esses métodos podem gerar esquemas candidatos viáveis que, quando avaliados dinamicamente, demonstram superior adaptabilidade à incerteza operacional e restrições de recursos em comparação com heurísticas tradicionais.

O estudo reconhece limitações, observando que a validação atual depende de cenários de teste construídos, em vez de dados operacionais do mundo real, layouts de estações ou diagramas originais de trens. Trabalhos futuros são propostos para estender o arcabouço para corredores ferroviários reais e configurações de rede mais complexas.