[Routing] Routing algorithms

Alex Wilson alex_wilson at pobox.com
Thu Nov 8 17:02:51 GMT 2007


I agree that it would be interesting to have node costs too. And for cobbled
streets, it would be easy to have an edge cost algorithm that included a
consideration for max distance that is comfortable.

Obviously having a parser for specifying edge and node costs could
significantly slow routing, and might preclude the use of pre-computed fast
routing systems, but might be useful for small-ish distances, or perhaps the
beginning and end of routes calculated using a more sophisticated
highway-aware system.

A.

On 08/11/2007, Chris Fleming <me at chrisfleming.org> wrote:
>
> 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...
>
> Cheers
> Chris
>
>
> >
> > ------------------------------------------------------------------------
>
> _______________________________________________
> Routing mailing list
> Routing at openstreetmap.org
> http://lists.openstreetmap.org/cgi-bin/mailman/listinfo/routing
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.openstreetmap.org/pipermail/routing/attachments/20071108/9cbbea76/attachment.html>


More information about the Routing mailing list