[Routing] Getting A* to prefer Motorways

[Andreas Leupin]

Hi,
A* seems to be quite fast then and therefore promising to me.  
However, I work actually at a different concept, which, on first  
sight may look strange, but I think that it may have some advantages  
over other methods:

My idea is to calculate backward from destination to start and doing  
this to determine for every end of an edge in the map the lowest cost  
to the destination (taking into account btw all the turn restrictions  
at the nodes). I try to formulate this in more detail in a "yellow  
paper" hopefully in the next one or two weeks.  I have published  
apreleminary version (containing the introduction for test purposes)  
on my website "www.leupinfo.ch/OpenGPScout"...

The advantages I see for this procedure are as follows:
- turn restrictions (and driving restrictions at start and  
destination) can be taken into account quite easily;
- the first calculation itself may be more time consuming  (but I  
have not yet estimated the exact differences for that - because I  
need no sorting of any kind for the nodes, this may not be so bad...)  
than using A* but during the navigation I have the advantage to know  
the best route from every node - therefore a recalculation of the  
route is possible extremly fast if necessary - and this is IMHO very  
important during the navigation.
- The memory usage is probably smaller than with A* (or at least it  
is easier to determine - in principle I need one byte per node and  
appr. 5 bytes per edge to hold the cost to the destination during the  
calculation)

This only as a short input to the discussion...

Best regards
Andreas



Am 30.09.2007 um 16:22 schrieb Marcus Wolschon:

> -----BEGIN PGP SIGNED MESSAGE-----
> Hash: SHA1
>
>
> Hi,
>
> thanks for all the answers. :)
> finally solved my problems and now routing has become
> incredibly fast. :)
> (A route between a street in the middle of Freiburg,
> up the A5-motorway into a street smack in the middle of
> Karlsruhe in 90-23ms.) And I haven't even started reducing
> the map yet (eleminate nodes, ways and tags that are not
> required or allowed for routing).
>
> - ------------- algorithm used
>
> In the end I used the heuristics for choosing the path to
> descend for the recursion in A* but applied it to sorting
> the stack of nodes to examine in Dijkstra. It seems I was
> wrong in my estimations about the expected memory-footprint.
> Stack-Size is far more limiting for me.
>
> It looks like traveling-salesman may actually hit the road
> this week to see how well it performs outside the lab.
> (driving into one of the big white spots on the map anyway.
>  mapping on the way to, testing routing on the way back a few
>  days later.)
>
> - ------------- Havenstine-distance
>
> I think using the Havenstine-distance is not an issue
> unless routes get incredibly long (like spain->china).
>
> - ------------- outcome of the motorway-issue
>
> I found in my code that it did not avoid the motorway
> (I had a penalty multiplied to the distance for leaving
> onto a "lesser" road) but simply got cought in some loops
> due to a typo in the code.
> It routed fairly well without being actually attracted to
> the motorway but discouraged to leave it by this factor.
>
> PS:
> Are there any plans to specify how to tag turn-restrictions
> and house-numbers yet? With the upcomming relations this
> was supposed to become possible and I can't wait to add
> support for both.
>
>
> Marcus
> -----BEGIN PGP SIGNATURE-----
> Version: GnuPG v1.4.6 (GNU/Linux)
> Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org
>
> iD8DBQFG/7Ehf1hPnk3Z0cQRAvtxAKCcXjM9+BznpiXpHROHrMHZZuCeMwCgoO6Z
> evGByXrHxdCmZCovM+k1PBA=
> =XbTb
> -----END PGP SIGNATURE-----
>
> _______________________________________________
> Routing mailing list
> Routing at openstreetmap.org
> http://lists.openstreetmap.org/cgi-bin/mailman/listinfo/routing

Andreas Leupin
Kretzgasse 2
CH-5416-Kirchdorf
Tel. P [+41](0)56 282 07 40
        G [+41](0)56 310 39 32
a.leupin at hispeed.ch



-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.openstreetmap.org/pipermail/routing/attachments/20070930/988d6f5b/attachment.html>