Fastest-Route Finding

1. Overview — two routing questions

Routing inside RideChain is not one problem, it is two, and conflating them is the most common mistake. The first is single-route: given one origin and one destination, what is the fastest road path, and what is the ETA? This drives navigation, partner offers, and the live arrival countdown the booker watches. The second is multi-stop: given a vehicle and a pile of parcels with different pickups and drops, what is the cheapest sequence of stops that respects capacity and time windows? That is the Vehicle Routing Problem (VRP), and it is the literal cost engine of the platform.

Both questions are answered against a road graph we host ourselves. RideChain runs a self-hosted OSRM (Open Source Routing Machine) instance on top of OpenStreetMap (OSM) rural extracts for the districts we operate in. Because the routing engine is ours, a route query costs us essentially compute only — not a per-call API fee. That ~₹0 marginal cost is what makes it economical to call routing thousands of times a day for ETAs, re-routes and VRP solves; see Scale & Low-Cost for how this folds into unit economics.

2. Routing engine architecture

The Go modular monolith exposes a geo module that is the single entry point for every routing question. Callers (matching, booking ETA, the VRP solver, the Dispatch app) never talk to OSRM directly — they call the geo module, which owns caching, fallback, map-matching and the rural weighting layer. This keeps routing policy in one place and lets us swap the backend without touching callers.

1. Caller asks the geo module — route(origin, dest, vehicleClass) or vrp(stops, vehicle, constraints).
2. Map-match the inputs — snap raw GPS coordinates to the nearest road segment so a point in a field routes from the road, not the crop.
3. Check Redis — for a corridor we have computed recently, return the cached route/ETA immediately.
4. Call self-hosted OSRM — on a cache miss, query our OSRM on the regional OSM extract; OSRM returns geometry + base travel time.
5. Apply rural weighting — adjust the raw OSRM time for surface, vehicle class, season and safety (see §4).
6. Fallback if OSRM cannot answer — if our extract has no road to a remote hamlet (or OSRM is down), fall back to a maps provider, then to straight-line + landmark anchoring.
7. Cache & return — write the result to Redis with a TTL and return route geometry + adjusted ETA to the caller.

