← Back
Home › Systems › Transport, logistics and mobility

transit-planner

Turns published timetables and live vehicle feeds into door-to-door journeys that trade arrival time against transfers and walking, for travellers and apps.

GTFS, RAPTOR

Open the transit-planner pagetransit-planner Geodesic distance (haversine,Vincenty, Karney)geometry: Shortest-path distance between two lat/lon points on the Earth: haversine on a sphere (about 0.5% error), Vincenty or Karney on the WGS84 ellipsoid (sub-millimetre).›R-treegeometry: A balanced tree of nested bounding boxes that indexes rectangles and points, answering window and nearest-neighbour queries by pruning whole subtrees.›Connection scan algorithmgraphs: Earliest-arrival transit routing by scanning departure-sorted connections onceContraction hierarchies(shortcut-based shortest paths)graphs: Rank the nodes, remove them one by one while adding shortcut edges that keep distances intact, then answer queries with two tiny searches that only climb the ranking.›Dijkstra's algorithmgraphs: Single-source shortest paths with non-negative edge weights by settling vertices in order of distance with a priority queue.›Raptor transit routinggraphs: Round-based public transit / schedule routing (RAPTOR) with Pareto setsTime dependent shortest pathgraphs: Shortest paths where edge costs depend on departure time (FIFO property, timetable graphs)Protobuf wire formatnetworking: Protocol Buffers wire format: tags, varints, length-delimited fields and schema evolutionFuzzy string matchingsearch-sort: Edit distance, Jaro-Winkler and trigram indexes for approximate name and address matchingRadix sortsearch-sort: Non-comparison sort that distributes keys by 8-bit digits; several times faster than comparison sorts on large arrays of integers, floats or fixed-size keys.›Inverted indexstorage: Map each term to a sorted, compressed list of the documents containing it; the core of full-text search and other fast set queries.›W-TinyLFUsystems: An LRU window plus segmented LRU, guarded by a 4-bit Count-Min sketch that admits a newcomer only if it beats the victim's frequency.›Newton root findingnumerics: Linearize at the guess and jump to the tangent root; quadratic convergence near a simple root, made robust by brackets (1D) or line search.›d-ary heapdata-structures: Array heap with d children per node (d = 4 typical): half the binary heap's depth, siblings in one cache line, faster priority queues.›BFS and DFSgraphs: The two basic graph traversals; BFS gives hop distances and levels, DFS gives discovery/finish order for cycles, components and topological order.›Calendar date arithmeticsystems: Civil dates, time zones (tzdb), DST gaps, month-end anchoring and duration mathBit packing and PFORcompression: Store blocks of integers with exactly b bits each and patch rare outliers separately (PFOR); the fastest integer codec family, billions of values per second.›Delta encodingcompression: Store differences between consecutive values instead of the values, turning sorted IDs, timestamps and counters into small numbers that pack into few bits.›Varint (LEB128)compression: Variable-length integers in 7-bit groups with a continuation bit; small numbers take 1 byte, the wire format of Protobuf, WebAssembly and DWARF.›BM25 rankingsearch-sort: The standard lexical relevance score: IDF-weighted term frequency with saturation (k1) and length normalization (b); default in Lucene, Elasticsearch and SQLite FTS5.›Sorted-list intersectionsearch-sort: Intersect sorted id lists by merging, galloping from the short list into the long one, and skipping whole compressed blocks, shortest list first.›LU and Cholesky factorizationnumerics: Factor A = PLU (any square matrix, partial pivoting) or A = LLᵀ (SPD) once in O(n³), then solve each right-hand side in O(n²).›Sparse matrices (CSR)numerics: Compressed sparse row stores only nonzeros as row pointers, column indices and values; SpMV streams them once, so it is memory-bandwidth bound.›SIMD programminghardware-os: Process 4-16 lanes per instruction with AVX2, AVX-512 or NEON via Rust std::arch, with runtime dispatch and a portable fallback.›Top-k selectionsearch-sort: Keep the k best of n items without sorting all n - bounded min-heap for streams, quickselect for arrays, threshold pruning to skip most items.›Unicode text tokenization forsearchsearch-sort: Turn multilingual text into index terms: segment words (UAX 29 style, CJK bigrams), normalize, case-fold and accent-fold, identically at index and query time.›Text normalizationmachine-learning: Rewrite messy text into one canonical form for matchers and models, or into spoken words for speech output (and back), keeping a map to the original offsets.›

