⚡ electrical engineering

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

This paper introduces a method to identify and formalize recurring public transit schedules as "DayTypes" from GTFS data using H3 route-pattern keys and similarity metrics, enabling more efficient timetable synchronization, vehicle scheduling, and demand assignment by distinguishing between minor timing shifts and significant service changes.

Original authors: Evgeny Makarov, Georgy Taubkin

Published 2026-06-16

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Evgeny Makarov, Georgy Taubkin

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine public transit schedules as a massive, chaotic library of bus and train timetables. If you look at a calendar, you might think every single day has a unique schedule. But in reality, most days are just copies of each other. Mondays look like other Mondays; Saturdays look like other Saturdays. Holidays, however, are the "special editions" that break the pattern.

The problem is that the standard digital format used to share these schedules (called GTFS) doesn't organize them this way. It lists every single trip for every single day as if they were all unique, making it hard for computers to see the repeating patterns. It's like having a recipe book where "Monday's Soup" and "Tuesday's Soup" are listed as completely different recipes, even though they are identical, just because the page numbers are different.

This paper introduces a way to clean up that library and group these schedules into logical "families."

The Core Idea: "DayTypes"

The authors call these families DayTypes. Think of a DayType as a "template" or a "mold."

The Template: Instead of looking at 365 different days, the system finds that 52 of them are "Monday Templates," 52 are "Saturday Templates," and maybe 5 are "New Year's Day Templates."
The Goal: By grouping days this way, planners can stop treating every day as a unique puzzle. They can see the big picture: "Oh, this agency runs a 'Weekday' mold, a 'Weekend' mold, and a 'Holiday' mold."

The Problem with "Names" vs. "Reality"

The paper highlights a tricky problem with how transit data is currently stored. It relies on administrative IDs (like shape_id or stop_id) which are like internal library catalog numbers.

The Analogy: Imagine a bus route that goes from Point A to Point B. One day, the transit agency changes the internal catalog number for that route from "Route-123" to "Route-456," even though the bus still stops at the exact same places in the exact same order.
The Old Way: A computer would think "Route-123" and "Route-456" are two completely different buses. It would think the schedule changed, even though the passenger experience didn't.
The New Way (H3 Keys): The authors use a clever trick called H3 indexing. Instead of trusting the internal catalog numbers, they look at the actual physical map. They turn every bus stop into a tiny, unique digital tile on a map (like a pixel). If the bus stops at the same tiles in the same order, the system knows it's the same route, regardless of what the agency called it internally. This makes the system "immune" to administrative name changes.

The "Tolerance" Test: Is it a Change or Just a Shift?

Once the system groups the days, it needs to compare them. The authors created a three-step "ruler" to measure how different two schedules are:

The Exact Ruler (The Audit): This checks if the schedules are identical down to the second. If a bus leaves at 8:00:00 on Monday and 8:00:01 on Tuesday, this ruler says, "These are different!" This is useful for catching data errors or intentional tiny tweaks.
The Flexible Ruler (Time-Tolerant): This is the "everyday" ruler. It asks, "If we allow for a small delay (say, 3 minutes), are these schedules basically the same?" If the bus leaves at 8:00 on Monday and 8:02 on Tuesday, this ruler says, "Close enough! They are the same schedule, just shifted slightly."
The Structural Ruler: This checks if the structure is different. If Monday has 10 buses and Tuesday has only 2, or if Tuesday skips a whole stop, the ruler says, "These are totally different schedules," even if the few buses that do run are close in time.

What They Found

The authors tested this system on real data from Japan and Canada.

