[Routing] Yet another parser

[Dennis Luxen]

> Yes, I've read a few papers on that page. There is a lot of info there 
> which would require a lot of time to fully understand. But the math 
> formulas is not really what I'm interested in, the practical usage is.
> 
> The only thing that I could not find is if CH model is able to provide 
> routing for different kinds of transport (with their different edge 
> weights) within the database or that one has to build a database for 
> every set of rules.

If you only have a few edge weight functions, then it is probably the 
easiest to have different routing data structures or databases as you 
call them.

There is also a master thesis on the subject of flexible objective 
functions. So, there should be more information on that available 
shortly. Anyway, there is also another speedup technique calles SHARC 
that has a variant that does pareto optimal paths, which might be what 
you are looking for. The corresponding paper is called "Pareto Paths 
with SHARC" and available from here:

http://i11www.iti.uni-karlsruhe.de/members/daniel_delling/publications

> I see that your name is mentioned on the project page, so I would like 
> to ask some questions:
> Did you experiment with OSM data, or did you use the commercial dataset 
> that was used for the other papers?

For the publications commercial data sets were used, which are denser 
than the OSM data sets. I experimented on the OSM data about a year ago 
for a many-to-many routing application for ride sharing. You can find a 
related technical report here, but it does not go into any OSM specific 
details: https://algo2.iti.uni-karlsruhe.de/1377.php

> Can you give some insight in how practical it would be to use the 
> existing GPL licensed CH code for http://www.yournavigation.org (world 
> wide routing, faster, better then the current solution with Gosmore)? 

I don't know the routing core of Gosmore, but I assume that it is using 
some simple routing algoritmhm. From that assumption I'd guess that CH 
would perform faster and better than Gosmore.

> E.g. what has to be done to get car, bicycle and truck routing?
> How much RAM and disk space is approx. required when working with the 
> OSM planet file?

Easist approach would be to have seperate routing data structures for 
each vehicle type. First of all, one would parse the world file and 
extract the paths that can be accessed by the vehicle type. Bicycles 
don't use highways and trucks don't use bicycle tracks. One problem 
might be the inconsistent quality of the OSM data. The road network 
might not be strongly connected.

I can only give rough estimates on the numbers here since my experience 
is limited to the german subgraph only. So, I think it is best to point 
you to the numbers in one of the papers, i.e. see page 19 of that one: 
https://algo2.iti.uni-karlsruhe.de/1328.php

Preprocessing for Contraction Hierarchies of Europe (18 Million nodes, 
42.6 million edges )is about 25mins and the space overhead is negative, 
meaning that the routing data structures needs less space than the 
original road network. Also note, that this preprocessing does not 
include the conversion of the XML-based OSM-data to a more usable 
format. That would come in extra, but like the CH preprocessing it is 
only necessary once.

I don't know the number of road segments and waypoints of the planet 
file that are needed for routing, so I can only speculate. But the 
numbers for the commercial road network of Europe should give you an 
impression.

The CPU load for a single query will be much less, since it can be 
answered with much less effort.

-Dennis