OSRM data generation and deployment

Open Source Routing Machine

The Open Source Routing Machine (OSRM) is an open-source router designed for use with data from the OpenStreetMap project. 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

Why OpenStreetMap over Google Maps ?

Open Street Maps (OSM) is an open source project maintained by the OpenStreetMap Community that provides free editable maps of the whole world. The most obvious advantage in using OpenStreetMap-based software over a commercial solution is economical convenience, because OpenStreetMap comes as free software.

The downside is that it takes a little configuration in order to setup a working web service. The easiest and quickest way to setup your own routing engine is to use Docker images

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.

Generate data using Docker:

Our web service will be based on a map export from OpenStreetMap. There are several possible ways to obtain a map export.

The first option is to point your browser to the OpenStreetMap’s export page, zoom on the interested area, and click on Export. (You may need to use one of the other sources if the native export does not work; Overpass API is a good choice.) This will allow you to finely choose which areas to include in your map and, in general, to cut down on the pre-processing times.

https://www.openstreetmap.org/export#map=6/16.225/73.059

However, there are limits on the size of the export you can get from the OSRM website, so you might want to download a ready-made export. A number of services, such as Geofabrik and Mapzen offer updated and ready-made map exports of countries and selected metropolitan areas, which are good for most use cases.

In this article we will see how the OSRM data is generated for India using MLD pipeline.

To generate the routing data you need to download the .pbf file for India from Geofabrik.

wget http://download.geofabrik.de/asia/india-latest.osm.pbf

OSM data comes in a variety of formats including XML and PBF, and contain a plethora of data. The data includes information which is irrelevant to routing, such as positions of public waste baskets. Also, the data does not conform to a hard standard and important information can be described in various ways. Thus it is necessary to extract the routing data into a normalized format. This is done by the OSRM tool named extractor.

Profiles are used during this process to determine what can be routed along, and what cannot (private roads, barriers etc.).

For the MLD pipeline we need to extract (osrm-extract) a graph out of the OpenStreetMap base map

docker run -t -v $(pwd):/data osrm/osrm-backend:latest osrm-extract -p /opt/car.lua /data/india-latest.osm.pbf

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/india-latest.osm.pbf inside the container is referring to $(pwd)/india-latest.osm.pbf on the host

Then partition (osrm-partition) this graph recursively into cells, by using the following command

docker run -t -v $(pwd):/data osrm/osrm-backend:latest osrm-partition /data/india-latest.osrm

Note that india-latest.osrm has a different file extension.

Once the graph is partitioned in to cells, customize the cells (osrm-customize) by calculating routing weights for all cells

docker run -t -v $(pwd):/data osrm/osrm-backend:latest osrm-customize /data/india-latest.osrm

For CH the partition and customize pipeline stage gets replaced by adding shortcuts from the Contraction Hierarchies algorithm (osrm-contract)

Once the graph is customized, then spawning up the development HTTP server (osrm-routed) responding to queries

OSRM Docker Deployment

Docker image can be run standalone without Kubernetes

docker run -t -i -p 5000:5000 -v $(pwd):/data -d osrm/osrm-backend:latest osrm-routed — algorithm mld /data/india-latest.osrm

Make requests against the HTTP server

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

docker run -p 9966:9966 osrm/osrm-frontend

OSRM Kubernetes Deployment

To deploy the OSRM in Kubernetes cluster, we need the routing data inside the Kubernetes cluster. There are multiple ways to achieve this. The reliable way is to use persistent volume model in a dynamic Kubernetes cluster. On a standalone k8s cluster the simple and easiest way is to use the hostPath.

To deploy on standalone cluster once the data generation is completed, copy all the generated files to the following location /data/osrm/india on the server. Make sure this data is available on all the Kubernetes nodes.

Now use the below mentioned YAML file to deploy the osrm-backend application in k8s.

osrm-backend-india.yaml

apiVersion: v1
kind: Service
metadata:
  name: osrm-india
  labels:
    app: osrm-india
spec:
  ports:
  - port: 5000
    targetPort: 5000
    name: http
  selector:
    app: osrm-india
  type: NodePort
---
apiVersion: extensions/v1beta1
kind: Deployment
metadata:
  name: osrm-india
spec:
  replicas: 1
  template:
    metadata:
      labels:
        app: osrm-india
    spec:
      containers:
      - name: osrm-india
        image: osrm-backend:latest
        command: ["/bin/sh", "-c"]
        args: ["osrm-routed --algorithm mld /data/india-latest.osm.pbf"]
        ports:
        - containerPort: 5000
          name: osrm-port
        volumeMounts:
        - name: india
          readOnly:  true
          mountPath: /data
      volumes:
      - name: india
        hostPath:
          path: /data/osrm/india
        resources:
          requests:
            memory: "512Mi"
            cpu: "0.5"
          limits:
            memory: "512Mi"
            cpu: "0.5"

Below config make sure the data is mounted to the docker container while deploying

        volumeMounts:
        - name: india
          readOnly:  true
          mountPath: /data
      volumes:
      - name: india
        hostPath:
          path: /data/osrm/india

Command to run the osrm-backend image in Kubernetes

kubectl apply -f osrm-india.yaml

To deploy the user-facing frontend with map, apply the below file

osrm-frontend.yaml

kind: Service
metadata:
  name: osrm-frontend
  labels:
    app: osrm-frontend
spec:
  ports:
  - port: 9966
    targetPort: 9966
    name: http
  selector:
    app: osrm-frontend
  type: NodePort
---
apiVersion: extensions/v1beta1
kind: Deployment
metadata:
  name: osrm-frontend
spec:
  replicas: 1
  template:
    metadata:
      labels:
        app: osrm-frontend
    spec:
      containers:
      - name: osrm-frontend
        image: osrm/osrm-frontend
        ports:
        - containerPort: 9966
          name: osrm-frontend
        env:
        - name: BACKEND
          value: 'http://osrm-india:5000'

Command to run the osrm-backend image in Kubernetes

kubectl apply -f osrm-frontend.yaml

Note:

OSRM data can be generated for any countries. The data generation consumes lot of memory on your server based on the country . To generate OSRM data for India, docker runs consumes almost 7 GB of RAM on the server.

Conclusion

This blog covers the configuration and maintenance of a web service which can answer questions such as:

• What is the closest street to a given pair of coordinates?
• What’s the best way to get from point A to point B?
• How long does it take to get from point A to point B with a car, or by foot?

References

Geofabrik Download Server

BBBike extracts OpenStreetMap