osrm-backend

Open Source Routing Machine - C++ backend

6,994

3,664

6,994

452

View on GitHub

Top Related Projects

graphhopper

5,914

Open source routing engine for OpenStreetMap. Use it as Java library or standalone web server.

valhalla

4,976

Open Source Routing Engine for OpenStreetMap

Quick Overview

OSRM (Open Source Routing Machine) is an open-source routing engine for shortest path queries on road networks. It is designed to be fast and efficient, making it suitable for use in real-time applications such as navigation systems and route planning tools.

Pros

High Performance: OSRM is designed to be fast and efficient, capable of handling large road networks and providing quick responses to routing queries.
Scalability: OSRM can handle road networks of varying sizes, from small cities to entire countries, making it suitable for a wide range of applications.
Customizability: OSRM allows users to customize the routing algorithm and data sources, enabling the creation of specialized routing solutions.
Open-Source: OSRM is an open-source project, allowing developers to contribute to the codebase, report issues, and collaborate on improvements.

Cons

Complexity: Setting up and configuring OSRM can be a complex process, especially for users who are new to the project.
Limited Documentation: The project's documentation, while comprehensive, could be improved to make it more accessible for new users.
Dependency on External Data: OSRM relies on external data sources, such as OpenStreetMap, to build its road network. The quality and accuracy of the routing results depend on the quality of the underlying data.
Limited Mobile Support: While OSRM can be used in mobile applications, the project's focus is primarily on server-side routing, and the mobile experience may not be as polished as some commercial alternatives.

Code Examples

OSRM is a C++ library, and it provides a variety of APIs for interacting with the routing engine. Here are a few examples of how to use OSRM:

Performing a Simple Route Query:

#include <osrm/osrm.hpp>
#include <osrm/route_parameters.hpp>
#include <osrm/json_container.hpp>

int main() {
    OSRM osrm("path/to/osrm/data");
    RouteParameters params;
    params.coordinates.emplace_back(52.519930, 13.438640);
    params.coordinates.emplace_back(52.513191, 13.415852);
    params.steps = true;
    
    json::Object result;
    osrm.Route(params, result);
    
    // Process the routing result
    std::cout << result.dump() << std::endl;
    return 0;
}

Customizing the Routing Profile:

#include <osrm/osrm.hpp>
#include <osrm/engine_config.hpp>

int main() {
    EngineConfig config;
    config.storage_config = "path/to/osrm/data";
    config.use_shared_memory = false;
    config.algorithm = EngineConfig::Algorithm::MLD;
    
    OSRM osrm(config);
    
    // Perform routing queries using the customized profile
    // ...
    
    return 0;
}

Batch Processing of Routing Queries:

#include <osrm/osrm.hpp>
#include <osrm/route_parameters.hpp>
#include <osrm/json_container.hpp>

int main() {
    OSRM osrm("path/to/osrm/data");
    
    std::vector<RouteParameters> batch_params;
    batch_params.emplace_back(52.519930, 13.438640, 52.513191, 13.415852);
    batch_params.emplace_back(48.137154, 11.576124, 48.145386, 11.558496);
    
    std::vector<json::Object> batch_results;
    osrm.BatchRoute(batch_params, batch_results);
    
    // Process the batch routing results
    for (const auto& result : batch_results) {
        std::cout << result.dump() << std::endl;
    }
    
    return 0;
}

Getting

Competitor Comparisons

graphhopper

5,914

Open source routing engine for OpenStreetMap. Use it as Java library or standalone web server.

Pros of GraphHopper

More flexible and customizable, allowing for easier integration of custom algorithms and data structures
Better support for multiple profiles (car, bike, foot, etc.) within a single graph
More actively maintained with frequent updates and community contributions

Cons of GraphHopper

Generally slower performance compared to OSRM, especially for large-scale routing tasks
Higher memory consumption, which can be a limitation for resource-constrained environments
Steeper learning curve due to its more complex architecture and customization options

Code Comparison

OSRM (C++):

osrm::EngineConfig config;
config.storage_config = {"path/to/data.osrm"};
config.use_shared_memory = false;
osrm::OSRM engine(config);

GraphHopper (Java):

GraphHopper hopper = new GraphHopper();
hopper.setOSMFile("path/to/map.osm.pbf");
hopper.setGraphHopperLocation("path/to/graph-cache");
hopper.setProfiles(new Profile("car").setVehicle("car").setWeighting("fastest"));
hopper.importOrLoad();

Both OSRM and GraphHopper are powerful routing engines, but they cater to different use cases. OSRM excels in performance and is ideal for large-scale applications, while GraphHopper offers more flexibility and easier customization for diverse routing scenarios.

valhalla

4,976

