Technische Samenvatting: Recurrente Openbaar Vervoer-schema's: Stabiele Identificatie vanuit GTFS en Gelijkenisanalyse

1. Probleemstelling

Openbaar vervoer-schema's vertonen recurrente dienstverleningsstructuren waarbij meerdere kalenderdata identieke passagiersgerichte dienstregelingen delen (bijv. standaard werkdagen), terwijl andere dagen verschillen door weekenden, feestdagen of speciale evenementen. De General Transit Feed Specification (GTFS), de wereldwijde standaard voor transitdata, codeert deze recurrente "DayTypes" echter niet expliciet. In plaats daarvan vertegenwoordigt GTFS dienstverlening via onderling afhankelijke tabellen (kalender, ritten, haltes, vormen), waardoor downstream-modellen voor planning, voertuigtoewijzing en vraaganalyse de recurrente aanbodobjecten uit gefragmenteerde data moeten reconstrueren.

De kernuitdaging is tweeledig:

1. Identificatie: Hoe extraheer je stabiele, recurrente dienstklassen (DayTypes) uit GTFS zonder te vertrouwen op administratieve identificatoren (bijv. shape_id, stop_id) die tussen feed-releases kunnen veranderen, ondanks dat de fysieke dienst hetzelfde blijft.
2. Vergelijking: Hoe vergelijk je deze geëxtraheerde schema's om onderscheid te maken tussen strikte timetable-verschillen, kleine tijdsverschuivingen (bijv. een vertraging van 1 minuut) en substantiële structurele veranderingen (bijv. het verwijderen of toevoegen van een route).

2. Methodologie

2.1. Formele Definities

Het artikel formaliseert twee belangrijke concepten:

• Routepatroon (Route Pattern): Een passagiersgerichte dienstvariant gedefinieerd door een geordende haltevolgorde en reisrichting. In tegenstelling tot de administratieve identifier shape_id, wordt een Routepatroon gedefinieerd door het fysieke pad en de volgorde van haltes.
• DayType: Een categorie data die exact dezelfde set Routepatroon-ritten uitvoert op hetzelfde tijdstip. Het wordt strikt gedefinieerd als de set van rit-specificaties: $DayType(d) = \{(p, dep_t, arr_t)\}$, waarbij $p$ het Routepatroon is, en $dep_t/arr_t$ de eerste vertrek- en laatste aankomsttijden zijn.

2.2. Stabiele Extractie via H3-indexering

Om stabiliteit te garanderen tegen administratieve herlabeling van identificatoren, stelt de auteur een extractiemethode voor met behulp van het H3 hiërarchische geospatiale indexeringssysteem (Uber Technologies, 2018).

• Routepatroon Sleutel: In plaats van shape_id of stop_id te gebruiken, zet de methode de geordende sequentie van haltecoördinaten om in een sequentie van H3-cellen (Resolutie 15). Deze sequentie dient als een deterministische, stabiele sleutel voor het Routepatroon.
• Extractie Algoritme:
  1. Breid GTFS kalender- en uitzonderingstabellen uit om een lijst van actieve ritten voor elke datum te genereren.
  2. Converteer voor elke actieve rit de haltevolgorde naar een H3-gebaseerde Routepatroon-sleutel.
  3. Vorm een rit-specificatie tuple: $(H3\_key, first\_departure, last\_arrival)$.
  4. Groepeer data die exact dezelfde set rit-specificatie tuples delen in één enkele DayType.
• Invariantie: Deze aanpak zorgt ervoor dat als twee GTFS-feeds dezelfde fysieke dienst beschrijven maar verschillende administratieve ID's gebruiken, de geëxtraheerde DayType-partitie identiek blijft, mits de haltecoördinaten en de volgorde ongewijzigd blijven.

2.3. Schema Vergelijkingskader

Het artikel introduceert een drielaagse hiërarchie van metrieken om DayTypes $A$ en $B$ te vergelijken:

1. Exacte Metrieken ($d_0$):

   • Maakt gebruik van de Jaccard-afstand op de set van rit-specificaties.
     *ed Behandelt elke afwijking in Routepatroon, vertrektijd of aankomsttijd als een afzonderlijke DayType.
   • Dient als een strikt auditsignaal voor datakwaliteit en intentionele tijdsaanpassingen.

2. Tijd-tolerante Metrieken ($d_\epsilon$):

   • Introduceert een tolerantieparameter $\epsilon$ (bijv. 1, 3 of 5 minuten).
   • Twee ritten zijn $\epsilon$-equivalent als ze dezelfde Routepatroon-sleutel delen en hun vertrek-/aankomsttijden verschillen met $\le \epsilon$.
   • Berekent de tijd-tolerante Jaccard-afstand op basis van het maximale aantal $\epsilon$-equivalente paren.
   • Dit niveau bepaalt of exacte verschillen louter kleine tijdsverschuivingen zijn.

3. Diagnostiek van Structurele Vergelijkbaarheid:

   • Om te voorkomen dat kleine overeenkomsten overmatig worden geïnterpreteerd als volledige schema-overeenkomsten, berekent het kader:
     • Gematched Aandeel ($M_\epsilon$): De proportie ritten die onder tolerantie gekoppeld kunnen worden.
     • Rit-aantal Onbalans ($Q$): Het relatieve verschil in het totaal aantal ritten tussen de twee DayTypes.
     • Niet-gematchte Aantal ($U_\epsilon$): Het aantal ritten dat niet gekoppeld kan worden.
   • Dit maakt onderscheid tussen een "tijdsverschuiving van hetzelfde schema" (hoge $M_\epsilon$, lage $Q$) en een "structurele dienstverandering" (lage $M_\epsilon$, hoge $Q$).