flowchart TB
  C["Caller: matching / ETA / VRP / Dispatch"] --> GEO["Go geo module
(routing policy owner)"]
  GEO --> MM["Map-matching
snap GPS to nearest road"]
  MM --> CACHE{"Redis route/ETA
cache hit?"}
  CACHE -- "hit" --> RET["Return cached route + ETA"]
  CACHE -- "miss" --> OSRM["Self-hosted OSRM
(rural OSM extract)"]
  OSRM -- "ok" --> WGT["Apply rural weighting
(surface, vehicle, season)"]
  OSRM -- "no road / down" --> FB["Fallback chain"]
  FB --> PROV["Maps provider"]
  FB --> SL["Straight-line + landmark
+ Point anchor"]
  PROV --> WGT
  SL --> WGT
  WGT --> STORE["Write Redis (TTL)"]
  STORE --> RET
  classDef core fill:#e8f0fb,stroke:#1f5fae,color:#143d6e;
  classDef warn fill:#fff3e0,stroke:#f4920b,color:#8a5200;
  class GEO,OSRM core; class FB,PROV,SL warn;
        

Map-matching deserves emphasis. Rural GPS is noisy: a partner's phone may report a fix 30–80 m off the actual road, or inside a field. Before routing, the geo module snaps the coordinate to the most plausible road segment given the recent track (OSRM's /match service does exactly this). Without snapping, a route would start "in the middle of a paddy field" and produce nonsense distances. Snapping is also what keeps the live partner trail on the road as it moves (see Geolocation).

3. Fastest single route & ETA

For a single A→B path, OSRM precomputes the road graph using Contraction Hierarchies (CH) — a preprocessing technique that makes shortest-path queries (a Dijkstra-style search over a contracted graph) return in microseconds even on a large district extract. The raw output is a route geometry plus a base travel time. We never ship that base time to the booker untouched.

The displayed ETA is the base time multiplied by a rural reality factor:

The factors come from the road-graph weighting in §4. A generic maps ETA assumes a tarred highway at car speed; on an unpaved monsoon-soft village road, a loaded mini-truck moves at a fraction of that, so applying the factor stops us from promising arrivals we cannot keep. A slightly pessimistic ETA that we beat builds trust; an optimistic one we miss destroys it.

flowchart LR
  A["Snapped origin + dest"] --> CH["OSRM Contraction Hierarchies
(Dijkstra-style query)"]
  CH --> BASE["Route geometry + base time"]
  BASE --> F1["× surface factor"]
  F1 --> F2["× vehicle factor"]
  F2 --> F3["× season / monsoon factor"]
  F3 --> F4["× daylight / safety factor"]
  F4 --> ETA["Conservative ETA shown to booker"]
  ETA --> LIVE["Recompute as partner moves
(live ETA)"]
        

Live ETA updates: the partner's position streams in (see Geolocation). As each fix arrives, the geo module re-snaps it and recomputes the remaining route from the partner's current point to the next stop, so the countdown the booker sees is always "from where the partner actually is now." We debounce this — recompute on a meaningful move or every N seconds, not on every jittery fix — and serve the recompute from cache where the corridor is unchanged.

4. Rural road-graph weighting

Off-the-shelf maps are built for cars on highways in cities. They will happily route a mini-truck down a dirt track that floods in July, or send a tractor along a route that a bike could take but a tractor cannot. RideChain corrects this by treating every road edge as carrying a set of weight factors, applied on top of OSRM's base time. The weighting is also vehicle-class aware: the same physical road has a different cost for a cycle, a bike, an auto, a Tata Ace, or a tractor-trolley.

Why generic maps fail rural India: they lack the surface metadata, treat every vehicle as a car, ignore monsoon seasonality, and have no concept of a ferry timetable on a village river crossing. The result is confidently-wrong routes and ETAs. RideChain's weighting layer turns OSRM's geometric answer into an operational one — the route a real Bolero can actually drive today, in this weather, at this hour. The factors are sourced from OSM tags where present, enriched by partner-reported road conditions and manual overrides, and stored alongside the graph in PostGIS.

5. The VRP — multi-stop bundling

This is the cost lever. The Vehicle Routing Problem asks: given a vehicle with a fixed capacity, a set of parcels each with a pickup and a drop and possibly a time window, what stop sequence minimises total trip cost while serving every parcel? Solving it well is what lets one trip carry many parcels.

The economics are simple and brutal: cost-per-parcel = trip cost ÷ N, where N is the number of parcels on the trip. A dedicated single-parcel run has N=1, so the parcel eats the whole trip cost. A milk-run with N=20 splits the same fuel-and-time cost twenty ways. That is exactly why a bundled POINT → POINT parcel can be ₹25–45 while the same distance on an urgent dedicated run is ₹70–90 (see Commission & Pricing).

flowchart TB
  IN["Pending parcels
(pickups + drops, time windows)"] --> CLU["Cluster stops
by geography / corridor"]
  CLU --> SEQ["Sequence stops within a cluster
(savings / nearest-neighbour + 2-opt)"]
  SEQ --> CAP{"Within vehicle
capacity?"}
  CAP -- "no" --> SPLIT["Split batch or upgrade vehicle"]
  SPLIT --> CLU
  CAP -- "yes" --> TW{"Time windows
satisfiable?"}
  TW -- "no" --> SPLIT
  TW -- "yes" --> ASSIGN["Assign route to partner
+ compute cost-per-parcel"]
  ASSIGN --> DISP["Dispatch run"]
  classDef core fill:#e8f0fb,stroke:#1f5fae,color:#143d6e;
  classDef warn fill:#fff3e0,stroke:#f4920b,color:#8a5200;
  class CLU,SEQ,ASSIGN core; class SPLIT warn;
        

Heuristics, not brute force. The VRP is NP-hard, so we never search for a provably-optimal tour. We use well-known heuristics that get within a few percent of optimal in milliseconds:

6. Milk-run scheduling

Not every bundle is solved fresh. The cheapest, most predictable runs are scheduled milk-runs: a fixed loop from a Block Hub out to a string of village Points and back, on a timetable. Parcels accumulate at the hub between runs; when the scheduled departure arrives (or the hub fills past a threshold), the run is sequenced by the VRP over whatever is staged and dispatched.

The key efficiency trick is the backhaul: the outbound leg carries parcels to villages; the return leg, which would otherwise run empty, carries village produce back to the mandi (market). Filling the empty return leg roughly halves the dead-kilometre cost of the loop and adds a second revenue stream from the same fuel.

flowchart LR
  HUB["🏬 Block Hub
parcels accumulate"] -->|"outbound: drop parcels"| V1["Village Point 1"]
  V1 --> V2["Village Point 2"]
  V2 --> V3["Village Point 3"]
  V3 -->|"backhaul: load produce"| MANDI["🧺 Mandi / market"]
  MANDI -->|"return leg, now full"| HUB
  classDef hub fill:#fff3e0,stroke:#f4920b,color:#8a5200;
  classDef green fill:#e7f6ec,stroke:#1f9d57,color:#0f5c33;
  class HUB hub; class MANDI green;
        

7. Re-routing & dynamic events

A planned route rarely survives contact with reality. A road blocks, a vehicle breaks down, an urgent parcel is booked along a route already in flight, or a partner deviates from the plan. Re-routing handles each by re-solving incrementally from the partner's current position over the remaining stops — never throwing away progress already made.

flowchart TB
  EV["Dynamic event
(block / breakdown / urgent insert / deviation)"] --> POS["Take partner's current snapped position"]
  POS --> REM["Take remaining stops only"]
  REM --> KIND{"Event type?"}
  KIND -- "road block" --> BLK["Mark edge impassable
re-route around"]
  KIND -- "breakdown" --> RED["Re-dispatch remaining stops
to new vehicle"]
  KIND -- "urgent insert" --> INS{"Fits capacity + windows
with small detour?"}
  KIND -- "deviation" --> SNP["Re-snap + recompute remaining"]
  INS -- "yes" --> ADD["Insert stop into live route"]
  INS -- "no" --> NEW["Spin separate run"]
  BLK --> SOLVE["Incremental re-solve over remaining stops"]
  RED --> SOLVE
  ADD --> SOLVE
  SNP --> SOLVE
  SOLVE --> PUSH["Push updated route + ETA to Dispatch / Partner app"]
        

8. Performance & caching

Routing is called constantly — every ETA refresh, every match candidate, every VRP solve — so it must be cheap per call. We keep it cheap by computing as little as possible at request time.

1. Precompute hot corridors — the handful of hub→village and village→mandi paths used every day are computed once and pinned in cache; they almost never change.
2. Batch ETA queries — OSRM's table/matrix service answers many origin→destination pairs in one call, so the VRP gets its whole distance matrix in a single round-trip instead of N² queries.
3. Redis cache with TTL — route geometry and ETAs are stored with a time-to-live; a repeat query for the same corridor in the TTL window is a memory read, not an OSRM solve.
4. Invalidate on event — a road block, flood flag or partner-reported closure invalidates affected cache keys immediately, so we never serve a stale route around a real obstacle.
5. Shard by region — each district/region runs its own OSRM extract and cache shard, so load scales horizontally and a query only touches the graph it needs.

9. Edge cases & failure modes

Routing in the rural interior is the unhappy path by default — missing roads, stale maps, floods, broken-down trucks and noisy GPS are the norm, not the exception. Every risk below has a defined mitigation; the full catalogue lives in the Edge-Case Catalog.