Open Source Routing Engine for OpenStreetMap

Pros of Valhalla

Multi-modal routing support (car, bike, pedestrian, public transit)
Better support for real-time traffic updates and dynamic costing
More flexible customization options for routing algorithms

Cons of Valhalla

Potentially higher memory usage and slower preprocessing times
Less extensive documentation compared to OSRM
Steeper learning curve for implementation and customization

Code Comparison

OSRM (C++):

osrm::EngineConfig config;
config.storage_config = {"path/to/data.osrm"};
config.use_shared_memory = false;
osrm::OSRM engine(config);

Valhalla (C++):

boost::property_tree::ptree pt;
rapidjson::read_json("conf/valhalla.json", pt);
valhalla::baldr::GraphReader reader(pt.get_child("mjolnir"));
valhalla::loki::SearchLocation origin, destination;

Both projects offer powerful routing capabilities, but Valhalla provides more flexibility for multi-modal routing and real-time updates. OSRM, on the other hand, may be easier to set up and use for simpler routing tasks. The choice between the two depends on specific project requirements and the level of customization needed.

leaflet-routing-machine

1,137

Control for routing in Leaflet

Pros of leaflet-routing-machine

Easy integration with Leaflet maps for client-side routing
Supports multiple routing engines, including OSRM
Customizable UI with waypoint dragging and route display

Cons of leaflet-routing-machine

Limited to client-side routing, which may not be suitable for large-scale applications
Depends on external routing services, potentially increasing costs and latency
Less control over the underlying routing algorithm compared to osrm-backend

Code Comparison

leaflet-routing-machine:

L.Routing.control({
  waypoints: [
    L.latLng(57.74, 11.94),
    L.latLng(57.6792, 11.949)
  ],
  routeWhileDragging: true
}).addTo(map);

osrm-backend:

osrm::EngineConfig config;
config.storage_config = {"path/to/osrm/data"};
config.use_shared_memory = false;
osrm::OSRM osrm{config};

The leaflet-routing-machine code snippet shows how to add routing control to a Leaflet map, while the osrm-backend code demonstrates the initialization of the OSRM engine. leaflet-routing-machine focuses on the frontend integration, whereas osrm-backend provides low-level access to the routing engine, allowing for more customization and control over the routing process.

Convert designs to code with AI

Introducing Visual Copilot: A new AI model to turn Figma designs to high quality code using your components.

Try Visual Copilot

README

Open Source Routing Machine

High performance routing engine written in C++ designed to run on OpenStreetMap data.

The following services are available via HTTP API, C++ library interface and NodeJs wrapper:

Nearest - Snaps coordinates to the street network and returns the nearest matches
Route - Finds the fastest route between coordinates
Table - Computes the duration or distances of the fastest route between all pairs of supplied coordinates
Match - Snaps noisy GPS traces to the road network in the most plausible way
Trip - Solves the Traveling Salesman Problem using a greedy heuristic
Tile - Generates Mapbox Vector Tiles with internal routing metadata

To quickly try OSRM use our demo server which comes with both the backend and a frontend on top.

For a quick introduction about how the road network is represented in OpenStreetMap and how to map specific road network features have a look at the OSM wiki on routing or this guide about mapping for navigation.

Related Project-OSRM repositories:

osrm-frontend - User-facing frontend with map. The demo server runs this on top of the backend
osrm-text-instructions - Text instructions from OSRM route response
osrm-backend-docker - Ready to use Docker images

Documentation

Full documentation

Contact

Discord: join
IRC: irc.oftc.net, channel: #osrm (Webchat)
Mailinglist: https://lists.openstreetmap.org/listinfo/osrm-talk

Quick Start

The easiest and quickest way to setup your own routing engine is to use Docker images we provide.

There are two pre-processing pipelines available:

Contraction Hierarchies (CH)
Multi-Level Dijkstra (MLD)

we recommend using MLD by default except for special use-cases such as very large distance matrices where CH is still a better fit for the time being. In the following we explain the MLD pipeline. If you want to use the CH pipeline instead replace osrm-partition and osrm-customize with a single osrm-contract and change the algorithm option for osrm-routed to --algorithm ch.

Using Docker

We base our Docker images (backend, frontend) on Debian and make sure they are as lightweight as possible. Older backend versions can be found on Docker Hub.

Download OpenStreetMap extracts for example from Geofabrik

wget http://download.geofabrik.de/europe/germany/berlin-latest.osm.pbf

Pre-process the extract with the car profile and start a routing engine HTTP server on port 5000

docker run -t -v "${PWD}:/data" ghcr.io/project-osrm/osrm-backend osrm-extract -p /opt/car.lua /data/berlin-latest.osm.pbf || echo "osrm-extract failed"