How it is built

Architecture overview

A transit trip planner answers "how do I get from here to there, leaving at 08:15?" using buses, trams, metros and trains plus walking. Its data comes in two kinds: a static timetable published by each agency as a GTFS feed (stops, routes, trips, stop times, calendars, transfers), and a realtime feed in GTFS Realtime (trip updates, vehicle positions, service alerts) that says what is actually happening now. A street network supplies the walking (and cycling) legs at both ends and between stops. The planner compiles these inputs into an in-memory timetable, finds the journeys, and returns itineraries.

The one idea that makes it work is that transit is not an ordinary road graph. An edge exists only when a vehicle leaves, so the cost of a link depends on the time you arrive at it, and the best answer is usually not one journey but a set: the earliest arrival, the one with fewer transfers, the one with less walking. Planners therefore skip general shortest-path search for the transit part and scan the timetable directly, either route by route in rounds (one round per transfer) or connection by connection in departure order. Road-style speedups such as contraction hierarchies apply to the walking part only. Realtime delays are applied as patches on the compiled timetable, not by rebuilding it.

Parts:

 GTFS zip (agencies) ─► validate ─► compile: routes, trips, stop_times sorted ─┐
 OSM street extract  ───────────► street graph + stop snapping (R-tree) ──────┤
                                                                               ▼
 GTFS-Realtime (protobuf) ─► realtime overlay ─► timetable snapshot (immutable, + delay patch)
                                                       │
 query: origin, destination, time ─► access legs ─► transit router (rounds / scan) ─► egress legs
                                                       │
                                          Pareto set of itineraries ─► JSON API ─► cache

How the parts fit together

Feed import and timetable

A GTFS feed is a zip of CSV files. The reference describes stops.txt (with location_type and parent_station to model stations, platforms and entrances), routes.txt, trips.txt, stop_times.txt (arrival and departure per stop_sequence), calendar.txt and calendar_dates.txt for service days, frequencies.txt for headway-based service, transfers.txt (with transfer_type and min_transfer_time) and pathways.txt for station interiors. Import joins these into a compact model. Two details matter later: a trip can run past midnight so times may exceed 24:00:00, and the same stop_id values collide across agencies, so each feed gets a namespace.

Import validates before it compiles: unsorted stop_times, trips with a single stop, missing calendars and impossible speeds are rejected or repaired with a log entry, because the router assumes clean input. Radix sort is the practical choice for ordering millions of stop-time rows by (trip, sequence) or connections by departure time, since keys are fixed-size integers. Times in a compiled trip can be stored as differences from the previous stop, which are small numbers.

The compile step produces what the router reads. For a round-based router it groups trips that share the same stop pattern into routes and sorts the trips of a route by departure, so that "the first trip I can board at stop k" is a binary search; the arrays are contiguous per route, and a stop knows the list of routes that serve it. For a scan-based router it produces one flat array of connections (departure stop, arrival stop, departure time, arrival time, trip) sorted by departure time. Both are flat arrays of integers, which fit in memory and can be written to a file and memory-mapped so a restart does not re-parse the feeds. Service calendars are resolved to a day mask or a per-day bit set at compile time, not interpreted per query.

The contract is that a compiled snapshot is immutable. Queries running against it never see a half-applied update; a new feed version or a realtime patch produces a new snapshot (or a delta layer over the old one) that is swapped in atomically.

Transit router

This is the part with the real choices. Three blocks cover it; all three have no page yet.

raptor-transit-routing (no page yet) is RAPTOR (Delling, Pajor and Werneck). Each round k computes the best arrival at every stop using at most k trips: it scans each route that touches a stop improved in the previous round, once, riding the earliest boardable trip, and then relaxes footpath transfers. The result is a Pareto set over arrival time and number of transfers, one entry per round. The paper states that it is not Dijkstra-based, looks at each route at most once per round, needs no preprocessing, and so works in fully dynamic scenarios; it extends to further criteria such as fare zones or transfer reliability. Its rounds are breadth-first in the number of trips (BFS and DFS), and its service-day logic needs calendar-date-arithmetic (no page yet): time zones, daylight-saving changes and times past 24:00.

