⚡ electrical engineering

Recurring Public Transit Schedules: Stable Identification from GTFS and Similarity Analysis

Cet article introduit une méthode pour identifier et formaliser les horaires de transport public récurrents sous forme de « DayTypes » à partir des données GTFS en utilisant des clés de motifs de parcours H3 et des mesures de similitude, permettant ainsi une synchronisation plus efficace des horaires, de la planification des véhicules et de l'affectation de la demande en distinguant les décalages temporels mineurs des changements de service significatifs.

Auteurs originaux : Evgeny Makarov, Georgy Taubkin

Publié 2026-06-16

📖 6 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : Evgeny Makarov, Georgy Taubkin

Article original sous licence CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Ceci est une explication générée par l'IA de l'article ci-dessous. Elle n'a pas été rédigée ni approuvée par les auteurs. Pour une précision technique, consultez l'article original. Lire la clause de non-responsabilité complète

Imaginez les horaires de transports publics comme une bibliothèque massive et chaotique de fiches horaires de bus et de trains. Si vous regardez un calendrier, vous pourriez penser que chaque jour possède un horaire unique. Mais en réalité, la plupart des jours sont des copies les uns des autres. Les lundis ressemblent aux autres lundis ; les samedis ressemblent aux autres samedis. Les jours fériés, cependant, sont les « éditions spéciales » qui brisent le modèle.

Le problème est que le format numérique standard utilisé pour partager ces horaires (appelé GTFS) ne les organise pas de cette manière. Il répertorie chaque trajet pour chaque jour comme s'ils étaient tous uniques, ce qui empêche les ordinateurs de voir les modèles répétitifs. C'est comme avoir un livre de recettes où la « Soupe du lundi » et la « Soupe du mardi » sont répertoriées comme deux recettes complètement différentes, même si elles sont identiques, simplement parce que les numéros de page sont différents.

Ce document présente une méthode pour nettoyer cette bibliothèque et regrouper ces horaires en « familles » logiques.

L'idée centrale : les « DayTypes »

Les auteurs appellent ces familles des DayTypes. Considérez un DayType comme un « modèle » ou un « moule ».

Le Modèle : Au lieu de regarder 365 jours différents, le système trouve que 52 d'entre eux sont des « Modèles de Lundi », 52 sont des « Modèles de Samedi », et peut-être 5 sont des « Modèles du Jour de l'An ».
L'Objectif : En regroupant les jours de cette manière, les planificateurs peuvent cesser de traiter chaque jour comme un puzzle unique. Ils peuvent voir la vue d'ensemble : « Oh, une agence utilise un moule de 'Jour de semaine', un moule de 'Week-end' et un moule de 'Jour férié'. »

Le problème des « Noms » vs la « Réalité »

Le document souligne un problème délicat dans la façon dont les données de transport sont actuellement stockées. Elles reposent sur des identifiants administratifs (comme shape_id ou stop_id) qui sont comme des numéros de catalogue internes de bibliothèque.

L'Analogie : Imaginez une ligne de bus qui va d'un point A à un point B. Un jour, l'agence de transport change le numéro de catalogue interne de cette ligne de « Route-123 » à « Route-456 », même si le bus s'arrête exactement aux mêmes endroits dans le même ordre.
L'Ancienne Méthode : Un ordinateur penserait que la « Route-123 » et la « Route-456 » sont deux bus complètement différents. Il penserait que l'horaire a changé, même si l'expérience du passager est restée la même.
La Nouvelle Méthode (Clés H3) : Les auteurs utilisent une astuce ingénieuse appelée indexation H3. Au lieu de se fier aux numéros de catalogue internes, ils regardent la carte physique réelle. Ils transforment chaque arrêt de bus en une petite tuile numérique unique sur une carte (comme un pixel). Si le bus s'arrête sur les mêmes tuiles dans le même ordre, le système sait qu'il s'agit de la même route, quel que soit le nom donné par l'agence en interne. Cela rend le système « immunisé » contre les changements de noms administratifs.

Le test de « Tolérance » : Est-ce un changement ou juste un décalage ?