The flag -v "${PWD}:/data" creates the directory /data inside the docker container and makes the current working directory "${PWD}" available there. The file /data/berlin-latest.osm.pbf inside the container is referring to "${PWD}/berlin-latest.osm.pbf" on the host. Noting that this process can take a long time to complete with little changes on the terminal output, for example, a Mexico's OSM file of 550.7MB took around 30 minutes to finish extraction and generate edge-expanded graph representation.

docker run -t -v "${PWD}:/data" ghcr.io/project-osrm/osrm-backend osrm-partition /data/berlin-latest.osrm || echo "osrm-partition failed"
docker run -t -v "${PWD}:/data" ghcr.io/project-osrm/osrm-backend osrm-customize /data/berlin-latest.osrm || echo "osrm-customize failed"

Note there is no berlin-latest.osrm file, but multiple berlin-latest.osrm.* files, i.e. berlin-latest.osrm is not file path, but "base" path referring to set of files and there is an option to omit this .osrm suffix completely(e.g. osrm-partition /data/berlin-latest).

docker run -t -i -p 5000:5000 -v "${PWD}:/data" ghcr.io/project-osrm/osrm-backend osrm-routed --algorithm mld /data/berlin-latest.osrm

Make requests against the HTTP server

curl "http://127.0.0.1:5000/route/v1/driving/13.388860,52.517037;13.385983,52.496891?steps=true"

Optionally start a user-friendly frontend on port 9966, and open it up in your browser

docker run -p 9966:9966 osrm/osrm-frontend
xdg-open 'http://127.0.0.1:9966'

In case Docker complains about not being able to connect to the Docker daemon make sure you are in the docker group.

sudo usermod -aG docker $USER

After adding yourself to the docker group make sure to log out and back in again with your terminal.

We support the following images in the Container Registry:

Name	Description
`latest`	`master` compiled with release flag
`latest-assertions`	`master` compiled with with release flag, assertions enabled and debug symbols
`latest-debug`	`master` compiled with debug flag
`<tag>`	specific tag compiled with release flag
`<tag>-debug`	specific tag compiled with debug flag

Building from Source

The following targets Ubuntu 22.04. For instructions how to build on different distributions, macOS or Windows see our Wiki.

Install dependencies

sudo apt install build-essential git cmake pkg-config \
libbz2-dev libxml2-dev libzip-dev libboost-all-dev \
lua5.2 liblua5.2-dev libtbb-dev

Compile and install OSRM binaries

mkdir -p build
cd build
cmake ..
cmake --build .
sudo cmake --build . --target install

Request Against the Demo Server

Read the API usage policy.

Simple query with instructions and alternatives on Berlin:

curl "https://router.project-osrm.org/route/v1/driving/13.388860,52.517037;13.385983,52.496891?steps=true&alternatives=true"

Using the Node.js Bindings

The Node.js bindings provide read-only access to the routing engine. We provide API documentation and examples here.

You will need a modern libstdc++ toolchain (>= GLIBCXX_3.4.26) for binary compatibility if you want to use the pre-built binaries. For older Ubuntu systems you can upgrade your standard library for example with:

sudo add-apt-repository ppa:ubuntu-toolchain-r/test
sudo apt-get update -y
sudo apt-get install -y libstdc++-9-dev

You can install the Node.js bindings via npm install @project-osrm/osrm or from this repository either via

npm install

which will check and use pre-built binaries if they're available for this release and your Node version, or via

npm install --build-from-source

to always force building the Node.js bindings from source.

Unscoped packages

Prior to v5.27.0, the osrm Node package was unscoped. If you are upgrading from an old package, you will need to do the following:

npm uninstall osrm --save
npm install @project-osrm/osrm --save

Package docs

For usage details have a look these API docs.

An exemplary implementation by a 3rd party with Docker and Node.js can be found here.

References in publications

When using the code in a (scientific) publication, please cite

@inproceedings{luxen-vetter-2011,
 author = {Luxen, Dennis and Vetter, Christian},
 title = {Real-time routing with OpenStreetMap data},
 booktitle = {Proceedings of the 19th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems},
 series = {GIS '11},
 year = {2011},
 isbn = {978-1-4503-1031-4},
 location = {Chicago, Illinois},
 pages = {513--516},
 numpages = {4},
 url = {http://doi.acm.org/10.1145/2093973.2094062},
 doi = {10.1145/2093973.2094062},
 acmid = {2094062},
 publisher = {ACM},
 address = {New York, NY, USA},
}

Top Related Projects

Convert designs to code with AI

Introducing Visual Copilot: A new AI model to turn Figma designs to high quality code using your components.

Try Visual Copilot