Resumo Técnico: Cronogramas Recorrentes de Transporte Público: Identificação Estável a partir de GTFS e Análise de Similaridade

1. Declaração do Problema

Os cronogramas de transporte público exibem estruturas de serviço recorrentes onde múltiplas datas de calendário compartilham tabelas de horários idênticas para o passageiro (ex: dias úteis padrão), enquanto outras diferem devido a fins de semana, feriados ou eventos especiais. No entanto, o General Transit Feed Specification (GTFS), o padrão global para dados de trânsito, não codifica explicitamente esses "DayTypes" (Tipos de Dia) recorrentes. Em vez disso, o GTFS representa o serviço por meio de tabelas interdependentes (calendário, viagens, tempos de parada, formas), forçando modelos a jusante para escalonamento, atribuição de veículos e análise de demanda a reconstruir objetos de oferta recorrentes a partir de dados fragmentados.

O desafio central é duplo:

1. Identificação: Como extrair classes de serviço estáveis e recorrentes (DayTypes) do GTFS sem depender de identificadores administrativos (ex: shape_id, stop_id) que podem mudar entre as versões do feed, apesar de o serviço físico permanecer constante.
2. Comparação: Como comparar esses cronogramas extraídos para distinguir entre diferenças rigorosas de tabela (ex: uma diferença de 1 minuto) e mudanças estruturais substantivas (ex: remoção ou adição de rotas).

2. Metodologia

2.1. Definições Formais

O artigo formaliza dois conceitos fundamentais:

• Padrão de Rota (Route Pattern): Uma variante de serviço voltada ao passageiro, definida por uma sequência ordenada de paradas e direção de viagem. Diferente do shape_id do GTFS, que é um identificador administrativo, um Padrão de Rota é definido pelo caminho físico e pela ordem das paradas.
• DayType (Tipo de Dia): Uma categoria de datas que compartilham exatamente o mesmo conjunto de viagens de Padrão de Rota operando nos mesmos horários. É definido estritamente como o conjunto de especificações de viagem: $DayType(d) = \{(p, dep_t, arr_t)\}$, onde $p$ é o Padrão de Rota, e $dep_t/arr_t$ são a primeira partida e a última chegada.

2.2. Extração Estável via Indexação H3

Para garantir a estabilidade contra a renomeação de identificadores administrativos, os autores propõem um método de extração usando o sistema de indexação geoespacial hierárquica H3 (Uber Technologies, 2018).

• Chave de Padrão de Rota: Em vez de usar shape_id ou stop_id, o método converte a sequência ordenada de coordenadas das paradas em uma sequência de células H3 (Resolução 15). Esta sequência serve como uma chave determinística e estável para o Padrão de Rota.
• Algoritmo de Extração:
  1. Expandir as tabelas de calendário e exceções do GTFS para gerar uma lista de viagens ativas para cada data.
  2. Para cada viagem ativa, converter sua sequência de paradas em uma chave de Padrão de Rota baseada em H3.
  3. Formar uma tupla de especificação de viagem: $(H3\_key, first\_departure, last\_arrival)$.
  4. Agrupar datas que compartilham exatamente o mesmo conjunto de tuplas de especificação de viagem em um único DayType.
• Invariância: Esta abordagem garante que, se dois feeds de GTFS descreverem o mesmo serviço físico, mas utilizem IDs administrativos diferentes, a partição de DayType extraída permanecerá idêntica, desde que as coordenadas e a ordem das paradas não mudem.

2.3. Estrutura de Comparação de Cronogramas

O artigo introduz uma hierarquia de três níveis de métricas para comparar DayTypes $A$ e $B$:

1. Métricas Exatas ($d_0$):

   • Utiliza a Distância de Jaccard no conjunto de especificações de viagem.
   • Trata qualquer diferença no Padrão de Rota, horário de partida ou horário de chegada como um DayType distinto.
   • Serve como um sinal de auditoria rigoroso para qualidade de dados e ajustes de tempo intencionais.

2. Métricas com Tolerância de Tempo ($d_\epsilon$):

   • Introduz um parâmetro de tolerância $\epsilon$ (ex: 1, 3 ou 5 minutos).
   • Duas viagens são $\epsilon$-equivalentes se compartilharem a mesma chave de Padrão de Rota e seus horários de partida/chegada diferirem por $\le \epsilon$.
   • Calcula a distância de Jaccard com tolerância de tempo baseada no número máximo de pares $\epsilon$-equivalentes.
   • Esta camada determina se as diferenças exatas são apenas pequenos desvios de tempo.

