OSRM (Open Source Routing Machine) is a high-performance routing engine written in modern C++, specifically designed for computing the shortest path in road networks. Its core objective is to provide a fast, reliable, and customizable routing solution capable of handling continental-scale road network data, returning results in milliseconds. It serves as an ideal underlying engine for building applications such as map navigation, logistics distribution, and location-based services.

Key Features

  • Extreme Performance: Highly optimized for massive OpenStreetMap data, capable of processing road networks with tens of millions of nodes. Query response times are typically in the millisecond range, meeting the demands of real-time applications.
  • Multi-Modal Transport Support: Natively supports various travel modes such as car, bicycle, and foot, each with predefined routing rules (e.g., speed limits, one-way streets, bicycle accessibility).
  • Highly Customizable Rules: Through flexible "Profiles," developers can easily modify routing logic, such as setting vehicle size/weight restrictions, avoiding toll roads, adjusting priorities for different road classes, etc., to adapt to specific application scenarios.
  • Simple HTTP API: Provides a standardized HTTP API supporting core functions like route querying, distance matrices, and map matching, making it easy to integrate with various front-end applications (e.g., web, mobile apps).
  • Based on OpenStreetMap Data: Directly uses global OpenStreetMap open-source map data, which is frequently updated and widely覆盖.

Contraction Hierarchies (CH) Algorithm

GIS professionals are familiar with classic routing algorithms like Dijkstra or A*. These algorithms perform well on small-scale maps, but when the data scale expands to entire continents like Europe or North America, the computational complexity of Dijkstra's algorithm makes it nearly impossible to meet real-time online query requirements.

OSRM's core competitiveness lies in its clever algorithm design. It primarily employs the Contraction Hierarchies (CH) algorithm (combined with Multi-Level Dijkstra, MLD). The essence of the CH algorithm is "preprocessing":

  1. Preprocessing Phase: This is the "heavy" operation of OSRM. It reads all OSM road network data and "contracts" the graph. This process intelligently orders nodes (intersections) and creates "shortcuts," building a hierarchical graph structure. This phase may take minutes to hours (depending on the road network size), but it is a one-time operation.
  2. Querying Phase: Once preprocessing is complete, OSRM possesses an accelerated data structure. When a user requests a path from point A to point B, OSRM no longer needs to traverse massive amounts of original road network nodes. Instead, it can perform extremely fast queries on this graph with "shortcuts" and "hierarchies."

It is this model of "preprocess once, query quickly infinitely" that enables OSRM to compress route computation time to milliseconds on continental-scale road networks.

Quick Start

Official Website: https://project-osrm.org/

Source Code: https://github.com/Project-OSRM/osrm-backend

The typical workflow is as follows:

  1. Obtain Raw Data: Download the required road network data from sources like Geofabrik or OSM Planet.
  2. Preprocessing: Use tools like osrm-extract, osrm-partition, osrm-customize, or osrm-contract (depending on the chosen algorithm).
  3. Start the Routing Service: Run osrm-routed or deploy the service via Docker image (running in the background, listening for HTTP requests).
  4. Send Requests: Call the HTTP API, e.g., /route/v1/driving/{coords} to retrieve the route and duration.
  5. Front-End Display: Integrate the returned geometry, instructions, nodes, and annotations into GIS systems, visualization interfaces, or further analysis workflows.

Summary

Overall, OSRM is an excellent open-source routing engine for GIS, spatial network analysis, and service deployment scenarios. From the chain of "base data (OSM) → preprocessing → serviced queries," it exhibits characteristics of high performance, customizability, and low cost of use. For GIS professionals, if your scenarios involve road network analysis, accessibility/time-distance matrix construction, logistics route optimization, or building self-hosted navigation services, OSRM is worth trying.