[Routing] Getting A* to prefer Motorways

[hubert schmid]

Hi,

there is an iterative way to solve it (not tested jet ;)) 

1. find a route
2. check the route for restrictions
3. no restriction on the path - route found -> END
4. else (restriction found):
5. increase the resist of the following link to very high
6. goto 1

The resist is the cost-value for a link, for example 
the distance if you just look for the shortest path.
But normally, the resist depends on more values like
the type of road or traffic state, so it should be 
dynamicly changeable at runtime.

In your example, the resist of the B-to-C link has to
be set to a very high value. In the next iteration 
this possibility is blocked. Afterwards you have to
clean up and reset the resist of all links and D-to-C
is open again.

Of course, it is not perfect and there could be 
problems in networks with masses of restrictions, but
in normal networks it should work without manipulating
the node-link structure.

Bye Hubert

-------- Original-Nachricht --------
> Datum: Mon, 1 Oct 2007 01:25:13 +0200
> Von: Frederik Ramm <frederik at remote.org>
> An: routing at openstreetmap.org
> Betreff: Re: [Routing] Getting A* to prefer Motorways

> Hi,
> 
> > 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.
> 
> One other thing: 
> 
> How do you intend to do turn restrictions in A*? The basic algorithm
> will never re-visit a node it has already processed, right? 
> 
> Imagine the graph (fixed-width font please)
> 
>       C
>      /
> A---B
>      \
>       D
>      
> With turn restrictions, it may well happen that the route
> 
> A-B-C
> 
> is not allowed, while
> 
> A-B-D-B-C
> 
> is valid. But A* will never use the D-B step in the above example if I
> am not mistaken. 
> 
> 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
> 
> But I would almost guess that this introduces a truckload of problems
> somewhere else... surely a problem that has been solved in literature
> somewhere?
> 
> Bye
> Frederik
> 
> -- 
> Frederik Ramm  ##  eMail frederik at remote.org  ##  N49°00.09' E008°23.33'
> 
> 
> _______________________________________________
> Routing mailing list
> Routing at openstreetmap.org
> http://lists.openstreetmap.org/cgi-bin/mailman/listinfo/routing

-- 
Ist Ihr Browser Vista-kompatibel? Jetzt die neuesten 
Browser-Versionen downloaden: http://www.gmx.net/de/go/browser