Skip to content

===========================

Osrm is probably the fastest implementation of routing based on openstreetmaps. It's based on the technique of [ContractionHierarchies contraction hierarchies]

Installation

Source : https://github.com/DennisOSRM/Project-OSRM/wiki/Running-OSRM But here is a short version :

changetitle
1
2
3
4
git clone https://github.com/DennisOSRM/Project-OSRM.git
sudo apt-get install build-essential git scons libprotoc-dev libprotobuf7 protobuf-compiler libprotobuf-dev libpng-dev libbz2-dev libstxxl-dev libstxxl-doc libstxxl1 libxml2-dev libzip-dev libboost-thread-dev libboost-system-dev libboost-filesystem-dev libboost-regex-dev lua5.1-dev libluabind-dev
cd Project-OSRM
scons

If everything goes well, you have a number of programs you can use for the subsequent steps.

map generation

You need two steps, both will generate the data files in the same directory as the .osm file. Actually it can use :

  • .osm files
  • .osm.bz2 files
  • .osm.pbf files

The command (with example network) is :

changetitle
1
osrm-extract ../../grid/dat/hvh/network.osm

This will extract the map, into an .osrm, osrm.names and osrm.restrictions file. note If you want t alter speeds edit the file speedprofile.lua in the network where you run the extraction. and you need to do do BOTH steps again but then you need to generate the hierarchy :

changetitle
1
osrm-contract ../../grid/dat/hvh/network.osrm

This will add the files : edges,nodes,ramIndex,fileIndex and hsgr You can then alter the file server.ini and paste these filenames over the used ones.

You can now also generate multi level Dijkstra (MLD) networks. But since matrices are still faster with contraction hierarchies (CH) we don't..

If you want to generate MLD, you would skip the contract step above and instead do :

changetitle
1
2
osrm-partition network.osrm
osrm-customize network.osrm

And start the server :

changetitle
1
2
#./osrm-routed  # this would start it with MLH (default)
./osrm-routed --algorithm ch  # this runs CH !

To test this server use a browser and enter a url like : http://localhost:5000/viaroute?loc=52.248323,5.664496&loc=52.093345,5.774927 You should get a json file with the routing result.

If you do not want to user the osrm-routed server, there is an example program showing how to use the libosrm.a api in the example subdirectory. However it is not that easy to compile so here is the command line that nailed it :

changetitle
1
c++ example.cpp -I ../include -I../third_party/variant/include -I../third_party/flatbuffers/include -L../build -losrm -lboost_system -lrt -lpthread -lboost_thread -lboost_filesystem -lboost_iostreams

Also this still will not work with CH, since MLD is the default :

changetitle
1
2
3
4
./a.out ../netherlands-latest.osrm
terminate called after throwing an instance of 'osrm::util::exception'
what():  Could not find any metrics for MLD in the data. Did you load the right dataset?
Aborted

So to fix that, edit the code and the solution is already added for you though commented :

changetitle
1
2
// config.algorithm = EngineConfig::Algorithm::CH;
config.algorithm = EngineConfig::Algorithm::MLD;

Simply comment the other line instead. The example is for Monaco, so it won't match anything and will tell you just that.

osrm data format

There are two steps in the generation process as described above, the first will make 2 files (given network.osm.pbf) :

  • network.osrm
  • network.osrm.restrictions
  • network.osrm.names

These files are intermediate files and will not be used in routing, except for the .names file, which stays the same in the next step. The second step will create :

  • network.osrm.nodes
  • network.osrm.edges
  • network.osrm.hsgr
  • network.osrm.ramIndex
  • network.osrm.fileIndex

I will describe them in the same order, and use a table-like format that shows a byte per cell.

network.osrm

This image describes the layout of the file, the top blocks represent one bytes each. This would be an osrm file of 3 nodes and 3 roads : net1 The name id in the edges record is 0 for edges without a name or a direct index in the .names file mentioned later.

network.osrm.restrictions

For now, i have to settle for the layout as analyzed, i do not know yet how it should be interpreted exactly. net2

network.osrm.names

Simply the names of the edges, prefixed with their length. net3 This file is unsorted and is meant for forward references only. Edges with the same name will have only one entry in this file and will all point to the Nth line in this file. edges without a name all point to index 0