Une fois que le système a regroupé les jours, il doit les comparer. Les auteurs ont créé une « règle » en trois étapes pour mesurer à quel point deux horaires sont différents :

La Règle Exacte (L'Audit) : Elle vérifie si les horaires sont identiques à la seconde près. Si un bus part à 8:00:00 le lundi et à 8:00:01 le mardi, cette règle dit : « Ce sont des différences ! » Cela est utile pour détecter les erreurs de données ou les micro-ajustements intentionnels.
La Règle Flexible (Tolérante au temps) : C'est la règle de « tous les jours ». Elle demande : « Si nous acceptons un petit retard (disons, 3 minutes), ces horaires sont-ils fondamentalement les mêmes ? » Si le bus part à 8h00 le lundi et à 8h02 le mardi, cette règle dit : « C'est assez proche ! C'est le même horaire, juste légèrement décalé. »
La Règle Structurelle : Elle vérifie si la structure est différente. Si le lundi compte 10 bus et le mardi seulement 2, ou si le mardi saute un arrêt complet, la règle dit : « Ce sont des horaires totalement différents », même si les quelques bus qui circulent sont proches dans le temps.

Ce qu'ils ont découvert

Les auteurs ont testé ce système sur des données réelles du Japon et du Canada.

Les Résultats : Ils ont réussi à éliminer l'encombrement et à trouver les modèles cachés. Par exemple, dans une ville canadienne, ils ont trouvé un cycle propre de seulement trois DayTypes : les Jours de semaine, les Samedis et les Dimanches. Dans une ville japonaise, ils ont trouvé un DayType de « Nouvel An » qui était complètement différent de tout le reste.
La Surprise : Ils ont découvert qu'au Canada, de nombreux horaires qui semblaient « complètement différents » sur papier (parce que les heures ne correspondaient pas exactement) étaient en fait le même horaire avec de petits décalages temporels. Cependant, au Japon, certains horaires qui semblaient différents étaient véritablement structurellement différents (itinéraires ou arrêts différents), et non de simples décalages horaires.

Pourquoi cela importe

Ce document n'invente pas une nouvelle façon de faire circuler les bus ou de prédire le trafic. À la place, il construit une meilleure couche de traduction.

Il prend des données brutes et désordonnées et les transforme en « DayTypes » propres et reconnaissables.
Il permet aux ordinateurs de ne plus être confus par les changements de noms ou les minuscules différences de temps.
Il donne aux planificateurs une liste compacte et claire de « modèles d'horaires » avec lesquels travailler, ce qui facilite la comparaison entre différentes villes, la vérification des erreurs ou la planification future.

En résumé, ce document fournit une méthode intelligente et stable pour organiser le chaos des horaires de transports publics, transformant une montagne de données quotidiennes en un ensemble gérable de modèles répétitifs.

Résumé technique : Horaires de transport public récurrents : Identification stable à partir du GTFS et analyse de similitude

1. Énoncé du problème

Les horaires de transport public présentent des structures de service récurrentes où de multiples dates partagent des horaires identiques du point de vue des passagers (par exemple, les jours de semaine standards), tandis que d'autres diffèrent en raison des week-ends, des jours fériés ou d'événements spéciaux. Cependant, le General Transit Feed Specification (GTFS), la norme mondiale pour les données de transport, n'encode pas explicitement ces « DayTypes » (types de journée) récurrents. Au lieu de cela, le GTFS représente le service par le biais de tables interdépendantes (calendrier, trajets, arrêts, formes), forçant les modèles en aval pour la planification, l'affectation des véhicules et l'analyse de la demande à reconstruire des objets d'offre récurrents à partir de données fragmentées.

Le défi central est double :

Identification : Comment extraire des classes de service récurrentes et stables (DayTypes) à partir du GTFS sans dépendre d'identifiants administratifs (par exemple, shape_id, stop_id) qui peuvent changer entre les versions de flux malgré un service physique constant.
Comparaison : Comment comparer ces horaires extraits pour distinguer les différences de l'horaire strict (ex. : un décalage de 1 minute) des changements structurels substantiels (ex. : suppression ou ajout d'une ligne).