The Results: They successfully stripped away the clutter and found the hidden patterns. For example, in one Canadian city, they found a clean cycle of just three DayTypes: Weekdays, Saturdays, and Sundays. In a Japanese city, they found a "New Year" DayType that was completely different from everything else.
The Surprise: They discovered that in Canada, many schedules that looked "completely different" on paper (because the times didn't match exactly) were actually just the same schedule with small time shifts. However, in Japan, some schedules that looked different were truly structurally different (different routes or stops), not just time shifts.

Why This Matters

This paper doesn't invent a new way to run buses or predict traffic. Instead, it builds a better translation layer.

It takes messy, raw data and turns it into clean, recognizable "DayTypes."
It allows computers to stop getting confused by name changes or tiny time differences.
It gives planners a clear, compact list of "schedule templates" to work with, making it easier to compare different cities, check for errors, or plan for the future.

In short, the paper provides a smart, stable way to organize the chaos of public transit schedules, turning a mountain of daily data into a manageable set of repeating patterns.

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

1. Problem Statement

Public transit schedules exhibit recurring service structures where multiple calendar dates share identical passenger-facing timetables (e.g., standard weekdays), while others differ due to weekends, holidays, or special events. However, the General Transit Feed Specification (GTFS), the global standard for transit data, does not explicitly encode these recurring "DayTypes." Instead, GTFS represents service through interdependent tables (calendar, trips, stop_times, shapes), forcing downstream models for scheduling, vehicle assignment, and demand analysis to reconstruct recurring supply objects from fragmented data.

The core challenge is twofold:

Identification: How to extract stable, recurring service classes (DayTypes) from GTFS without relying on administrative identifiers (e.g., shape_id, stop_id) that may change between feed releases despite the physical service remaining constant.
Comparison: How to compare these extracted schedules to distinguish between strict timetable differences, minor timing shifts (e.g., a 1-minute delay), and substantive structural changes (e.g., route removal or addition).

2. Methodology

2.1. Formal Definitions

The paper formalizes two key concepts:

Route Pattern: A passenger-facing service variant defined by an ordered stop sequence and travel direction. Unlike GTFS shape_id, which is an administrative identifier, a Route Pattern is defined by the physical path and stop order.
DayType: A category of dates sharing the exact same set of Route Pattern trips operating at the same times. It is defined strictly as the set of trip specifications: $DayType(d) = \{(p, dep_t, arr_t)\}$ , where $p$ is the Route Pattern, and $dep_t/arr_t$ are the first departure and last arrival times.

2.2. Stable Extraction via H3 Indexing

To ensure stability against administrative identifier relabeling, the authors propose an extraction method using the H3 hierarchical geospatial indexing system (Uber Technologies, 2018).

Route Pattern Key: Instead of using shape_id or stop_id, the method converts the ordered sequence of stop coordinates into a sequence of H3 cells (Resolution 15). This sequence serves as a deterministic, stable key for the Route Pattern.
Extraction Algorithm:
1. Expand GTFS calendar and exception tables to generate a list of active trips for every date.
2. For each active trip, convert its stop sequence into an H3-based Route Pattern key.
3. Form a trip specification tuple: $(H3\_key, first\_departure, last\_arrival)$ .
4. Group dates that share the exact same set of trip specification tuples into a single DayType.
Invariance: This approach ensures that if two GTFS feeds describe the same physical service but use different administrative IDs, the extracted DayType partition remains identical, provided stop coordinates and order are unchanged.

2.3. Schedule Comparison Framework

The paper introduces a three-tiered hierarchy of metrics to compare DayTypes $A$ and $B$ :

Exact Metrics ( $d_0$ ):
- Uses the Jaccard Distance on the set of trip specifications.
- Treats any difference in Route Pattern, departure time, or arrival time as a distinct DayType.
- Serves as a strict audit signal for data quality and intentional timing adjustments.
Time-Tolerant Metrics ( $d_\epsilon$ ):
- Introduces a tolerance parameter $\epsilon$ (e.g., 1, 3, or 5 minutes).
- Two trips are $\epsilon$ -equivalent if they share the same Route Pattern key and their departure/arrival times differ by $\le \epsilon$ .
- Calculates a time-tolerant Jaccard distance based on the maximum number of $\epsilon$ -equivalent pairs.
- This layer determines if exact differences are merely small timing shifts.
Structural Comparability Diagnostics:
- To prevent over-interpreting small matches as whole-schedule similarities, the framework computes:
  - Matched Share ( $M_\epsilon$ ): The proportion of trips that can be paired under tolerance.
  - Trip-Count Imbalance ( $Q$ ): The relative difference in the total number of trips between the two DayTypes.
  - Unmatched Count ( $U_\epsilon$ ): The number of trips that cannot be paired.
- This distinguishes between a "timing-shifted version of the same schedule" (high $M_\epsilon$ , low $Q$ ) and a "structural service change" (low $M_\epsilon$ , high $Q$ ).

3. Key Contributions

Formalization: Defines Route Patterns and DayTypes as recurring supply objects, distinct from internal vehicle or crew scheduling.
Stable Extraction: Develops a GTFS extraction procedure using H3 route-pattern keys that is invariant to administrative identifier relabeling, solving a critical reproducibility issue in longitudinal GTFS analysis.
Comparison Hierarchy: Proposes a metric system that separates strict audit (exact), timing sensitivity (time-tolerant), and structural change (diagnostics), addressing the limitations of using a single similarity metric.
Downstream Utility: Provides compact, recurring schedule sets that can serve as inputs for timetable synchronization, vehicle scheduling, demand assignment, and mismatch diagnosis models.
Empirical Validation: Validates the framework on GTFS feeds from Japan and Canada, demonstrating successful extraction across different network scales and calendar encoding strategies.

4. Results and Findings

The framework was applied to 40 Japanese and 38 Canadian transit agencies.

Extraction Success: The algorithm successfully identified recurring DayTypes for all agencies without manual intervention, recovering standard weekly cycles (weekday/Saturday/Sunday), holiday exceptions, and single-day anomalies.
DayType Counts: The median number of non-empty DayTypes per agency was 4 in both countries. However, Japanese agencies showed higher variability (max 39) compared to Canadian agencies (max 17), reflecting more granular holiday/seasonal calendars in the Japanese sample.
Disjointness Analysis:
- Exact Disjointness: A significant portion of agencies had DayType pairs with zero shared trips (Jaccard distance = 1.0). This was more common in Canada (36% of agencies) than Japan (15%).
- Tolerance Impact: When applying time tolerance (1–5 minutes), many "exactly disjoint" pairs in Canada acquired some matching trips, suggesting they were timing variations of similar structures. In Japan, exact disjointness was more persistent, indicating stronger structural separation between service regimes.
- Structural Reality: Despite acquiring matches under tolerance, the median matched share remained low (6.3% in Canada, 0% in Japan) with high trip-count imbalances. This confirms that many "disjoint" DayTypes represent fundamentally different service volumes or route sets, not just shifted schedules.
Nesting: Full nesting (where one DayType is a strict subset of another) was observed in 69% of Japanese agencies and 58% of Canadian agencies, indicating that graduated service reduction is a common practice in both regions.

5. Significance and Claims

The paper positions its contribution as a methodological representation layer rather than a new optimization algorithm. Its significance lies in:

Bridging the Gap: It connects raw, fragmented GTFS data to the recurring supply objects required by downstream methodological models (e.g., deficit-function analysis, vehicle scheduling).
Stability: By decoupling service identification from administrative IDs, it enables reliable longitudinal analysis of schedule evolution across feed releases.
Nuanced Interpretation: The proposed metric hierarchy prevents the misclassification of minor timing noise as structural service changes, while still preserving the ability to audit exact schedule deviations.
Compact Representation: It transforms large, date-specific timetables into a compact library of recurring DayTypes, facilitating more efficient scheduling, demand assignment, and mismatch analysis.

The authors conclude that while GTFS does not explicitly define DayTypes, they are implicitly encoded and can be robustly extracted and compared using this framework, providing a necessary foundation for advanced transit planning and analysis.