network.osrm.nodes

This file is a straightforward array of nodeinfo records : net4 The id is the original openstreetmap id, not an index. And this file contains all nodes in the original graph, before contraction. This file does not contain a node counter, so you will have to read all records to count the number of nodes.

network.osrm.edges

This file is a straightforward array of roadinfo records, the number of roads is already read in .osrm so it looks like : net5

  • Via node id is an index into the original nodes array so it will be between 0 and #originaledges-1.
  • name id is an index into the names array, so it will be between 0 and nnames -1
  • turn restriction is one of 16 possibilities meaning (-1 for 0 based):
changetitle
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
# "NoTurn",
# "GoStraight",
# "TurnSlightRight",
# "TurnRight",
# "TurnSharpRight",
# "UTurn",
# "TurnSharpLeft",
# "TurnLeft",
# "TurnSlightLeft",
# "ReachViaPoint",
# "HeadOn",
# "EnterRoundAbout",
# "LeaveRoundAbout",
# "StayOnRoundAbout",
# "StartAtEndOfStreet",
# "ReachedYourDestination"

An example of how you can read lines in this file :

changetitle
1
2
3
4
5
...
103 at node 47303 TurnSharpRight, onto road Am Graaf
104 at node 47303 TurnSlightLeft, onto road Rue Jean-Pierre Kirsch
105 at node 47303 NoTurn, onto road B 7
...

network.osrm.hsgr

This is the hierarchy file, containing all shortcuts added in the osrm-prepare step. net6 This files contains another number of nodes then the original nodes. These nodes represent the starting point for the edges that follow. The only parameter for the edges is the first edge that originates from this node, the last can be calculated by taking the next node's first edge and subtracting 1. The edge numbers are an index in the edges of the contraction hierarchy and are between 0 and (number of CH edges -1). The order of this list will very probably reflect the CH level of the nodes. The edges in the CH specify an edge id, which is an index in the original edges file and so these id's are between 0 and (original edges -1). The to id is an index in the CH nodes list and so is between 0 and (number of CH nodes -1).

network.osrm.ramIndex

network.osrm.fileIndex

example

Here is an example network to show the osrm buildup. net7 It has 9 nodes numbered 0-8 and 13 edges lettered a-m. All roads are bi-directional except l which only goes from 3 to 2. Also edge i is modeled with a middle (shape) node (8). The extracted .osrm file would look like this :

changetitle
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
# nodes : 9
10,5100000,409999,0,0
20,5170000,459999,0,0
30,5140000,480000,0,0
40,5130000,440000,0,0
50,5180000,430000,0,0
60,5160000,400000,0,0
70,5110000,480000,0,0
80,5170000,500000,0,0
90,5160000,440000,0,0
#edges : 14
8,60,10,67097,96620
4,30,20,36121,52015
7,40,20,46595,67098
12,40,30,29930,43100
10,10,40,39389,56721
9,90,40,33367,48050
3,20,50,23461,33784
11,50,60,30373,43738
1,10,70,50193,72279
13,30,70,33367,48050
2,40,70,35665,51358
6,20,80,27574,39708
5,30,80,36121,52015
9,60,90,27635,39795

You will probably be able to decode this, i will just mention the first node and edge : Node with id 10 is at coordinate 51.00000,4.09999 and has no bollards or trafficlights. (0,0) Edge 8 goes from node id 60 to node id 10 and has distance 67097 and weight 96620. Note that this is an intermediate file, not used in the final router. Here are the files that will be used :

.osrm.names

index name
0 "(null)"
1 "a"
2 "b"
3 "c"
4 "d"
5 "e"
6 "f"
7 "g"
8 "h"
9 "i"
10 "j"
11 "k"
12 "l"

This is simply a (road) name index, with 0 as the empty name for roads with no name. Node have no name, roads do, like streetnames etc. The index is used in the nameid field of each edge in the .osrm.edges file.

.osrm.nodes

index id latitude longitude
0 10 5100000 409999
1 20 5170000 459999
2 30 5140000 480000
3 40 5130000 440000
4 50 5180000 430000
5 60 5160000 400000
6 70 5110000 480000
7 80 5170000 500000
8 90 5160000 440000

The nodes file contains all nodes with their id and coordinates, sorted on id.

