[Routing] Bad routing: U turns for highway links?

[Stephen Woodbridge]

Anthony wrote:
> On Wed, Jul 21, 2010 at 10:12 AM, Stephen Woodbridge 
> <woodbri at swoodbridge.com <mailto:woodbri at swoodbridge.com>> wrote:
> 
>         On Sat, Jul 17, 2010 at 10:52 PM, Alan Millar <am12 at bolis.com
>         <mailto:am12 at bolis.com> <mailto:am12 at bolis.com
>         <mailto:am12 at bolis.com>>> wrote:
> 
>            Am I really asking something unreasonable of a router that
>         when an
>            xxxx_link way meets an xxxx way at a very low angle, the
>         router should
>            know to go forward and not almost reverse?
> 
> 
>     To some extent yes, this is unreasonable to ask of the router. While
>     it is not totally impossible to build a router to do this, routing
>     algorithms do not deal with geometry they only deal with
>     connectivity. You have to have geometry to deal with angles. While
>     this could be added to the preprocessing of the data into the graph
>     file you would have to represent it as another cost constraint or as
>     a turn restriction and the router would need to be "aware" of how to
>     handle these.
> 
>     It is better to fix the data, period!
> 
>     You can not expect all routers to implement every weird hack to work
>     around all the weird data problems that various data sources have
>     and might want the router to handle. This is just not reasonable.
> 
> 
> My concern is that the turn is not per-se illegal, it just isn't a good 
> idea when there's traffic around.  Under Florida statutes, a U-turn can 
> be made outside the city so long as it "can be made in safety and 
> without interfering with other traffic and unless such movement is not 
> prohibited by posted traffic control signs".  So my understanding is 
> that this turn, absent a double-double yellow dividing median (which 
> *is* present in the original example), would be legal.  On the other 
> hand, unless it's 3 AM and there aren't any other cars on the road, it 
> probably can't "be made in safety and without interfering with other 
> traffic".
> 
> So, it seems to me that the only way to perfectly correctly handle this 
> would at the point of the router.

So what rules are you proposing the router should implement again?
How is the router supposed to know "when there's traffic around" so it 
should change its behavior?

There is nothing in your above explanation that would lead me to believe 
that this should be in the router. I the data model does not support 
encoding all these information then that should be fixed. If the process 
of loading the data into the router does not carrier all the data 
forward then that needs to be fixed. And if the router does not support 
turn-restrictions then that needs to be fixed.

In most cases that I have seen, routing problems are caused by data 
issues. And most of these problems are related to errors in the source 
data, but some are related to problems in constructing the appropriate 
restrictions needed to model the real world.

Things like turn restrictions should be implemented in the data. Turn 
restrictions can represent physical restrictions like barriers, or legal 
restrictions like signs, or vehicle classes like police and emergency 
vehicles, cars, trucks, mopeds, etc, and restrictions can have time 
information encoded into them, like this restriction only applies 
between 7AM-10AM or whatever. Navteq does this in there data and then it 
is up to the router to implement the restrictions for the class of 
problems it is trying to solve. In a GPS it has time information so it 
can apply time restrictions. But a site like Google maps does not worry 
about time restrictions as it is not doing real-time planning.

The actual routing code depending on the algorithms used, is pretty well 
documented and researched in Universities.

Best regards,
   -Steve