[Routing] Fast Routing Engine - State of Play

[Florian Detig]

this sounds really promising!
can't await playing around with it..

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?
@Brandon @Denis (How) does your implementations differ from Robert Geisbergers implementation?


flo




----- Original Message ----
> From: Dennis Luxen <luxen at kit.edu>
> To: routing at openstreetmap.org
> Sent: Thu, April 1, 2010 3:43:14 PM
> Subject: [Routing] Fast Routing Engine - State of Play
> 
> Dear list,

at FOSSGISS 2010 I promised to deliver a fast routing engine 
> for the
community to use and ready for OSM data by May of this year. I intend 
> to
keep this promise.

Now, here is the good news. Since last saturday, 
> the engine is running
with OSM data and is serving requests. At the moment it 
> is a private
beta run as the software stability needs to improve. I have 
> notified
some of the OSM/routing people I know to let them have a try. Thanks 
> to
those who already tested it. I look forward to having an open beta 
> soon.

The engine is going to be just an engine and not just another 
> routing
web site. I am not good at building web sites and there are 
> already
several of them. What they lack is fast and exact routing. 
> Therefore,
the engine intends to fill that void by providing an easy to use 
> API
that reachable by HTTP and returns an XLM file describing the route. 
> At
the moment it is a rudimentary GPX file describing the geocoordinates 
> of
all points on the route and does not feature route directions or 
> any
driving assistence yet. But this is certainly a major field of work 
> for
the future.

So, why is the source not public yet. There are 
> several reasons. The
first one is/was that I needed time to code it and who 
> really needs just
another half-working software product? Although the core 
> algorithm had
been open-source for quite some time, there was code that had 
> to be
rewritten, added or adapted to fit into the server setting. The 
> other
reason is that not all license issues are cleared yet. But don't 
> fear,
'cause these issues will be resolved by May.

Meanwhile, the 
> development will progress and the todo list is still
getting longer everyday. 
> I have several features planned, that are not
implemented yet.

Let's 
> take a brief look at some of the technical features:

The engine is based 
> on the Contraction Hierarchies algorithm published
by Geisberger et al. in 
> 2008 (http://algo2.iti.kit.edu/1087.php). The
current code runs on Linux but 
> compiles on Mac OS X as well. Other OSes
are untested at the 
> moment.

The performance right now is dominated by communicating the 
> result of
the computation over the network. For a cross country route [1] 
> through
Germany it takes less than a milisecond to compute the route, but 
> around
25 miliseconds to send the actual output to the client over the 
> network
on a Core2Duo CPU. Numbers for roads on the European road network 
> are
similar.

Best wishes and happy easter 
> holidays,
Dennis

[1] 
> http://www.dennisluxen.de/route.zip

_______________________________________________
Routing 
> mailing list

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