.osrm.edges

index at node do a to go onto
0 3 gostraight onto road g
1 3 turnslightright onto road l
2 3 turnright onto road b
3 3 turnslightleft onto road i
4 5 turnslightright onto road k
5 5 turnright onto road i
6 6 turnleft onto road m
7 6 turnsharpleft onto road b
8 2 turnright onto road l
9 2 turnslightright onto road m
10 2 turnsharpleft onto road e
11 3 gostraight onto road j
12 3 turnsharpleft onto road l
13 3 turnleft onto road b
14 3 turnsharpright onto road i
15 4 turnslightleft onto road k
16 7 turnsharpright onto road e
17 1 turnsharpleft onto road g
18 1 turnslightleft onto road c
19 1 turnsharpright onto road f
20 3 turnslightleft onto road j
21 3 turnsharpright onto road g
22 3 turnsharpleft onto road b
23 3 turnright onto road i
24 6 turnright onto road a
25 6 turnsharpright onto road b
26 7 turnsharpleft onto road f
27 0 turnsharpright onto road h
28 0 turnsharpleft onto road a
29 1 turnsharpright onto road d
30 1 turnleft onto road c
31 1 turnslightright onto road f
32 2 turnleft onto road d
33 2 turnright onto road m
34 2 turnslightleft onto road e
35 6 turnsharpright onto road a
36 6 turnsharpleft onto road m
37 8 noturn onto road i
38 1 turnslightright onto road d
39 1 turnright onto road g
40 1 gostraight onto road f
41 5 turnslightleft onto road h
42 5 turnsharpleft onto road i
43 0 turnsharpleft onto road j
44 0 turnleft onto road a
45 4 turnslightright onto road c
46 8 noturn onto road i
47 0 turnsharpright onto road j
48 0 turnright onto road h
49 2 turnslightleft onto road d
50 2 turnleft onto road l
51 2 turnslightright onto road e
52 3 turnleft onto road j
53 3 turnright onto road g
54 3 turnsharpright onto road l
55 3 turnslightright onto road i
56 1 turnsharpleft onto road d
57 1 turnslightleft onto road g
58 1 gostraight onto road c
59 2 turnright onto road d
60 2 turnslightright onto road l
61 2 turnslightleft onto road m
62 3 turnslightright onto road j
63 3 turnsharpleft onto road g
64 3 turnleft onto road l
65 3 turnslightleft onto road b
66 5 turnleft onto road h
67 5 turnsharpright onto road k

The edges file contains all edges generated. This is called en edge-expanded graph. Two steps are taken here :

generating graph nodes

For each segment in the graph two nodes will be generated, on for each direction. Example :

segment fromnode tonode
a 0 6
a 6 0
b 3 6
b 6 3

etc. Of course one-way roads will not become two but one graph node. In this case it will be 28 graph nodes, since the example has no oneway segments.

generating graph edges

For every possible movement between the edges, a graph edge will be created. In the example below i give the node numbers to specify the direction of the edge. So 0-6 means a,0,6 in the table above.

from graph node to graph node
0-6 6-0
0-6 6-3
0-6 6-2
6-0 0-6
6-0 0-3
6-0 0-5

So a u-turn is added as well ! The restrictions file is also considered in this step, so if a turn is forbidden, the graph edge is not created.

.osrm.hsgr

The hierarchy itself becomes a little too big to show in complete. So the middle part of the tables is skipped. 28+1 edge based nodes (0-27 plus 28 to specify the endroad of node 27 (startroad-1))

index startroad
0 0
1 4
2 4
3 6
4 11
5 16
6 20
24 130
25 133
26 136
27 139
28 142

There are 142 (0-141) edges in the hierarchy. # Note : that the from id's where generated from the above list.They are not in the real data. # Also note : that the column edge id points to edges in the hierarchy table (this table) when shortcut is 1, and in the original edges table if shortcut is 0.

