Skip to content

Route Direction Matching

Finds valid boarding → alighting stop pairs for a passenger's origin → destination journey across all syncc-registered lines and routes. The core search algorithm of the passenger route discovery feature.

Where It Is Used

apps/passengers-app/src/app/core/services/lines.service.ts — findRoutes()

Called when a passenger enters an origin and destination to find available bus routes.

Algorithm

Entry Point: findRoutes(originLat, originLng, destLat, destLng, walkRadiusMeters = 1000)

  1. Fetch all active lines with their routes and checkpoints.
  2. For each route, call matchDirection(checkpoints, origin, dest, walkRadius).
  3. Also try the checkpoints reversed to handle bidirectional routes stored in one direction only.
  4. Deduplicate results using a Set<string> keyed by ${routeId}-${boardStop.id}-${alightStop.id}.
  5. Sort all results by combined walk distance: boardDist + alightDist (ascending).

Core Matching: matchDirection(checkpoints, origin, dest, walkRadius)

Checkpoints in order: [C0, C1, C2, C3, C4, C5]
                            ↑ board          ↑ alight
                      closest to origin   closest to dest (must come AFTER board)

  1. Find the checkpoint closest to the origin (no radius cutoff — always returns the nearest one regardless of distance, then filter by walkRadius): $$C_{\text{board}} = \arg\min_{i} \text{Haversine}(C_i, \text{origin})$$

  2. Among all checkpoints after $C_{\text{board}}$ in sequence, find the one closest to the destination: $$C_{\text{alight}} = \arg\min_{i > \text{boardIndex}} \text{Haversine}(C_i, \text{destination})$$

  3. If no valid $C_{\text{alight}}$ exists (origin is past the last stop in this direction), return null for this direction.

  4. Calculate walk distances:

  5. $d_{\text{board}} = \text{Haversine}(\text{origin}, C_{\text{board}})$

  6. $d_{\text{alight}} = \text{Haversine}(\text{destination}, C_{\text{alight}})$

  7. Filter: only include the result if both $d_{\text{board}} \le \text{walkRadius}$ and $d_{\text{alight}} \le \text{walkRadius}$.

Why "After" Enforcement Matters

Without the index constraint, a passenger traveling northbound could get matched with an alighting stop that is south of their boarding stop — making the bus travel backwards. The i > boardIndex constraint enforces forward-direction travel within the route's checkpoint sequence.

Implementation Sketch

function matchDirection(
  checkpoints: Checkpoint[],
  origin: LatLng,
  dest: LatLng,
  walkRadius: number
): RouteMatch | null {
  // 1. Find nearest to origin
  let boardIdx = 0, boardDist = Infinity;
  checkpoints.forEach((c, i) => {
    const d = haversine(origin, c);
    if (d < boardDist) { boardDist = d; boardIdx = i; }
  });

  // 2. Find nearest to dest, after boardIdx
  let alightIdx = -1, alightDist = Infinity;
  for (let i = boardIdx + 1; i < checkpoints.length; i++) {
    const d = haversine(dest, checkpoints[i]);
    if (d < alightDist) { alightDist = d; alightIdx = i; }
  }

  if (alightIdx === -1) return null;
  if (boardDist > walkRadius || alightDist > walkRadius) return null;

  return {
    boardStop: checkpoints[boardIdx],
    alightStop: checkpoints[alightIdx],
    boardDist,
    alightDist,
  };
}

Complexity

$O(n \times m^2)$ where $n$ = number of routes, $m$ = checkpoints per route. Acceptable because: - Routes typically have 5–20 checkpoints. - The full route list is fetched once and filtered in-memory.