Dennis Luxen | 1 Apr 15:43 2010

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

Gmane