[Routing] Routing algorithms

Chris Fleming me at chrisfleming.org
Thu Nov 8 16:43:00 GMT 2007

Alex Wilson wrote:
> I've also been implementing routing over OSM data - using the Boost 
> graph library (BGL). I have a GUI written in PyQT4 interfacing with a 
> routing backend written in C++, using Boost python to create the 
> interface between the two languages.
> It's a nice solution because there are a large number of algorithms in 
> the BGL and they've all been very thoroughly tested.
> I was also considering using the boost spirit parser to allow users to 
> specify edge costs using expressions - so if, for instance, you were a 
> law-breaking cyclist, you could specify that you were happy too cycle 
> down one-way streets the wrong way if ever it would save you 
> significant time over a legal route ;-)
The other way of thinking about one ways is that a cyclist could cycle 
down a normal street at say 10 to 20 miles an hour, but walk down a one 
way street at 4 miles an hour so this is a valid thing to do, without 
breaking the law...

There are a few other  interesting cyclist problems, we have a LOT of 
cobbled roads which I'm happy for up to 100m but any longer is painful; 
it would be great if the algorithm could account for this and increase 
the cost of long sections of cobbles.

The other issue that has a big effect on journey times is traffic 
lights, nodes with traffic lights need to have additional cost added... 
(we spend a lot of time at work debating the merits of the slightly 
longer off road cycle route which is pretty much traffic light free with 
the more direct on road route which is free of traffic lights,  and a 
colleague pointed me to a non obvious route that while longer was 
significantly faster.)

Lots of people seem to be working on there own routing solutions, would 
it make sense to pick one and work co-operatively...


> ------------------------------------------------------------------------

More information about the Routing mailing list