[Routing] Fast Routing Engine - State of Play

[Florian Detig]

> > in munich there was a small research project applying (Geisberger) 
> 
> contraction hierarchies with osm data to do energy efficient 
> routing.
>  We ran into some issues with negative edge weights (e.g. 
> electronic 
> car downhill) What are your views on this?

That's 
> easy to fix. Add a large enough constant to all of your edges
until all are 
> non-negative (or non-zero). Electric cars are all 
> about
potentials.

hmm.. makes sense. although I still don't get what difference that would make :/ Geisbergers algorithm did produce results, albeit weird ones sometimes. probably my personal understanding of how these algorithms work is insufficient...

> @Brandon @Denis (How) does your implementations 
> differ from Robert 
> Geisbergers implementation?

At the moment, 
> the preprocessing is still the same. That's going to
change as 
> well.

did someone think of / try a MapReduce approach for preprocessing contraction hierarchies? maybe it could help parallelize computation and iteratively approximate betweeness centrality to pick the "right" nodes for higher "levels"..

btw what is it anyway that guarantees the algorithm to find a/the shortest path in the end? if only higher level (shortcut) edges are expanded and lower ones are pruned, why aren't there any shorter paths that stay undiscovered?
(plz excuse if this the wrong place to ask.. but this keeps puzzling me)

kind rgds
flo


Brandon already mentioned in another email that he has is 
> own
implementation.



--Dennis

_______________________________________________
Routing 
> mailing list

> href="mailto:Routing at openstreetmap.org">Routing at openstreetmap.org
http://lists.openstreetmap.org/listinfo/routing