[Routing] turn-restrictions working in Traveling Salesman

Marcus Wolschon Marcus at Wolschon.biz
Tue Mar 24 07:26:45 GMT 2009


On Fri, 20 Mar 2009 17:27:30 +0200, Nic Roets <nroets at gmail.com> wrote:
>> Can you give some more details about how you did it?
> 
> Give numbers to all your segments (gosmore uses "double half segments"
but
> the idea is the same)
> 
> Then you have an array of Dijstra nodes :
> struct DijkstraNode {
>   int segnumber;
>   boot forwards; /* Are we traveling forwards or backwards ? */
>   float distance;
>   boot unprocessed;
>   /* For A* you may have an additional variable for the heuristic */
> }
> 
> Each (segnumber, forwards) pair may only occur once.
> So for each Dijkstra iteration you look in the array for the dijkstraNode
d
> with the lowest distance with unproceesed equal to TRUE.
> * If forwards is true, you find the OSM node n to which the segment is
> pointing to. Otherwise n is the OSM node that the segment is coming from.
> * Now you look at all the segments s connected to n. (Gosmore will
current
> not consider s=d.segnumber, so u-turns back into the same way are not
> allowed) Can I travel from d.segnumber to s ? If yes, add
> (segnumber=s,unprocessed=TRUE) to the dijstraNode array. If it's already
in
> the array and the new distance is shorter, update it.

Thanks a lot for the suggestion Nic!
I was able to implement it and it seems to work fine.
Other then your implementation I does allow u-turns
(unless a no_u_turn -relation exists).

As I already have a RoutingStep -class that is used to abstract
between routing-engines and diving-instruction-plugins I could do
away with the "bool forwards;" and segment-numbering. A RoutingStep
contains a start-node, way and end-node.
I do not mark them as "unprocessed" as I keep one sorted set of
RoutingSteps to be processed and one map of the best step for each
processed one.

Announcement:
  http://apps.sourceforge.net/phpbb/travelingsales/viewtopic.php?f=3&t=46
I'll update the Java Webstart -version of Traveling Salesman tonight
in case anyone wants to play around with it.

Marcus

>> "a user who simply looks for a navigation or routing- application to
USE"
> 
> Note that a user does not need to know what algorithm the program uses.

I agree that many would not care and just skip that point.
The ones who care would like to know and the others dont care.
As most of them are free software I as a developer do care as
it shows me where I can look for reference as I just did with your
turn-restrictions.

> AFAIK the house number data in OSM is still quite limited. So saying
'Yes'
> is very misleading to a newbie.

I don't think think so. It is an important feature to distinct between
the capabilities of the different programs. That's what the table it about.

> Will you update your table when new versions of gosmore is released ? I
> doubt it. So your table will just continue to mislead newbies.

If I notice such a change in
http://wiki.openstreetmap.org/wiki/Gosmore
yes, I will update it acordingly.

> I can't see how a smart guy like you can think it's acceptable to just
make
> up facts.

What factual errors remain in the table?

Marcus




More information about the Routing mailing list