2. Méthodologie

2.1. Définitions formelles

Le document formalise deux concepts clés :

Modèle de ligne (Route Pattern) : Une variante de service face au passager définie par une séquence ordonnée d'arrêts et une direction de trajet. Contrairement à l'identifiant administratif shape_id du GTFS, un Modèle de ligne est défini par le chemin physique et l'ordre des arrêts.
Type de journée (DayType) : Une catégorie de dates partageant exactement le même ensemble de trajets de Modèles de ligne opérant aux mêmes heures. Il est défini strictement comme l'ensemble des spécifications de trajets : $DayType(d) = \{(p, dep_t, arr_t)\}$ , où $p$ est le Modèle de ligne, et $dep_t/arr_t$ sont le premier départ et la dernière arrivée.

2.2. Extraction stable via l'indexation H3

Pour garantir la stabilité face au renommage des identifiants administratifs, les auteurs proposent une méthode d'extraction utilisant le système d'indexation géospatiale hiérarchique H3 (Uber Technologies, 2018).

Clé de Modèle de ligne : Au lieu d'utiliser shape_id ou stop_id, la méthode convertit la séquence ordonnée des coordonnées d'arrêts en une séquence de cellules H3 (Résolution 15). Cette séquence sert de clé déterministe et stable pour le Modèle de ligne.
Algorithme d'extraction :
1. Étendre les tables de calendrier et d'exception du GTFS pour générer une liste de trajets actifs pour chaque date.
2. Pour chaque trajet actif, convertir sa séquence d'arrêts en une clé de Modèle de ligne basée sur H3.
3. Former un tuple de spécification de trajet : $(H3\_key, first\_departure, last\_arrival)$ .
4. Grouper les dates qui partagent exactement le même ensemble de tuples de spécification de trajet en un seul DayType.
Invariance : Cette approche garantit que si deux flux GTFS décrivent le même service physique mais utilisent des identifiants administratifs différents, la partition de DayType extraite reste identique, à condition que les coordonnées et l'ordre des arrêts ne changent pas.

2.3. Cadre de comparaison des horaires

Le document introduit une hiérarchie à trois niveaux de métriques pour comparer les DayTypes $A$ et $B$ :

Métriques exactes ( $d_0$ ) :
- Utilise la distance de Jaccard sur l'ensemble des spécifications de trajets.
- Traite toute différence de Modèle de ligne, d'heure de départ ou d'heure d'arrivée comme un DayType distinct.
- Sert de signal d'audit strict pour la qualité des données et les ajustements de temps intentionnels.
Métriques avec tolérance temporelle ( $d_\epsilon$ ) :
- Introduit un paramètre de tolérance $\epsilon$ (ex. : 1, 3 ou 5 minutes).
- Deux trajets sont $\epsilon$ -équivalents s'ils partagent la même clé de Modèle de ligne et que leurs heures de départ/arrivée diffèrent de $\le \epsilon$ .
- Calcule la distance de Jaccard avec tolérance temporelle basée sur le nombre maximum de paires $\epsilon$ -équivalentes.
- Cette couche détermine si les différences exactes sont de simples décalages temporels mineurs.
Diagnostics de comparabilité structurelle :
- Pour éviter de sur-interpréter de petites correspondances comme des similitudes de programmes complets, le cadre calcule :
  - Part de correspondance ( $M_\epsilon$ ) : La proportion de trajets qui peuvent être appariés sous la tolérance.
  - Déséquilibre du nombre de trajets ( $Q$ ) : La différence relative du nombre total de trajets entre les deux DayTypes.
  - Nombre non apparié ( $U_\epsilon$ ) : Le nombre de trajets qui ne peuvent pas être appariés.
- Cela distingue une « version décalée dans le temps du même horaire » (haute $M_\epsilon$ , faible $Q$ ) d'un « changement de service structurel » (faible $M_\epsilon$ , haute $Q$ ).

3. Contributions clés

