Skip to content

Active Trip Suggestions

Real-time passenger recommendation engine that surfaces currently active bus trips serving an origin → destination corridor, including single-transfer options. The most complex algorithm in syncc.

Where It Is Used

apps/api-server/src/trips/trips.service.ts — getActiveSuggestions()

Called when a passenger opens the "Find a Bus" screen with their current location and a destination.

Overview

The algorithm runs in two sequential stages:

  1. Direct suggestions — trips the passenger can board and ride directly to their destination.
  2. Transfer suggestions — pairs of trips where the passenger rides legA, transfers on foot to legB, and continues to the destination.

Stage 1: Direct Suggestions

Input

  • originLat, originLng — passenger's current GPS position
  • destLat, destLng — destination
  • walkRadiusMeters — maximum walk distance to board or alight (default: 600 m)

Steps

  1. Load active trips — fetch all ACTIVE trips with their routes, checkpoints, and driver info in a single query.

  2. Batch-fetch last GPS positions — one query using DISTINCT ON (vehicleId) ordered by timestamp descending: sql SELECT DISTINCT ON ("vehicleId") "vehicleId", lat, lng, "createdAt" FROM "VehicleLocationLog" ORDER BY "vehicleId", "createdAt" DESC Results are stored in a Map<vehicleId, {lat, lng}> for O(1) lookup.

  3. For each active trip: a. Get the set of already-cleared checkpoint IDs from trip.actualCheckpoints. b. From remaining (not-yet-cleared) checkpoints, find the one closest to the origin within walkRadius — this is the candidate boarding stop. c. Among remaining checkpoints after the boarding stop in sequence, find the one closest to the destination within walkRadius — the alighting stop. d. If either is missing, skip this trip. e. Calculate ETA to boarding: $$\text{ETA}{\text{board}} = \frac{\text{Haversine}(\text{busPos}, C{\text{board}})}{200\ \text{m/min}}$$ f. Record the match.

  4. Sort by: ETA ascending (soonest bus first), then boardDist + alightDist ascending (shortest walk second).

Stage 2: Transfer Suggestions

Finds routes where the passenger can walk between two bus routes at an intermediate point.

Transfer Radius

350 m — maximum walk distance between the alighting point of legA and the boarding point of legB. Chosen as a comfortable urban transfer distance (~4 min walk).

Steps

  1. Collect all (trip, boardingStop) pairs from Stage 1 as legA candidates.

  2. For each legA trip:

  3. Identify remaining checkpoints (not yet passed by the bus).

  4. For each other active trip (legB):

    • For each remaining checkpoint of legA, check if any checkpoint of legB is within 350 m: $$\text{Haversine}(C_{\text{legA},i},\, C_{\text{legB},j}) \le 350\ \text{m}$$
    • The first such pair is the transfer point.
    • From legB's transfer checkpoint onwards, find the closest checkpoint to the destination within walkRadius — the final alighting stop.
    • If found, record the transfer match (legA, transferPointA, legB, transferPointB, finalAlight).

  5. Deduplicate using a Set<string> keyed by ${tripA.id}:${tripB.id} — prevents the same pair appearing multiple times from different transfer points.

  6. Sort by total journey time estimate.

Data Structures

// Already-cleared checkpoints (from Trip.actualCheckpoints JSON column)
const passedIds = new Set(trip.actualCheckpoints as string[]);

// Vehicle positions (batched, O(1) lookup)
const posMap = new Map<number, { lat: number; lng: number }>();

// Transfer deduplication
const seenPairs = new Set<string>();

Speed Constants

Movement Speed Basis
Bus (in service) 200 m/min (12 km/h) Typical Bolivian urban congestion
Pedestrian (walk) 80 m/min (4.8 km/h) Average pedestrian pace

Complexity

  • Stage 1: $O(T \times C)$ — trips × checkpoints per trip
  • Stage 2: $O(T^2 \times C^2)$ — worst case; in practice bounded by early break on first transfer match

The batch GPS query is the key performance optimization — without it, each trip would require a separate database round-trip.