MPEE — Offline route calculations & optimization

What it is

MPEE is built from two Rust crates — dijeng<br>(contraction-hierarchy routing) and brooom (the VRP<br>solver). Together they solve a 50,000-customer vehicle-routing problem on<br>a laptop without ever materialising a full distance matrix ,<br>and in head-to-head tests on a Mac they produced shorter routes than<br>VROOM at equal runtime,<br>using less memory. The engine binary is under ~50 MB; the map cache<br>scales with the area you download.

🧭<br>Point-to-point routes<br>Driving distance + time between two coordinates, with optional geometry.

🚚<br>Multi-vehicle VRP<br>Best routes for N vehicles over your own stops — capacities, skills, time windows, mixed fleets.

🔎<br>Offline geocoding<br>Street ⇄ coordinate and street-crossing lookup, reusing the same cache. No separate index.

🗺️<br>Bring your own area<br>Any OpenStreetMap extract sized to where you operate. One downloaded area, one cache.

Scope: MPEE covers a single downloaded area — it is not<br>a route-anywhere-on-Earth offline map. There is no global tiling, by<br>design: within your area, one cache is simpler and faster.

How it compares (measured, Apple M3 Pro)

A 50,000-customer fleet implies a 50,000 × 50,000 distance<br>matrix — ~10 GB if you store it. The classic<br>OSRM + VROOM split builds and ships that matrix<br>between two processes; MPEE streams it in one process and never<br>materialises it — which is where the speed and memory wins come from.

Routing — N×N duration+distance matrix · dijeng vs OSRM, Greater London CH (n = 1.16 M)

MatrixMPEE — timeMPEE — peak RAMOSRM

10k × 10k4.3 sstreamedimpractical — no chunked many-to-many<br>50k × 50k 94 s ≤ 500 MB OOM — the matrix alone is ~10 GB

Honest caveat: OSRM is ~3× faster on a single point-to-point query<br>(≈30 µs vs ≈88 µs). MPEE wins decisively the moment you need a fleet-sized<br>matrix — the case VRP actually requires.

Optimisation — VRP solver · brooom vs PyVRP / VROOM / OR-Tools, Solomon-style

ScaleResult

N = 1,000beats the next-best solver (PyVRP) on 17 / 20 seeds, p ≈ 10⁻⁷<br>N = 50,000the only tested solver that converges on a laptop<br>Inner loopthe entire local search (2-opt, relocate, swap-star, Or-opt, ILS-kick, regret-3) as one GPU megakernel — Metal on Mac, Vulkan/DX12 elsewhere; sub-ms per iteration

End-to-end on this machine: 2,000 jobs / 50 vehicles in ~2 min (matrix 0.32 s);<br>5,000 / 100 in ~9 min (matrix 4.10 s), both ≥99 % assigned. Full numbers in the<br>dijeng and<br>brooom READMEs.

Install

pip install mpee

Prebuilt wheel for macOS (arm64); Linux/Windows install from the source<br>distribution (needs a Rust toolchain) until multi-platform wheels are<br>published. Python 3.8+. No Rust toolchain needed for the macOS wheel.

Quick start (CLI)

1. Install & get a map once

# MPEE — offline routing, VRP & street geocoding for one downloaded area.<br># Docs: https://punnerud.github.io/mpee/ Source: https://github.com/punnerud/mpee<br>pip install mpee

# Download an OpenStreetMap extract (Geofabrik) …<br>mpee download europe/great-britain/england/greater-london

# … and preprocess it into a routable cache (.pp + .ch + .names).<br>mpee build data/greater-london-latest.osm.pbf # car (default)<br># mpee build data/greater-london-latest.osm.pbf bicycle # or: car | bicycle | foot<br>After this you are fully offline. The cache is reusable; a re-run reuses it instantly (--force rebuilds, --quiet hushes progress).

2. Route from A to B

mpee route 51.5080,-0.1281 51.5138,-0.0984 --cache data/greater-london-latest.osm.pbf<br># distance: 2.38 km<br># duration: 4.4 min

3. Optimize a delivery run over many stops

# stops.txt: one "lat,lon" per line (or a JSON [[lat,lon], …])<br>mpee optimize --stops stops.txt --vehicles 5 --capacity 20 \<br>--cache data/greater-london-latest.osm.pbf<br># stops: 50 vehicles used: 3/5 unassigned: 0<br># total: 60.0 km, 115 min (solved in 4.6s)

4. Geocode within the area (offline)

mpee reverse 51.5080,-0.1281 --cache data/greater-london-latest.osm.pbf # → Trafalgar Square<br>mpee geocode "Baker Street" --cache data/greater-london-latest.osm.pbf # → 51.522072,-0.157497<br>mpee crossing "Oxford Street" "Regent Street" --cache ... # → Oxford Circus (LAT,LON)

Use it from Python

Coordinate order. The simple helpers take<br>(lat, lon). The VROOM-style solve(problem)<br>accepts a coordinate as {"lat": …, "lon": …} (recommended),<br>[lon, lat], or {"coord": [lon, lat]}.

import mpee

# Open a prebuilt cache (built once via `mpee build`).<br>r = mpee.Router("data/greater-london-latest.osm.pbf.pp",<br>"data/greater-london-latest.osm.pbf.ch")

# Distance + time between two points.<br>leg = r.route(51.5080, -0.1281, 51.5138, -0.0984)<br>print(leg["distance_km"], "km,", leg["duration_min"], "min")

# Optimize 50 deliveries across 5 vehicles.<br>stops = [(51.51, -0.12), (51.49, -0.10)] # your (lat, lon) list<br>plan = r.optimize(stops, vehicles=5, capacity=20, time_limit_s=5.0)

# Geocoding (needs the .names sidecar built by `mpee build`).<br>r.reverse(51.5080, -0.1281) # → "Trafalgar Square"<br>r.geocode("Baker Street") # → {"name", "lat",...