connection-scan-algorithm (no page yet) is CSA (Dibbelt, Pajor, Strasser, Wagner). It keeps an earliest-arrival label per stop and scans the departure-sorted connection array once from the query time: a connection is usable if you can be at its departure stop by its departure time, and then it may improve its arrival stop. It is very simple, needs no graph, and the profile variant answers "all good departures in a time window".

time-dependent-shortest-path (no page yet) is the graph formulation: nodes for stops (or events), edges whose travel time depends on the departure time, and a FIFO property (leaving later never gets you there earlier). It lets you use Dijkstra's algorithm and its speedups (the priority queue is a d-ary heap), but the timetable-native algorithms avoid its cost of modelling transfers in the graph.

Which one: RAPTOR when you want several criteria and an easy realtime update (the routes are arrays; a delay shifts times in one route); CSA when you want the smallest code path for earliest arrival or profile queries and the connection array already fits. Both can be parallelised across queries; RAPTOR also within a query across routes. Both consume a source stop set (with walking times) and a target set, which is the contract with the street router.

Street router

Walking from the origin to the first stop, from the last stop to the destination, and between nearby stops makes up much of a real journey. The street graph comes from OpenStreetMap; Dijkstra's algorithm (with a d-ary heap as its queue) from the origin, limited to a maximum walking time, gives the access legs to nearby stops. For repeated queries over a large area, Contraction hierarchies answer street distances with two small searches over a preprocessed graph. A timetable-level footpath table (from transfers.txt or computed between stops within a radius) is what the transit router uses between rounds. Geodesic distance (its ellipsoidal variants iterate with Newton root finding) gives the straight-line distance used for the cheap first filter (candidate stops) and as a fallback when no street path is available. The general road-routing design is in maps and routing.

Spatial and name lookup

Finding stops near a coordinate is a window or nearest-neighbour search over a few hundred thousand points: an R-tree (or a grid) built at import time. Finding the origin from text ("Hauptbahnhof", "Main St") is a name search: an Inverted index over stop and place names (posting lists intersected with Sorted-list intersection, stored with Varint (LEB128), Delta encoding and Bit packing and PFOR, ranked by BM25 ranking), with fuzzy-string-matching (no page yet) for typos and transliterations; address-level geocoding is a separate service, see geocoder.

Realtime overlay

GTFS Realtime messages are Protocol Buffers (protobuf-wire-format, no page yet). A feed message carries entities of three kinds: TripUpdate (predicted arrival and departure per stop through StopTimeUpdate, with a ScheduleRelationship such as scheduled, skipped or no data), VehiclePosition and Alert. A feed's incrementality is either full dataset or differential, so the consumer must handle both. The overlay matches each update to a compiled trip (by trip id and start date), copies the trip's times, applies the delays, and stores the patched trip in a layer consulted before the base timetable. Cancellations and skipped stops mark the trip or stop as unusable for boarding. An added trip needs a new route entry. Propagation is the sharp edge: a delay reported at one stop must be extended forward to later stops where the feed is silent, with a documented rule, or the planner will show impossible connections.

Serving

Queries are small and bursty at commute hours. Many origins and times repeat (home stations, popular destinations), so a result cache with an admission policy such as W-TinyLFU protects the router from the hot head of the distribution; entries are keyed by snapshot version so a realtime patch invalidates them cleanly.

Data and control flow

Static load (once per feed update):

  1. Download and validate each agency's GTFS zip; namespace ids; resolve calendars to service days.
  2. Group trips into routes by stop pattern, sort trips by time, compute footpaths between stops; build the connection array if CSA is used.
  3. Build the stop R-tree and the name index, snap stops to the street graph, and write the snapshot.
  4. Swap the snapshot into the serving process; drop cache entries keyed to the old version.