index edgeid from to weight shortcut forward backward
0 47 0 5 72279 0 0 1
1 3 0 10 174142 1 0 1
2 9 0 10 123819 1 1 0
3 2 0 20 56721 0 1 0
4 27 2 1 56721 0 0 1
5 26 2 23 136415 1 1 0
6 22 3 0 144566 1 0 1
7 43 3 0 96620 0 1 0
8 22 3 4 211482 1 0 1
132 42 24 26 43738 0 1 0
133 4 25 2 96620 0 0 1
134 45 25 11 43738 0 1 0
135 67 25 27 39795 0 0 1
136 5 26 2 96620 0 0 1
137 24 26 10 77522 1 0 1
138 46 26 23 39795 0 1 0
139 66 27 3 39795 0 1 0
140 25 27 11 83533 1 1 0
141 37 27 22 48050 0 0 1

Why are there so much more nodes then in the input ? Because these are so-called edge-based nodes. These can be viewed as outgoing edges from a node, imagine it as the first step onto a road so you can't go in other directions anymore, the road is chosen. View the next picture, the red numbers are the edge base nodes, close to an original node (blue) means that they start from there.

net8

So for instance edgebased node 0 goes up, and 1 goes down, 22 goes right etc.. Note that (disclaimer : this seems to be so for these small examples)

  • the oneway street "l" still has two edge bases nodes
  • each road seems to be paired with it's following number if even or with it's predecessor if uneven : [0,1][2,3][4,5] ...
  • the edge based nodes are number starting from original node index 0, and then in increasing order of "original to-node index" (3,5,6 for original node 0)
  • if an edge was already numbered in a pair it is skipped, leaving only edges to higher numbered nodes. # edge base node 0-5 (node 0 to 3,5,6) # edge base node 6-13 (node 1 to 2,3,4,7) # edge based node 14-19 (node 2 to 3,6,7) (1 is already numbered) # edge based node 20-23 (node 3 to 6 and 8) (0 and 1 already done)

regular segments

A regular segment can be forward or backward directed.

forward

A forward segment simply reads. Let's take one from the example table

index edgeid from to weight shortcut forward backward
3 2 0 20 56721 0 1 0

in combination with rule (2) from the segment descriptions

index at node do a to go onto
2 3 turnright onto road b

Index [3] : there is a road 56721 long from segment 0 leading to segment 20, and it turns right onto road b at node 3. Watch the segment and node indices here.

backward

The backward version, again with an example :

index edgeid from to weight shortcut forward backward
0 47 0 5 72279 0 0 1

and

index at node do a to go onto
47 0 turnsharpright onto road j

Just swap from and to node to get : There is a road 72279 long leading from segment 5 to 0 and it turns sharp right at node 0 onto road J.

shortcuts

Shortcuts have a different interpretation of mainly the edge-id. The highest index in non-shortcut rules is 67 (the number of hierarchy edges). And 27 for shortcuts (the number of original edges). So a forward rule reads :

index edgeid from to weight shortcut forward backward
2 9 0 10 123819 1 1 0

There is a shortcut of 123819 long going from edge 0 to edge 10 and it's last segment is edge 9.

reverse

index edgeid from to weight shortcut forward backward
1 3 0 10 174142 1 0 1

This is the same principle : swap from and to There is a shortcut of length 174142 going from 10 to 0, and it's last segment is edge 3.

Hierarchy

The last (reverse) example only presented part of the hierarchy. It gave the total length of the shortcut : 1 (c) 4 (k) 5 (h) 0 : 174142 And it gave the end segment (h). However if you want to print a route, you need the other segments as well.

index edgeid from to weight shortcut forward backward
137 24 26 10 77522 1 0 1

This is a shortcut (also reverse) of 77522, going from 10 to 26 with 24 as last segment. Here are all the shortcuts broken down :

index from to via length path pathnrs
0 22 0 3 184465 i-i-h 22-27-3-0
3 11 1 8 100882 c-g 11-8-1
4 1 11 2 197079 j-h-k 1-2-25-11
7 2 1 23 184465 h-i-i 2-26-23-1
8 2 5 23 235823 h-i-i-b 2-26-23-20-5
10 2 11 25 140358 h-k 2-25-11
12 22 3 27 87845 i-i 22-27-3
14 11 4 1 157603 c-g-j 11-8-1-4
15 21 4 1 108079 b-j 21-1-4
17 0 5 20 108079 j-b 0-20-5
19 5 1 2 256744 a-h-i-i 5-2-26-23-1
20 5 11 2 212637 a-h-k 5-2-25-11
36 7 16 12 143738 d-f-e 7-12-19-16
69 12 16 19 91723 f-e 12-19-16