Formalisation : Définit les Modèles de ligne et les DayTypes comme des objets d'offre récurrents, distincts de la planification interne des véhicules ou du personnel.
Extraction stable : Développe une procédure d'extraction GTFS utilisant des clés de Modèle de ligne H3 qui est invariante au renommage des identifiants administratifs, résolvant un problème critique de reproductibilité dans l'analyse longitudinale des GTFS.
Hiérarchie de comparaison : Propose un système de métriques qui sépare l'audit strict (exact), la sensibilité temporelle (tolérance de temps) et les diagnostics structurels (changements), répondant aux limites de l'utilisation d'une seule métrique de similitude.
Utilité en aval : Fournit des ensembles d'horaires récurrents compacts pouvant servir d'entrées pour la synchronisation des horaires, l'affectation des véhicules, l'assignation de la demande et les modèles de diagnostic de décalage.
Validation empirique : Valide le cadre sur des flux GTFS du Japon et du Canada, démontrant une extraction réussie à travers différentes échelles de réseaux et stratégies d'encodage de calendrier.

4. Résultats et conclusions

Le cadre a été appliqué à 40 agences japonaises et 38 canadiennes.

Succès de l'extraction : L'algorithme a identifié avec succès des DayTypes récurrents pour toutes les agences sans intervention manuelle, récupérant les cycles hebdomadaires standards (jours de semaine/samedi/dimanche), les exceptions de jours fériés et les anomalies d'une seule journée.
Comptage des DayTypes : Le nombre médian de DayTypes non vides par agence était de 4 dans les deux pays. Cependant, les agences japonaises présentaient une plus grande variabilité (max 39) par rapport aux agences canadiennes (max 17), reflétant des calendriers saisonniers/fériés plus granulaires dans l'échantillon japonais.
Analyse de la disjointure :
- Disjointure exacte : Une partie significative des agences présentait des paires de DayTypes sans trajet partagé (distance de Jaccard = 1,0). Cela était plus fréquent au Canada (36 % des agences) qu'au Japon (15 %).
- Impact de la tolérance : En appliant une tolérance temporelle (1 à 5 minutes), de nombreuses paires « exactement disjointes » au Canada ont acquis des correspondances, suggérant qu'il s'agissait de variations temporelles de structures similaires. Au Japon, la disjointure exacte était plus persistante, indiquant une séparation structurelle plus forte entre les régimes de service.
- Réalité structurelle : Malgré l'acquisition de correspondances sous la tolérance, la part de correspondance médiane est restée faible (6,3 % au Canada, 0 % au Japon) avec des déséquilibres élevés du nombre de trajets. Cela confirme que de nombreux DayTypes « disjoints » représentent fondamentalement des volumes de service ou des ensembles de routes différents, et non de simples décalages d'horaires.
Emboîtement (Nesting) : Un emboîtement complet (où un DayType est un sous-ensemble strict d'un autre) a été observé dans 69 % des agences japonaises et 58 % des agences canadiennes, indiquant qu'une réduction graduée du service est une pratique courante dans les deux régions.

5. Signification et affirmations

Le document positionne sa contribution comme une couche de représentation méthodologique plutôt que comme un nouvel algorithme d'optimisation. Sa signification réside dans :

Combler le fossé : Il connecte les données GTFS brutes et fragmentées aux objets d'offre récurrents requis par les modèles méthodologiques en aval (ex. : analyse de la fonction de déficit, planification des véhicules).
Stabilité : En découplant l'identification du service des identifiants administratifs, il permet une analyse longitudinale fiable de l'évolution des horaires à travers les versions de flux.
Interprétation nuancée : La hiérarchie de métriques proposée empêche la classification erronée du bruit temporel mineur comme des changements de service structurels, tout en préservant la capacité d'auditer les écarts horaires exacts.
Représentation compacte : Il transforme les grands horaires datés en une bibliothèque compacte de DayTypes récurrents, facilitant une planification, une assignation de la demande et une analyse de décalage plus efficaces.

Les auteurs concluent que bien que le GTFS ne définisse pas explicitement les DayTypes, ils sont implicitement encodés et peuvent être extraits et comparés de manière robuste à l'aide de ce cadre, fournissant ainsi une base nécessaire pour la planification et l'analyse avancées du transport.