3. Belangrijkste Bijdragen

1. Formalisering: Definieert Routepatronen en DayTypes als recurrente aanbodobjecten, onderscheiden van interne voertuig- of personeelsplanning.
2. Stabiele Extractie: Ontwikkelt een GTFS-extractieprocedure met behulp van H3-routepatroon-sleutels die invariant is voor administratieve identifier-relabeling, wat een cruciaal probleem oplost voor de reproduceerbaarheid van longitudinale GTFS-analyses.
3. Vergelijkingshiërarchie: Stelt een metrieksysteem voor dat strikte audit (exact), tijdsgevoeligheid (tijd-tolerant) en structurele verandering (diagnostiek) scheidt, waarmee de beperkingen van het gebruik van een enkele gelijkenis-metriek worden aangepakt.
4. Downstream Nut: Biedt compacte, recurrente sets van schema's die als input kunnen dienen voor timetable-synchronisatie, voertuigplanning, vraagtoewijzing en mismatch-diagnosemodellen.
5. Empirische Validatie: Valideert het kader op GTFS-feeds van Japanse en Canadese vervoersbedrijven, waarbij succesvolle extractie over verschillende netwerkmaten en kalenderencoderingstrategieën wordt aangetoond.

4. Resultaten en Bevindingen

Het kader werd toegepast op 40 Japanse en 38 Canadese vervoersbedrijven.

• Extractie Succes: Het algoritme identificeerde succesvol recurrente DayTypes voor alle vervoersbedrijven zonder handmatige interventie, waarbij standaard wekelijkse cycli (werkdag/zaterdag/zondag), feestdag-uitzonderingen en enkelvoudige dag-anomalieën werden teruggevonden.
• DayType Aantallen: Het mediaan aantal niet-lege DayTypes per vervoersbedrijf was 4 in beide landen. Echter, Japanse vervoersbedrijven vertoonden een hogere variabiliteit (maximaal 39) vergeleken met Canadese vervoersbedrijven (maximaal 17), wat de fijnmazigere feestdag/seizoensgebonden kalenders in de Japanse steekproef weerspiegelt.
• Disjointheid Analyse:
  • Exacte Disjointheid: Een aanzienlijk deel van de vervoersbedrijven had DayType-paren met nul gedeelde ritten (Jaccard-afstand = 1.0). Dit kwam vaker voor bij Canadese bedrijven (36%) dan bij Japanse (15%).
  • Impact van Tolerantie: Wanneer een tijd-tolerantie (1–5 minuten) werd toegepast, verkregen veel "exacte disjointe" paren in Canada enkele gematchte ritten, wat suggereert dat zij tijdsvariaties waren van vergelijkbare structuren. In Japan was exacte disjointheid persistenter, wat wijst op een sterkere structurele scheiding tussen dienstregelingen.
  • Structurele Realiteit: Ondanks het verkrijgen van matches onder tolerantie, bleef het mediaan gematchte aandeel laag (6,3% in Canada, 0% in Japan) met hoge rit-aantal onbalansen. Dit bevestigt dat veel "disjuncte" DayTypes fundamenteel verschillende dienstvolumes of route-sets vertegenwoordigen, en niet slechts verschoven schema's zijn.
• Nesting: Volledige nesting (waarbij één DayType een strikte deelverzameling is van een andere) werd waargenomen in 69% van de Japanse en 58% van de Canadese vervoersbedrijven, wat aangeeft dat een geleidelijke reductie van de dienstverlening een gangbare praktijk is in beide regio's.

5. Betekenis en Claims

Het artikel positioneert zijn bijdrage als een methodologische representatielaag in plaats van een nieuw optimalisatiealgoritme. De betekenis ligt in:

• Overbruggen van de Kloof: Het verbindt ruwe, gefragmenteerde GTFS-data met de recurrente aanbodobjecten die vereist zijn door downstream methodologische modellen (bijv. deficit-function analyse, voertuigplanning).
• Stabiliteit: Door de identificatie van de dienstverlening los te koppelen van administratieve ID's, maakt het een betrouwbare longitudinale analyse van de evolutie van schema's mogelijk over verschillende feed-releases heen.
• Genuanceerde Interpretatie: De voorgestelde metriek-hiërarchie voorkomt de misclassificatie van kleine tijdsruis als structurele dienstveranderingen, terwijl het nog steeds in staat is om exacte schema-afwijkingen te auditeren.
• Compacte Representatie: Het transformeert grote, datum-specifieke timetables naar een compacte bibliotheek van recurrente DayTypes, wat efficiëntere voertuigplanning, vraagtoewijzing en mismatch-analyse faciliteert.

De auteurs concluderen dat hoewel GTFS DayTypes niet expliciet definieert, deze impliciet gecodeerd zijn en robuust geëxtraheerd en vergeleken kunnen worden met behulp van dit kader, wat een noodzakelijke basis biedt voor geavanceerde transitplanning en -analyse.