[Routing] A-Star meet-in-the-middle

OJW streetmap at blibbleblobble.co.uk
Tue Nov 20 21:37:07 GMT 2007


On Tuesday 20 November 2007 21:13:11 Nic Roets wrote:
> (Why aren't we discussing the important issues, like adding a penalty
> to right turns at intersections... ?)

The example I found while demonstrating pyroute was (routing from A to B along 
the brown cycle path):

http://wiki.openstreetmap.org/images/6/6d/Bedford_bridge.png

What the routing algorithm doesn't realise is: because the red node is also 
part of a main road, it takes 2.5 minutes to go from one side to the other, 
as you wait for the pedestrian crossings.  Taking another route (in red on 
that diagram) under the bridge* will save a lot of time not because of the 
distance, but because of not having to cross the road.

Unfortunately, that means you need to start analysing each junction node to 
give penalties for going across it in certain directions (not dissimilar to 
the right-turn example I guess)



* actually, the red route here needs to be marked as flood-prone, so that when 
your mobile device downloads the weather report and discovers that it's been 
raining for a while (or downloads the data from upstream locks), it knows to 
avoid that route which is underwater...





More information about the Routing mailing list