Route calculation in pure C, from PBF to path

A routing engine you can embed anywhere

OSRM and Valhalla are excellent routing engines, but they're large C++ projects with dozens of dependencies, heavy preprocessing pipelines, and multi-GB memory footprints even for small regions. Want to run routing in the browser? On a truck's onboard computer? In a WASM sandbox? You need something smaller.

Velo trades some features for radical simplicity: one PBF file in, routes out. No PostgreSQL, no preprocessing database, no protobuf compiler. Load a PBF (or a pre-built .vlg binary index for 100× faster loading), build a CSR graph, and start routing. The same code runs native, embedded, or in the browser via WASM.

From brute-force to landmark-guided search

  vl_route(graph, from, to, options)
       │
       ▼
  ┌──────────────┐
  │ Grid Index   │  O(1) nearest node lookup
  │ 1000x1000    │  (lat/lon → node_id)
  └──────┬───────┘
         │
         ├─── VL_ALGORITHM_DIJKSTRA ─────────▶ Explores 100%
         ├─── VL_ALGORITHM_DIJKSTRA_BIDIR ──▶ Explores ~50%
         ├─── VL_ALGORITHM_ASTAR ────────────▶ Explores 30-50%
         ├─── VL_ALGORITHM_ASTAR_BIDIR ─────▶ Explores ~25%   (default)
         ├─── VL_ALGORITHM_ALT ──────────────▶ Explores 5-15%  (with landmarks)
         └─── VL_ALGORITHM_BUCKET_HEAP ─────▶ O(1) amortized ops

Query time comparison (Hungary, 2.7M nodes)

ALT landmarks

A* with Landmarks and Triangle Inequality. At startup, Velo computes shortest-path distances from every node to/from 16–32 landmark nodes. At query time, these precomputed distances provide a tighter lower bound than Haversine, dramatically pruning the search space.

• Dual-mode — separate distance and time landmarks for shortest and fastest queries
• 5–15× speedup over bidirectional A* on country-scale routes
• Preprocessing — 4–8 seconds for 32 landmarks on Hungary
• Memory — ~2.6GB for 32 landmarks, 2.7M nodes (compressed)

Car, truck, bike, foot — per-edge access control

Profiles are implemented as bitmask flags on each edge, extracted from OSM access tags during PBF parsing. Filtering adds zero overhead at query time — it's a single bitwise AND per edge relaxation.

Optimization modes

REST, C library, or WASM — same code

REST API (port 8082)

# Route between two points (fastest car route)
curl "http://localhost:8082/api/v1/route?from=47.497,19.040&to=46.253,20.148"

# Truck profile, shortest distance, with geometry
curl "http://localhost:8082/api/v1/route?\
  from=47.497,19.040&to=46.253,20.148&\
  profile=truck&mode=shortest&geometry=true"

# Response:
# {
#   "status": "ok",
#   "route": {
#     "distance": 187432.5,
#     "duration": 7234.2,
#     "profile": "truck",
#     "mode": "shortest",
#     "geometry": "encoded_polyline..."
#   },
#   "meta": { "nodes_explored": 12543, "search_time_ms": 34.5 }
# }

C API

// Load graph from binary index (100ms)
VLGraph *g = vl_load_binary("hungary.vlg");

// Build ALT landmarks (4-8 seconds, once at startup)
VLLandmarks *lm = vl_landmarks_create(g, 32);

// Route: Budapest → Szeged, truck, fastest
VLRouteOptions opts = {
    .algorithm = VL_ALGORITHM_ALT,
    .profile   = VL_PROFILE_TRUCK,
    .weight    = VL_WEIGHT_DURATION,
    .landmarks = lm
};

VLRoute route;
VLStatus status = vl_route(g, from, to, &opts, &route);

if (status == VL_STATUS_OK) {
    printf("%.0fm in %.0fs\n", route.distance, route.duration);
}
vl_route_free(&route);
vl_landmarks_free(lm);
vl_graph_free(g);

Graph data structures

struct VLNode {
    VLCoordFixed coord;  // lat/lon * 1e7
    uint32_t edge_start;  // edge array idx
    uint32_t edge_count;  // outgoing edges
    int64_t osm_id;
};

struct VLEdge {
    uint32_t target;    // target node
    uint32_t distance;  // millimeters
    uint16_t duration;  // deciseconds
    uint16_t flags;     // road + access
};

CSR, grid index, degree-2 contraction

Graph optimizations

• Degree-2 contraction — eliminates chain nodes (only 2 edges), reduces graph 40–60%
• Grid spatial index — 1000×1000 cells for O(1) average nearest-node lookup
• Reverse graph — pre-built reverse edge index for O(degree) backward search
• Hilbert ordering — cache-friendly geographic node ordering
• Fixed-point coordinates — 32-bit integers (lat × 10⁷) instead of 64-bit doubles

Memory budget (country → continental)

Three ways to try Velo

1. Browser (zero install)

The API documentation page includes a live WASM demo with embedded Monaco data. Calculate routes between Monaco locations in the browser.

2. Build from source

# Clone and build
git clone https://github.com/ottofleet/otto.git
cd otto && make velo

# Run all 52 tests
make test-velo

3. Route server

# Build and start server
make velo-api
./velo/api/velo-route-server data/hungary-latest.osm.pbf

# Or use pre-built index (100x faster loading)
./velo/api/velo-route-server --load-index data/hungary.vlg

# Calculate a route
curl "http://localhost:8082/api/v1/route?\
  from=47.497,19.040&to=46.253,20.148&profile=truck"

Common questions

Why not use OSRM or Valhalla?

Both are excellent but large: OSRM is ~100K LoC of C++ with Boost, Lua, and TBB. Velo is ~7K lines of C with zero dependencies. It compiles to WASM, runs on an onboard computer, and loads a country graph in 100ms from a .vlg file. The tradeoff: OSRM has CH (sub-ms queries), turn-by-turn navigation, and traffic. Velo has ALT (36–86ms), four profiles, and radical simplicity.

How does FuelWise use Velo?

FuelWise calculates fuel-optimal refueling stops along a route. It uses Velo to compute distances between fuel stations along the path, then Ralph (LP solver) to optimize which stations to stop at and how much fuel to load. Velo provides the distance inputs; Ralph provides the optimization.

Can Velo handle continental-scale routing?

Not yet at consumer latency. The US graph (~175M nodes) needs ~20GB RAM with landmarks. The EU graph (~350M nodes) needs ~37GB. A 64-core server with 128GB RAM can serve continental routes in <2 seconds. For sub-millisecond queries, Contraction Hierarchies are planned for Phase 2.

What about truck-specific restrictions?

Velo's truck profile currently avoids hgv=no roads. The roadmap includes height, weight, length, and axle-count constraints from OSM tags, plus hazmat routing. These are stored as sparse restrictions (affecting ~1–5% of edges) to avoid memory bloat.

What license?

AGPLv3 with a Trucking Exception. Same terms as all OTTO modules.