3. Diagnósticos de Comparabilidade Estrutural:

   • Para evitar a interpretação excessiva de pequenas correspondências como similaridades de todo o cronograma, a estrutura calcula:
     • Parcela Correspondente ($M_\epsilon$): A proporção de viagens que podem ser pareadas sob tolerância.
     • Desequilíbrio de Contagem de Viagens ($Q$): A diferença relativa no número total de viagens entre os dois DayTypes.
     • Contagem Não Correspondida ($U_\epsilon$): O número de viagens que não podem ser pareadas.
   • Isso distingue entre uma "versão com deslocamento de tempo do mesmo cronograma" (alta $M_\epsilon$, baixa $Q$) e uma "mudança estrutural de serviço" (baixa $M_\epsilon$, alta $Q$).

3. Principais Contribuições

1. Formalização: Define Padrões de Rota e DayTypes como objetos de oferta recorrentes, distintos do escalonamento interno de veículos ou tripulação.
2. Extração Estável: Desenvolve um procedimento de extração de GTFS usando chaves de padrão de rota H3 que é invariante à renomeação de identificadores administrativos, resolvendo um problema crítico de reprodutibilidade na análise longitudinal de GTFS.
3. Hierarquia de Comparação: Propõe um sistema de métricas que separa a auditoria estrita (exata), a sensibilidade de tempo (tolerância de tempo) e a mudança estrutural (diagnósticos), abordando as limitações de usar uma única métrica de similaridade.
4. Utilidade a Jusante: Fornece conjuntos de cronogramas recorrentes compactos que podem servir como entradas para modelos de sincronização de horários, escalonamento de veículos, atribuição de demanda e modelos de diagnóstico de incompatibilidade.
5. Validação Empírica: Valida a estrutura em feeds de GTFS do Japão e do Canadá, demonstrando a extração bem-sucedida em diferentes escalas de rede e estratégias de codificação de calendário.

4. Resultados e Descobertas

A estrutura foi aplicada a 40 agências japonesas e 38 canadenses.

• Sucesso da Extração: O algoritmo identificou com sucesso DayTypes recorrentes para todas as agências sem intervenção manual, recuperando ciclos semanais padrão (dias úteis/sábado/domingo), exceções de feriados e anomalias de um único dia.
• Contagem de DayTypes: A mediana de DayTypes não vazios por agência foi 4 em ambos os países. No entanto, as agências japonesas mostraram maior variabilidade (máximo de 39) em comparação com as canadenses (máximo de 17), refletindo calendários sazonais/feriados mais granulares na amostra japonesa.
• Análise de Disjunção:
  • Disjunção Exata: Uma parte significativa das agências apresentou pares de DayTypes com zero viagens compartilhadas (distância de Jaccard = 1.0). Isso foi mais comum no Canadá (36% das agências) do que no Japão (15%).
  • Impacto da Tolerância: Ao aplicar a tolerância de tempo (1–5 minutos), muitos pares "exatamente disjuntos" no Canadá adquiriram algumas viagens correspondentes, sugerindo que eram variações de tempo de estruturas similares. No Japão, a disjunção exata foi mais persistente, indicando uma separação estrutural mais forte entre os regimes de serviço.
  • Realidade Estrutural: Apesar de adquirir correspondências sob tolerância, a mediana da parcela correspondente permaneceu baixa (6,3% no Canadá, 0% no Japão) com altos desequilíbrios de contagem de viagens. Isso confirma que muitos DayTypes "disjuntos" representam volumes de serviço ou conjuntos de rotas fundamentalmente diferentes, e não apenas cronogramas deslocados.
• Nidificação (Nesting): A nidificação total (onde um DayType é um subconjunto estrito de outro) foi observada em 69% das agências japonesas e 58% das canadenses, indicando que a redução graduada de serviço é uma prática comum em ambas as regiões.

5. Significância e Alegações

O artigo posiciona sua contribuição como uma camada de representação metodológica, em vez de um novo algoritmo de otimização. Sua significância reside em:

• Preenchimento da Lacuna: Conecta dados GTFS brutos e fragmentados aos objetos de oferta recorrentes necessários para modelos metodológicos a jusante (ex: análise de função de déficit, escalonamento de veículos).
• Estabilidade: Ao desacoplar a identificação de serviço dos IDs administrativos, permite uma análise longitudinal confiável da evolução dos cronogramas entre as versões dos feeds.
• Interpretação Matizada: A hierarquia de métricas proposta evita a classificação errônea de ruído de tempo menor como mudanças estruturais de serviço, mantendo ainda a capacidade de auditar desvios exatos de cronograma.
• Representação Compacta: Transforma grandes tabelas de horários específicas por data em uma biblioteca compacta de DayTypes recorrentes, facilitando o escalonamento, a atribção de demanda e a análise de incompatibilidade de forma mais eficiente.

Os autores concluem que, embora o GTFS não defina explicitamente os DayTypes, eles estão implicitamente codificados e podem ser extraídos e comparados de forma robusta usando esta estrutura, fornecendo uma base necessária para o planejamento e análise avançados de transporte.