A trip planner that only understands road geometry cannot answer “which bus do I need to catch at 08:12 to make a 09:00 meeting downtown” — that question depends on when a vehicle is at a stop, not just where the stop sits in space. Answering it requires a graph indexed by time as well as location, built directly from a transit agency’s published schedule. This page implements that time-expanded graph from a raw GTFS feed’s stops.txt, trips.txt, and stop_times.txt files, and is the foundational parsing step behind GTFS multi-modal trip-planning automation, itself part of the broader Routing API Automation & Fleet Integration set of workflows for automating fleet and transit routing pipelines.

Most routing engines treat a road network as static: an edge’s cost is roughly constant regardless of when you traverse it. Transit schedules break that assumption completely — a given stop-to-stop hop is only traversable at specific departure times, and missing a departure by one second means waiting for the next trip, or the next day. Encoding that correctly, at the scale of a metro feed with hundreds of thousands of stop_times rows, means building the graph with vectorized pandas operations rather than iterating row by row in Python.

Time-expanded GTFS graph with connection scan Three horizontal stop lines for Stop A, Stop B, and Stop C are plotted against a left-to-right time axis. Circles mark individual stop-time nodes. Diagonal lines connect consecutive stop-times within the same trip, representing in-vehicle connection edges. A dashed horizontal segment at Stop B represents a transfer wait edge between alighting one trip and boarding another. The bold path traces the earliest-arrival route found by a connection scan; a dimmer parallel trip shows a later, non-optimal alternative. Stop A Stop B Stop C dep 08:12 arr 08:31 dep 08:34 arr 08:47 later trip, dep 08:40 arr 09:22 bold = earliest-arrival path via connection scan • dashed = transfer wait at Stop B • dim = later alternative trip

When to Use This Approach

Build a time-expanded graph directly from GTFS stop_times when the query is schedule-sensitive — “when will I arrive,” “which specific trip should I board,” “how many transfers does this itinerary need.” It is the wrong tool when you only need topological transit connectivity (which stops are served by which routes, ignoring timing), or when the feed’s frequencies.txt defines headway-based service rather than exact stop_times — that case needs the trips expanded into synthetic stop_times first.

Use a time-expanded connection graph when:

  • You need earliest-arrival or latest-departure answers tied to a real departure time, not just reachability
  • The feed publishes exact stop_times (most fixed-route bus and rail agencies)
  • You’re fusing transit legs with walking or cycling legs from the OSM network, where access and egress times must line up with actual departures
  • You need to reconstruct a specific itinerary — boarded trip, alighting stop, transfer stop — not just a travel-time estimate

Reach for a different model when:

  • The feed is headway-based only (frequencies.txt with no matching stop_times beyond a template trip) — expand headways into discrete departures before building connections
  • You need static, schedule-independent connectivity for network-design analysis rather than passenger-facing routing
  • Real-time GTFS-RT delay feeds are in play — the static connection graph is the baseline layer; delays require re-scoring connections at query time, not rebuilding the graph

Implementation

The snippet below covers the parsing and graph-construction layer only — the outer request/response wiring for a trip-planning endpoint lives in the GTFS multi-modal trip-planning automation overview and isn’t repeated here.

# requires: pandas (pip install pandas)
# Python 3.9+  |  pandas >= 1.5

import os
import pandas as pd


def gtfs_time_to_seconds(series: pd.Series) -> pd.Series:
    """Vectorized HH:MM:SS -> seconds-since-midnight. Handles GTFS values >= 24:00:00."""
    parts = series.str.split(":", expand=True).astype("int32")
    return parts[0] * 3600 + parts[1] * 60 + parts[2]


def parse_gtfs(feed_dir: str) -> dict[str, pd.DataFrame]:
    """Load the tables needed for a time-expanded graph, with compact dtypes."""
    cat = {"stop_id": "category", "trip_id": "category",
           "route_id": "category", "service_id": "category"}
    stops = pd.read_csv(os.path.join(feed_dir, "stops.txt"), dtype=cat)
    trips = pd.read_csv(os.path.join(feed_dir, "trips.txt"), dtype=cat)
    stop_times = pd.read_csv(os.path.join(feed_dir, "stop_times.txt"), dtype=cat)
    calendar = pd.read_csv(os.path.join(feed_dir, "calendar.txt"),
                            dtype={"service_id": "category"})

    cal_dates_path = os.path.join(feed_dir, "calendar_dates.txt")
    calendar_dates = (
        pd.read_csv(cal_dates_path, dtype={"service_id": "category"})
        if os.path.exists(cal_dates_path)
        else pd.DataFrame(columns=["service_id", "date", "exception_type"])
    )

    stop_times["arrival_sec"] = gtfs_time_to_seconds(stop_times["arrival_time"])
    stop_times["departure_sec"] = gtfs_time_to_seconds(stop_times["departure_time"])
    return {"stops": stops, "trips": trips, "stop_times": stop_times,
            "calendar": calendar, "calendar_dates": calendar_dates}


