03 / Constrained micromobility routing2025
A real-time routing engine that formulates the 45-minute bikeshare rental limit as a resource-constrained shortest path problem.
50ms
p99 latency
O(V log V)
routing complexity
Live
GBFS sync
Author
my role
Capital Bikeshare imposes strict 45-minute limits on single rentals, making cross-city commutes logistically painful. Instead of chaining naive API calls, CapitalBikeRoute+ treats this as a resource-constrained shortest path problem. It maintains a live spatial graph of the DC metro area, ingests General Bikeshare Feed Specification (GBFS) updates into Redis to monitor dock availability, and uses a modified graph search in Rust to find the optimal sequence of intermediate docking stations that minimizes overall travel time without violating the rental window.
What I did
- 01Formulated multi-leg routing as a constrained graph search, dynamically penalizing full or empty stations.
- 02Built a streaming ingestion pipeline in Python to keep the dock availability graph synchronized with live GBFS feeds.
- 03Implemented the core routing kernel in Rust to ensure p99 query latencies remain under 50ms.
- 04Exposed the routing engine via a scalable FastAPI backend.