[Routing] Implementing Turn-Restrictions

[Marcus Wolschon]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1


Hello.
Does anyone have a description of the Shooting* -algorithm?
(see below.)

Frederik Ramm schrieb:
> How do you intend to do turn restrictions in A*? The basic algorithm
> will never re-visit a node it has already processed, right? 

I dumped A* in the process. It's back to dijkstra now.


> Imagine the graph (fixed-width font please)
> 
>       C
>      /
> A---B
>      \
>       D
...
> A reasonably simple solution I could think of would mean that the
> graph be modified by introducing pseudo nodes and edges:
> 
>       C
>        \
> A---B   B'
>      \ /
>       D


Sounds like a good idea to turn "turn-restrictions" into the
simpler case of oneway-streets.

> ... surely a problem that has been solved in literature
> somewhere?

PGRouting seems to have implemented an algorithm names
Shooting* that can do turn-restrictions.
However I could not find much about it because shooting-star
is not exactly an uncommon phrase. ;)

Marcus
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.6 (GNU/Linux)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org

iD8DBQFHAHa7f1hPnk3Z0cQRArjBAJwJcKigMzrY7tZ2iG8pzf7RA8gKCwCgj00c
P4+y4goS5VgRYqnde5K6wU0=
=o3l5
-----END PGP SIGNATURE-----