def active_service_ids(calendar: pd.DataFrame, calendar_dates: pd.DataFrame,
                        service_date: str) -> set:
    """Resolve which service_id values run on a given calendar date."""
    ts = pd.Timestamp(service_date)
    dow = ts.day_name().lower()
    date_int = int(ts.strftime("%Y%m%d"))

    base = calendar.loc[
        (calendar["start_date"].astype(int) <= date_int)
        & (calendar["end_date"].astype(int) >= date_int)
        & (calendar[dow] == 1),
        "service_id",
    ]
    exceptions = calendar_dates[calendar_dates["date"].astype(int) == date_int]
    added = exceptions.loc[exceptions["exception_type"] == 1, "service_id"]
    removed = exceptions.loc[exceptions["exception_type"] == 2, "service_id"]
    return (set(base) | set(added)) - set(removed)


def build_connections(stop_times: pd.DataFrame, trips: pd.DataFrame,
                       active_services: set) -> pd.DataFrame:
    """Vectorized construction of connection edges: consecutive stop_times per trip."""
    active_trip_ids = trips.loc[trips["service_id"].isin(active_services), "trip_id"]
    st = (stop_times[stop_times["trip_id"].isin(active_trip_ids)]
          .sort_values(["trip_id", "stop_sequence"]))

    nxt = st.groupby("trip_id", observed=True).shift(-1)
    connections = pd.DataFrame({
        "trip_id": st["trip_id"],
        "from_stop": st["stop_id"],
        "dep_sec": st["departure_sec"],
        "to_stop": nxt["stop_id"],
        "arr_sec": nxt["arrival_sec"],
    }).dropna(subset=["to_stop"])

    connections["to_stop"] = connections["to_stop"].astype(st["stop_id"].dtype)
    connections["arr_sec"] = connections["arr_sec"].astype("int32")
    return connections.sort_values("dep_sec", kind="mergesort").reset_index(drop=True)

Every row in connections is one directed, time-stamped edge: board from_stop at dep_sec, alight to_stop at arr_sec, on trip_id. That table is the time-expanded graph — no explicit per-second node needs to be materialized. Querying it with a connection-scan algorithm (CSA) gives earliest-arrival answers without building an actual networkx graph object, which keeps memory bounded on feeds with millions of stop_times rows:

# requires: pandas (pip install pandas)
# Python 3.9+

import math
from collections import defaultdict


def earliest_arrival(connections: pd.DataFrame, source_stop: str,
                      start_sec: int, min_transfer_sec: int = 120):
    """Single forward pass over connections sorted by dep_sec (connection scan)."""
    earliest = defaultdict(lambda: math.inf)
    earliest[source_stop] = start_sec
    last_trip: dict[str, str] = {source_stop: None}
    came_from: dict[str, tuple] = {}

    scan = connections[connections["dep_sec"] >= start_sec]
    for c in scan.itertuples(index=False):
        ready = earliest[c.from_stop]
        if last_trip.get(c.from_stop) != c.trip_id:
            ready += min_transfer_sec  # boarding a different trip costs a transfer buffer
        if c.dep_sec >= ready and c.arr_sec < earliest[c.to_stop]:
            earliest[c.to_stop] = c.arr_sec
            last_trip[c.to_stop] = c.trip_id
            came_from[c.to_stop] = (c.from_stop, c.trip_id, c.dep_sec, c.arr_sec)

    return dict(earliest), came_from


# Example: earliest arrival from stop "1024" departing no earlier than 08:00
feed = parse_gtfs("gtfs_feed/")
services = active_service_ids(feed["calendar"], feed["calendar_dates"], "2026-07-13")
conns = build_connections(feed["stop_times"], feed["trips"], services)
arrivals, predecessors = earliest_arrival(conns, source_stop="1024", start_sec=8 * 3600)

The pre-filtering (dep_sec >= start_sec, dropna, sort_values) is fully vectorized; the scan itself is a single sequential pass, which is the correct complexity class for CSA (O(connections)) rather than a hidden O(n²). This is the same algorithmic family used by production journey planners such as MOTIS and OpenTripPlanner’s Raptor variant — a hand-rolled networkx graph with one node per (stop_id, time) pair works too, but scales far worse in both memory and construction time on metro-sized feeds.

Key Parameters and Tuning