A journey query:

  1. Resolve text to coordinates; find nearby stops with the R-tree; run the street search to get walking times to each (access legs), and the same at the destination (egress legs).
  2. Run the transit router from the departure time over the snapshot plus the realtime layer: round 0 starts from the access stops, each round boards the earliest trips and relaxes footpaths.
  3. Collect the arrivals at the egress stops plus egress walking time; keep the Pareto set over arrival time, transfers (and walking if asked).
  4. Reconstruct each itinerary from the stored parent pointers, attach platform and line names, and return it.

A realtime update (every few seconds to a minute, set by the agency's feed):

  1. Fetch the protobuf message; decode it; for each TripUpdate, find the compiled trip.
  2. Apply delays, skips and cancellations into the patch layer; propagate delays forward by the documented rule.
  3. Publish the new patch version; new queries use it, in-flight queries finish on the old one.

Scaling

In the order the limits appear:

  1. Query latency in a single process. The router reads flat arrays, so the first levers are layout (contiguous routes, small integer types, times as deltas) and pruning rules; stay in memory.
  2. Concurrent queries. Queries are independent and read-only on an immutable snapshot, so run them on all cores and scale out by adding identical replicas.
  3. Large areas. A country or continent multiplies stops and trips; reduce the work per query with a target-pruning bound, a limit on rounds, a bound on walking, and a time window for profile searches. Order of: more rounds than a handful of transfers rarely helps users.
  4. Street search cost. Long access legs or cycling make plain Dijkstra expensive; use contraction hierarchies or a stop-to-stop footpath table with a radius limit.
  5. Realtime volume. Many agencies mean many feeds; process feeds in parallel into separate patch shards and merge by trip id, and reject feeds with stale timestamps.
  6. Snapshot build time. Re-importing all feeds is slow, so recompile only changed feeds and reuse the compiled form of the others.

Failure modes

FailureSymptomCauseFix
Wrong service dayno trips found on holidays or weekendscalendar.txt / calendar_dates.txt exceptions not appliedresolve exceptions at compile time; test with known holidays
Times past midnightnight trips missing or on the wrong daytimes above 24:00:00 treated as invalid or wrappedkeep times as seconds since the service day's start
Impossible transferitinerary shows a 1-minute change between distant platformsmissing transfers.txt / pathway data, default transfer time too smallper-station minimum transfer times, use pathways, buffer on long station walks
Phantom delaylate vehicle shown but later stops unchangeddelay not propagated to stops the feed omitspropagation rule; mark stale predictions and expire them
Cancelled trip still offereduser is sent to a trip that does not runrealtime Canceled/skipped status ignored or trip matching failsmatch by trip id and start date; log unmatched updates and alarm on a rising rate
Duplicate stops across agenciestransfers between two agencies' stops not foundsame station modelled as separate stopsstation merge by distance and name; explicit transfer rows
Cache after updatestale routes served after a feed changecache not keyed by snapshotinclude snapshot/patch version in the key
Walking leg unrealisticroute through a motorway or private landstreet graph snap to the wrong edgesnap with direction and access tags; verify with sample walks
Router too slow on long searchestimeouts on cross-country tripsunbounded rounds, no pruninground limit, arrival-time bound from best known result, profile windows
Memory blowupprocess killed on a large regionwhole feeds held as text objectscompile to flat arrays, map the file, drop unused columns such as shapes

Real implementations

namewhat it isrepolicencenotes
OpenTripPlannermulti-modal trip planner; imports GTFS, GTFS Realtime and OpenStreetMapopentripplanner/OpenTripPlannerLGPL-3.0-or-laterJava; the repository's licence text is the GNU Lesser GPL v3 or later
MOTISmultimodal routing, geocoding and map tilesmotis-project/motisMITC++
nigiriMOTIS's timetable routing core ("Next Generation Routing")motis-project/nigiriMITC++ library
R5Conveyal's routing engine for multimodal networks, focused on public transitconveyal/r5MITbuilt for accessibility and scenario analysis
GTFS / GTFS Realtimethe data specificationsgoogle/transitApache-2.0reference protos and docs
Transitouscommunity-run, free public transit routing service——transitous.org; only what the site says

Sources