140 27 11 25 83533 i-k 27-25-11

routing algorithm

first pair of stacks

This is logical: we need as forward stack for routing from point A and a backward stack routing from point B. But the code has 2 forward and 2 backward stacks. One problem arising when starting a route is that you provide coordinates, but these do not match the closest node, but the closest edge based node. And such a node has a specific direction. Take for example node 19 in the picture above. So that is starting downward (as way e) from node 7 and is 50215 long. What we actually means is that we start at node 7 and should be able to use edge-based-nodes 19 AND 13. This is circumvented by running another Dijkstra when a node is bi-directed. The segment-based node found is actually always the lowest one of a pair. For instance we search for the segment with the coordinates of NODE 7 (right top) and we get a segment-pair that contains this coordinate. And that's 18-19. It probably could have been 12-13 as well, but it is not. Now 18 is added with a weight of -1 * 50215, so it will arrive exactly at 0 in node 7, and can than go in any direction. And 19 will be added with cost 0 to start just from scratch.

Second pair of stacks

Now the second pair of stacks is somewhat unclear, it definitely matters if you use them. Routing from node-pair 18-19 (7) to 10-11 (4) gives shortest of 73492 for stackpair 1 and 226698 for stackpair 2 this is mainly the route c-f and k-i-i-l-e routing from 7 to 4 (reverse) gives. shortest of 137814 (e-d-c) and 73492 : (f-c) So now stack2 gives the correct result, so it seems needed. What i presume is happening is that in searching for a phantom node, you find not point 7, but edge-based node 19. That would mean only edge e is considered and not f, while you want both. So the opposite edge-based node 18 is also added with a negative cost of -52015, so it will arrive at 7 with a cost of 0, and can plan onward onto edge 13 (f). This would also work if 7 had more than two edges attached. I wonder if it would pay to start the Dijkstra by first getting node 7 and finding all it's attached edge-based nodes, and putting all these into the heap. It would mean halving the calculation time. Also it would simplify the Matrix generation algorithm.

troubleshooting

wrong edge count

I mailed Dennis about this, the file .osrm.edges contains the number of original edges followed by the edges themselves. But the count in that file is wrong for now (until osrm add's my patch). The file is written in chunks of 100001, and the remainder is written after finishing the main loop. But the loop count is correctly maintained. However after the loop the remainder is added again, so the count is too high. Fix this by hand by commenting/disabling the line : numberOfOriginalEdges += originalEdgeData.size(); In Contractor/EdgeBasedGraphFactory.cpp

cannot find first segment of edge

When you encounter lines like these, there is something wrong with the data. First note that this only appears in a DEBUG compiled version. So if you get it in the fastcgi file and not in for example osrm-routed, check your compiler flags. To compile osrm-routed with debugging : scons --buildconfiguration=debug

changetitle
1
cannot find first segment of edge (30793,30789,1588591)

IT means an inconsistent contraction hierarchy (the .hsgr file). Do not use networks that spawn these errors

shared memory problems

The symptom is that the program using libosrm.a crashes with a message like this:

changetitle
1
2
3
terminate called after throwing an instance of 'osrm::util::exception'
what():  No shared memory block 'osrm-region' found, have you forgotten to run osrm-datastore?include/storage/shared_monitor.hpp:83
Aborted

It seems you need to prepare the network for shared memory use first. The explanation is here : https://github.com/Project-OSRM/osrm-backend/wiki/Configuring-and-using-Shared-Memory

But in short this command works :

changetitle
1
./build/osrm-datastore /data/netherlands-latest.osrm

Of course you need to be in the osrm-backend directory and that should be your data file base. One hiccup though is that it seems to work, but the command does give a couple of warnings :

changetitle
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
[info] Data layout has a size of 1745 bytes
[info] Allocating shared memory of 137216122 bytes
[warn] could not lock shared memory to RAM
[info] Data layout has a size of 1283 bytes
[info] Allocating shared memory of 398684997 bytes
[warn] could not lock shared memory to RAM
[info] All data loaded. Notify all client about new data in:
[info] /static  0
[info] /updatable       1
[info] All clients switched.

TODO: find out exactly how this works and how it works on Europe or even the world.