Parameter Typical value Effect Notes
service_date "2026-07-13" Selects which service_id values are active via calendar + calendar_dates Must be the feed’s local calendar date, not a UTC-shifted date — off-by-one here silently drops all weekend service
min_transfer_sec 120–300 Buffer required between alighting one trip and boarding a different one at the same stop Override per stop pair from transfers.txt min_transfer_time where the feed provides it; large stations often need more than the default
start_sec seconds since midnight Query origin departure time Accepts values > 86400 for queries against a service day that has already rolled past midnight
stop_id / trip_id dtype category Memory and join performance Cuts stop_times memory by roughly 40% on feeds above one million rows; required for groupby().shift() to align correctly
sort key on connections dep_sec, kind="mergesort" Determines scan order Use a stable sort — an unstable sort can reorder same-timestamp connections and change which trip wins a tie during the scan
horizon_sec (optional) start_sec + 4*3600 Caps how far into the day the scan runs Filtering connections to a bounded horizon before the scan shrinks the sequential pass on large all-day feeds

Integration Points

Access and egress legs. The time-expanded graph only covers in-vehicle movement between GTFS stops. Getting a rider from an arbitrary origin to the first boarding stop — and from the last alighting stop to the final destination — is a walking or cycling problem solved on the OSM network. See implementing multi-modal transit layers for how to attach stop_id nodes onto the road graph so access-leg cost can be computed with the same Dijkstra-style search used elsewhere in the pipeline.

First/last-mile micromobility. For trip plans that include a bike-share leg instead of walking, station coordinates need to be snapped onto the routable road graph before they can act as access points into the transit search. Snapping bike-share stations to OSM nodes covers the KD-tree nearest-node search and snap-distance thresholds needed to do that safely.

Itinerary reconstruction. came_from is keyed by stop and stores (from_stop, trip_id, dep_sec, arr_sec). Walk it backward from the destination stop to the source to recover the ordered sequence of boarded trips and transfer points — this is the structure a JSON trip-plan response needs, not just a scalar travel time.

Alternative engines. If the deployment already runs Valhalla for road and cycling routing, its multimodal costing model can ingest a GTFS feed directly and perform an equivalent time-expanded search inside the engine rather than in application code — see Valhalla configuration for multi-modal analysis for the tile-building and costing setup. The pandas approach here is preferable when you need full control over transfer rules, fare rules, or custom scoring that Valhalla’s costing model doesn’t expose.

Validation Checklist

  1. Connection row count. len(connections) should equal len(active_stop_times) - active_trip_ids.nunique() — every trip loses exactly one row (its terminal stop) when building connections. A larger gap usually means a stop_id or trip_id dtype mismatch broke the join.
  2. Non-negative travel time. Assert (connections["arr_sec"] >= connections["dep_sec"]).all(). A violation almost always traces back to incorrect midnight-rollover handling in gtfs_time_to_seconds.
  3. Service-day spot check. Compare active_service_ids() output against the agency’s published weekday/weekend service pattern for a known date, including at least one holiday present in calendar_dates.txt, to confirm exceptions are applied in the right direction.
  4. Monotonic itinerary. Walking the came_from chain from any reachable stop back to the source should show strictly non-decreasing dep_sec/arr_sec values at each hop — a decrease indicates the scan processed connections out of order.
  5. Overnight trips parse correctly. For feeds with late-night service, confirm stop_times["departure_sec"].max() > 86400 for at least one trip, and that such trips still connect correctly to next-day service without being clipped.
  6. Determinism. Re-running earliest_arrival() with identical inputs must return identical arrivals and came_from — no reliance on Python’s dict iteration order or unstable sorts creeping into the scan.
How do I handle trips that run past midnight in GTFS stop_times?

GTFS explicitly allows arrival_time/departure_time values past 24:00:00 for trips that start one service day and continue into the next. Keep these as plain seconds-since-midnight without wrapping modulo 86400 — a departure of 25:10:00 becomes 90600, not 3:10 AM. Only convert back to a wall-clock display format at render time; never wrap the underlying value used in comparisons inside the connection scan.

Why does my earliest-arrival scan return a slower path than expected?

Two causes account for most of these bugs. First, an unsorted or unstably sorted connections table — the scan requires strictly ascending dep_sec order to be correct. Second, applying the transfer buffer to every boarding, including staying on the same vehicle through a stop, which unfairly penalizes through-running trips. Track the trip_id that reached each stop and only add min_transfer_sec when the next connection’s trip_id differs from it.

My connections DataFrame has far fewer rows than expected — what's wrong?

This is usually correct, not a bug: grouping by trip_id and shifting by -1 intentionally drops the terminal stop_time of every trip, since a trip’s last stop has no outgoing connection. Row count should equal the original stop_times row count minus one row per distinct trip_id. If the gap is larger than that, check for a dtype mismatch between stop_id columns — pandas categorical columns built from different category sets can fail to align silently during the merge.